Back to Subject

Practice MCQ

Unit 4 - Notes

MTH401

Unit 4: Graphs theory I

1. Graph Terminologies

Basic Definitions

A Graph $G$ is defined as an ordered pair $G = (V, E)$ , where:

$V$ is a non-empty set of elements called vertices (or nodes).
$E$ is a set of elements called edges (or arcs). Each edge connects two vertices.

Directed vs. Undirected

Undirected Graph: Edges are unordered pairs $\{u, v\}$ . The edge connects $u$ and $v$ both ways.
Directed Graph (Digraph): Edges are ordered pairs . The edge goes from to .
- $u$ is the initial vertex.
- $v$ is the terminal vertex.

Vertex and Edge Relationships

Adjacency: Two vertices are adjacent (or neighbors) if they are connected by an edge.
Incidence: An edge is incident to the vertices it connects.
Loop: An edge that connects a vertex to itself ( $e = \{u, u\}$ ).
Parallel Edges (Multiple Edges): Two or more distinct edges that connect the same pair of vertices.
Simple Graph: A graph with no loops and no parallel edges.
Multigraph: A graph that allows parallel edges.
Pseudograph: A graph that allows both loops and parallel edges.

Degrees of Vertices

Degree (Undirected): The number of edges incident to vertex , denoted .
- Note: A loop contributes 2 to the degree.
Isolated Vertex: A vertex with $\deg(v) = 0$ .
Pendant Vertex: A vertex with $\deg(v) = 1$ .

The Handshaking Theorem:
In an undirected graph with $m$ edges, the sum of degrees of all vertices is twice the number of edges.

\sum_{v \in V} \deg(v) = 2|E|

Corollary: An undirected graph has an even number of vertices of odd degree.

Degrees in Directed Graphs

In-degree ( $\deg^-(v)$ ): Number of edges coming into $v$ .
Out-degree ( $\deg^+(v)$ ): Number of edges going out of $v$ .
Theorem: $\sum \deg^-(v) = \sum \deg^+(v) = |E|$ .

2. Special Types of Graphs

Complete Graph ( $K_n$ )

A simple graph containing exactly one edge between each pair of distinct vertices.

Vertices: $n$
Edges: $n(n-1)/2$
Regularity: Every vertex has degree $n-1$ .

Cycle Graph ( $C_n$ )

A graph consisting of vertices $v_1, v_2, ..., v_n$ and edges $\{v_1, v_2\}, \{v_2, v_3\}, ..., \{v_{n-1}, v_n\}, \{v_n, v_1\}$ .

Requires $n \geq 3$ .
Every vertex has degree 2.

Wheel Graph ( $W_n$ )

Constructed by taking a cycle graph $C_n$ and adding an additional vertex (hub) connected to all $n$ vertices of the cycle.

Vertices: $n + 1$
Edges: $2n$
(Note: Some texts define the size differently; usually $W_n$ denotes a wheel with $n$ rim vertices).

n-Cube (Hypercube, $Q_n$ )

A graph with vertices representing bit strings of length $n$ . Two vertices are adjacent if their bit strings differ by exactly one bit.

Vertices: $2^n$
Edges: $n \cdot 2^{n-1}$
Degree: Every vertex has degree $n$ .

Bipartite Graph

A graph $G$ is bipartite if its vertex set $V$ can be partitioned into two disjoint sets $V_1$ and $V_2$ such that every edge connects a vertex in $V_1$ to one in $V_2$ .

No edge connects two vertices within the same partition.
Theorem: A simple graph is bipartite if and only if it contains no odd length simple cycles.

Complete Bipartite Graph ( $K_{m,n}$ )

A bipartite graph where every vertex in set $V_1$ (size $m$ ) is connected to every vertex in set $V_2$ (size $n$ ).

Edges: $m \times n$
Degrees: Vertices in $V_1$ have degree $n$ ; vertices in $V_2$ have degree $m$ .

Regular Graph

A simple graph where every vertex has the same degree $k$ . It is called a $k$ -regular graph.

$K_n$ is $(n-1)$ -regular.
$C_n$ is 2-regular.

3. Representing Graphs

Adjacency Matrix

Let $G = (V, E)$ be a simple graph with $n$ vertices labeled $v_1, v_2, ..., v_n$ . The adjacency matrix $A$ is an $n \times n$ matrix where:

A_{ij} = \begin{cases} 1 & \text{if } \{v_i, v_j\} \in E \\ 0 & \text{otherwise} \end{cases}

