Graphs or Networks Chapter 2
For chapter 1 please click here.
In this chapter we will discuss about some common terminologies associated with graphs.
Let a graph or a network be denoted by “G”.
Subgraph: A graph “S” is called a subgraph of “G” if and only if vertices and edges of “S” are subset of vertices and edges of “G”.
Adjacent nodes: If two vertices in a graph are connected with each other, the pair is called adjacent nodes. Example: (A,B),(C,D) etc.
Parallel Edges: If two edges have same start and endpoint, the pair is called parallel edges.
Simple graph: If a graph has no parallel edges or loops then the graph is regarded as a simple graph. Graph 1 is not a simple graph as it has loops like BCAB. Additionally, Graph 1 has a single vertex loop at vertex E.
Weighted Graph: If edges in the graph contains weights to represent certain entity such cost, flow rate, distance etc., then the graph is regarded as weighted graph. Generally denoted as (u, v, w) where u is starting node, v is the end node and w is the weight.
Complete Graph: If in a graph each pair of vertices are adjacent to each other or each pair of vertices has an edge connecting them, then the graph is a complete graph. Number of edges in a complete graph can be given by ⁿC₂, where n is number of vertices in the graph.
Degree of Vertex: The number of edges incident on the vertex is the degree of the vertex. It is denoted as deg(v) or d(v). Note:- each edge in a graph contribute to 2 degrees in total graph (undirected graph). So d(E) in Graph 1 is 2. If graph as all the vertices with degree k then that graph is called k-regular graph.
Walk: An alternating sequence of vertices from set V and edges from set E which begins and ends with vertices is a walk. Closed walk when the start and the end vertex are same.
- Trail: A walk whose all edges are distinct.
- Path: A walk whose edges and vertices are distinct.
- Cycle: A walk with start and end vertex are same.
- Connected: A graph where all the vertices can be covered in a single path.
- Eulerian trail: A trail in a graph which visits all the edges in the graph once.
- Hamiltonian Cycle: A cycle which contains all the vertices in the graph. The graph is called a Hamiltonian Graph.
Diameter of a graph: It is the maximum of shortest path between two vertices of the graph. max(dist(v, u)) where max is maximum function and dist() is the shortest path.
Graph Isomorphism: If Graph1 and Graph2 are two graphs, if there exist a function I i.e. I : v →v¹ with (u, v) element of E to (u¹, v¹) element of E¹ then I is called Isomorphism and Graph1 and Graph2 are isomorphic graphs.
- Trees: It is a acyclic (does not contain any cycle) undirected graph.
- Out Tree: If a tree has a specified root node and all the edges point away from the root node then the tree is regarded as a out tree or arborescence.
- In Tree: If a tree has a specified root node and all the edges point towards the root node then the tree is regarded as a in tree or anti arborescence.
- Directed Acyclic Graph (DAG): As the name suggested a graph with directed edges with no cycles is a DAG.
- Bipartite Graph: A graph that can be subdivided into two parts such that the edges in E join a vertex in part 1 and a vertex in part 2, such graph is a Bipartite Graph.
Representation of Graphs: Since graphs are not a primitive data structure. It is represented as following:
- Adjacency Matrix: It is a matrix whose (i, j) position represents an edge running from i to j node in the graph and value at the position refers to edge weight.
- It is space efficient for dense graphs and complete graphs.
- To lookup edge weight time complexity O(1).
- Simplest Representation of graph.
- requires O(v²) space. So it is not space efficient when sparse graphs are concerned.
- Iterating over all the edges has complexity O(v²).
- Adjacency List: It represents the graph as map from nodes to list of edges.
- Space efficient for sparse graph.
- Iterating over edges is efficient.
- Less space efficient for dense graphs
- Edge weight look up O(E)
- Edge List: It is unordered list of edge triplets.
- efficient for sparse graphs
- all edge iteration is simple
- edge weight lookup is O(E)
- not efficient for dense graphs.
I hope this article enriched your knowledge about graphs.