Graphs can be of several types.
Basic Graphs
-
A graph with only arcs is called a directed graph, while a graph with no arcs is called a non-directed graph. A graph with both arcs and non-directed edges is called a mixed graph.
- These two concepts help us define a subjacent graph.
-
A null graph is a graph that has no vertices or edges.
-
A trivial graph is a graph that consists of a single vertex with no edges.
-
A proper graph is a graph with an edge that joins two different vertices.
-
A general graph (or pseudo-graph) is a graph that consists of at least one loop or at least one multi-edge.
-
A multi-graph (or loop-less graph) is a graph that has at least one multi-edge, but no loops.
Elegant Graphs
-
A simple graph is a graph with no multi-edges or loops.
-
A regular graph whose vertices all have the same degree.
-
A complete graph is a graph where every vertex pair is joined by an edge.
Connected Graphs
-
A connected graph is a graph where we can reach any vertex from any other one.
- A strongly connected graph is a connected graph where we can also reach any given vertex from itself.
Bipartite Graphs
-
A bipartite graph is a graph that can be “separated” into two interconnected graphs
- A complete bipartite graph is a bipartite graph where all the vertices of each subgraph are connected between each other.
Subgraphs
A subgraph is a graph contained within another graph.
-
Edge-disjoint subgraphs are subgraphs that don’t share any edges.
-
Vertex-disjoint subgraphs are subgraphs that don’t share any vertices.
When we erase most of the edges in a subgraph while keeping only the necessary ones to join all the vertices, we get an expanded subgraph.