Properties:
- Symmetric for undirected graphs ( $A_{ij} = A_{ji}$ ).
- Sum of a row $i$ equals $\deg(v_i)$ .
- For directed graphs, $A_{ij} = 1$ if there is an edge from $v_i$ to $v_j$ . It is not necessarily symmetric.
- Powers of the matrix ( $A^k$ ) reveal connectivity: $(A^k)_{ij}$ is the number of walks of length $k$ from $v_i$ to $v_j$ .

Incidence Matrix

Let $G = (V, E)$ be an undirected graph with $n$ vertices ( $v_1...v_n$ ) and $m$ edges ( $e_1...e_m$ ). The incidence matrix $M$ is an $n \times m$ matrix where:

M_{ij} = \begin{cases} 1 & \text{if edge } e_j \text{ is incident with } v_i \\ 0 & \text{otherwise} \end{cases}

Properties:
- Every column sums to 2 (since every edge connects two vertices).
- Row sums give the degree of the vertex.

4. Graph Isomorphism

Two simple graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic if there exists a one-to-one and onto function (bijection) $f: V_1 \to V_2$ such that:

\{u, v\} \in E_1 \iff \{f(u), f(v)\} \in E_2

Checking for Isomorphism

It is computationally difficult to prove isomorphism for large graphs, but easy to prove non-isomorphism by checking invariants (properties preserved under isomorphism).

Necessary Conditions (Invariants):
If $G_1$ and $G_2$ are isomorphic, they must have the:

Same number of vertices ( $|V_1| = |V_2|$ ).
Same number of edges ( $|E_1| = |E_2|$ ).
Same degree sequence (list of vertex degrees sorted in non-decreasing order).
Same connectivity/cycle structures (e.g., if $G_1$ has a cycle of length 3, $G_2$ must also).

Note: Satisfying these conditions does not guarantee isomorphism, but failing any of them guarantees non-isomorphism.

5. Path and Connectivity

Definitions of Traversal

Walk: A sequence of alternating vertices and edges. Repeated edges and vertices allowed.
Trail: A walk with no repeated edges.
Path: A walk with no repeated vertices (implies no repeated edges).
Cycle (Circuit): A path that starts and ends at the same vertex ( $v_0 = v_n$ ) with length $\ge 1$ .

Connectivity in Undirected Graphs

Connected Graph: There is a path between every pair of distinct vertices.
Connected Component: A maximal connected subgraph.
Cut Vertex (Articulation Point): A vertex whose removal increases the number of connected components.
Cut Edge (Bridge): An edge whose removal increases the number of connected components.

Connectivity in Directed Graphs

Strongly Connected: For every pair of vertices $u, v$ , there is a directed path from $u$ to $v$ AND from $v$ to $u$ .
Weakly Connected: The underlying undirected graph (ignoring edge directions) is connected.

6. Dijkstra’s Algorithm

Problem: Find the shortest path from a source vertex ( $a$ ) to all other vertices in a weighted graph.
Prerequisite: Edge weights must be non-negative.

Terminology

$w(u, v)$ : Weight of edge $(u, v)$ .
$L(v)$ : Label representing the tentative shortest distance from source to $v$ .
$S$ : Set of visited (permanently labeled) vertices.

Algorithm Steps

Initialization:
- Set $L(source) = 0$ .
- Set $L(v) = \infty$ for all other $v$ .
- Set $S = \emptyset$ .
Selection:
- Choose a vertex $u$ not in $S$ with the minimum $L(u)$ .
- Add $u$ to $S$ .
Relaxation:
- For every neighbor of that is not in :
  - New Distance $= L(u) + w(u, v)$ .
  - If New Distance $< L(v)$ , update $L(v) =$ New Distance.
Termination:
- Repeat steps 2 and 3 until all vertices are in $S$ (or destination is reached).

Pseudocode

TEXT

function Dijkstra(Graph, source):
    create vertex set Q

    for each vertex v in Graph:
        dist[v] ← INFINITY
        prev[v] ← UNDEFINED
        add v to Q
      
    dist[source] ← 0
      
    while Q is not empty:
        u ← vertex in Q with min dist[u]
        remove u from Q
          
        for each neighbor v of u:
            alt ← dist[u] + weight(u, v)
            if alt < dist[v]:
                dist[v] ← alt
                prev[v] ← u

    return dist[], prev[]

Complexity

Using an array: $O(|V|^2)$ .
Using a Min-Priority Queue (Binary Heap): $O(|E| \log |V|)$ .