Graph Terminology
It is convenient to introduce a bunch of terminology in connection with graphs. We will only be concerned with undirected graphs. However, a corresponding terminology exists for the directed graphs for each terminology we describe here. We will deal with directed graphs at a later point in time.
The processing of graph data structures is heavily dependent on the ability to quickly and systematically access vertices of a graph, starting with any initial vertex. Therefore, graph search or accessibility of the vertices from one or different vertices is essential. The accessibility or reachability in a graph is defined in different contexts as follows:
Path: There is a path from a vertex v to another vertex w if there is a sequence of vertices v, v1, v2, …, vk, w such that there exists edges between every pair of adjacent vertices of the sequence. That is, the graph has the following edges:
- (v,v1) ∈ E,
- (vi,vi+1) ∈ E, for 1 ≤ i ≤ k-1, and
- (vk, w) ∈ E.
Degree of vertices: Degree of a vertex is equal to the number of edges incident on it.
Simple path: A path is called a simple path if every vertex on the given path is distinct.
Length of a path: The number of edges on a path equals its length. So if a path represented by a sequence of k vertices then its length is k-1.
Simple cycle: A simple cycle is a simple path where the two end vertices are also connected with an edge.
Connected graphs: A graph G is connected if and only if there exists a path between every pair of vertices in G.
Subgraph: A graph H = (V1, E1) is a subgraph of a graph G=(V, E), if V1 ⊆ V and E1 ⊆ E.
Connected component: A maximally connected subgraph of a graph is known as a connected component of the graph. The maximality of a subgraph means that if we add one more vertex from the graph to the subgraph, it no longer remains connected.
Bipartite graphs: A graph G = (V, E) whose vertex set V can be divided into two disjoint sets V1 and V2 such that any edge has one end point in V1 and the other in V2.
Let us check some examples to understand the definitions we have learned. We begin with an example of a graph in the picture below.
Figure 1
The degree of vertex a is denoted by deg[a]. Since three edges are incident on a, deg[a] = 3. The table below lists out the degrees of a few of the vertices in the above graph.
| Vertex | Degree | Vertex | Degree |
|---|---|---|---|
| a | 3 | e | 3 |
| b | 2 | f | 2 |
| c | 3 | g | 2 |
| d | 3 | h | 2 |
The graph shown above is a disconnected graph as there is no path connecting vertex a to any of the vertices f or g or h. The graph has two connected components as marked H1 and H2 in the picture. There is a path between every pair of vertices belonging either to H1 or H2. However, if we add vertex c to subgraph H2 then it does remain connected. Similarly, if adding g to subgraph H1 lead it to become disconnected. There is a simple cycle between vertices f, g, h. The subgraph H1 has many simple cycles. One example for a cycle of length 5 is a, c, d, e, b.
We have already seen an example of a bipartite graph in the previous blog. An example representing the relationship between banks and their clients is given there. The banks are independent entities. A client may choose to have accounts in multiple banks. But no client is connected to another.