Introduction
We have already discussed some terms that describe different properties of graphs and we have considered directed, undirected and weighted graphs.
In this lesson we will see some other ways to classify graphs.
Connected and complete graphs
A graph is connected when no vertices or group of vertices are isolated from the rest of the graph. When a part of the graph is isolated, it is said to be disconnected.
If we remove a bridge from a connected graph the graph will become disconnected.
We call a graph on n vertices complete if every vertex is connected to every other vertex. There is exactly one complete graph for each value of n.
The degree of each individual vertex is equal to one less than the number of vertices overall. In other words, if you take n vertices and connect one to all the others, you draw n-1 edges from each vertex.
Examples
Example 1
In a connected graph:
A directed graph's edges indicate a one-way relationship and are represented by arrows.
A weighted graph's edges are assigned a number that can represent some property, such as distance or cost. Weighted graphs may be directed or undirected.
In a connected graph, no vertices or group of vertices are isolated from the rest of the graph. When a part of the graph is isolated, it is said to be disconnected.
In a complete graph, every vertex is connected by an edge to every other vertex.
Simple graphs
A graph is called a simple graph if it has:
no loops, and
no multiple edges.
The first graph is not simple because it has loops. The second graph is not simple because there are multiple edges between some vertices. The third graph is simple - no vertex is connected to itself, and no vertex is connected to any other in more than one way.
Examples
Example 2
Consider the following network:
What two changes could be made to make this network simple?
A simple graph is an undirected graph that contains no loops or multiple edges. A simple graph can be connected or disconnected.
Subgraph
A graph is called a subgraph (or subnetwork) when all vertices and edges are also the vertices and edges of another graph.
If we take a graph and delete some edges, or some of its vertices (and all edges connected to it), we obtain a subgraph of the original.
For example, any simple graph that has n vertices is a subgraph of the complete graph with n vertices - we can just add or delete edges to get from one to the other:
The graph on the left has the red edges added in to get the middle graph, and then the vertices are moved to get the right graph, which is a complete graph.
Examples
Example 3
Consider the following two graphs:
Is Graph 2 a subgraph of Graph 1?
A graph is a subgraph if all vertices and edges are also the vertices and edges of another graph.
Bipartite graph
A bipartite graph is a graph whose vertices can be divided into 2 groups such that each edge connects a vertex from one group to a vertex in another. Vertices in a group are never connected to other vertices in that group.
A bipartite graph does not have to be drawn in with the groups of vertices arranged in rows (although they usually are).
Examples
Example 4
Which of the following graphs are complete bipartite graphs?
A bipartite graph is a graph whose vertices can be split into two groups, where each edge connects a vertex from one group to a vertex in the other group.