Types of Graphs & Special Graphs: Connected, Bipartite, Isomorphic, Directed, Weighted

TAKEAWAYS:

• A connected graph has a path between every pair of vertices; otherwise, it is disconnected.
• Bipartite graphs partition vertices into two sets with no edges within a set; odd cycles make them impossible.
• Graph isomorphism maps vertices/edges preserving adjacency; check degree sequences and structures.
• Directed graphs use source/sink vertices and adjacency matrices with 0/1 entries for edges.
• Weighted graphs model real costs (e.g., distances, delays) and require algorithms like Dijkstra’s.
• Special graphs (trees, cycles) have unique properties: trees are acyclic and connected; cycles have no leaves.

1. Connected Graphs

A graph $G=(V,E)$ is connected if there is a path between every pair of vertices $u,v\in V$. Otherwise, it is disconnected.

Key Properties

• A graph with $n$ vertices is connected if it has at least $n-1$ edges (minimum spanning tree).
• Example: The internet (NTC/Ncell networks) is a connected graph where routers (vertices) are linked by fiber cables (edges).

Worked Example

Question: Is the following graph connected?

A -- B -- C
 \    /
   D

Solution:

• Paths: A→B→C, A→D→B, B→D→C, etc. All vertices are reachable.
• Answer: Yes, it is connected.

Visual

Caption: Connected graph with 4 vertices and 4 edges.

2. Bipartite Graphs

A graph $G$ is bipartite if its vertices can be divided into two disjoint sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$.

Key Properties

• No odd-length cycles (e.g., triangles).
• Proof: Assume a bipartite graph has an odd cycle. Partition vertices into $U$ and $V$. Alternating edges must switch sets, but an odd cycle would require a vertex to belong to both sets, a contradiction.

Worked Example

Question: Prove that a graph with an odd cycle (e.g., triangle) cannot be bipartite. Solution:

• Suppose $G$ is bipartite with sets $U$ and $V$.
• Traverse an odd cycle $u_1\to u_2\to \cdots \to u_k\to u_1$.
• Each edge alternates sets: $u_1\in U$, $u_2\in V$, $u_3\in U$, etc.
• After $k$ steps (odd), $u_k$ must be in $U$ (since $k$ is odd), but $u_1\in U$ and $u_k$ is adjacent to $u_1$, requiring $u_k\in V$. Contradiction.

Visual

Caption: Bipartite graph (left) vs. non-bipartite graph with a triangle (right).

3. Graph Isomorphism

Two graphs $G$ and $H$ are isomorphic if there exists a bijection $f:V(G)\to V(H)$ preserving adjacency.

Key Steps to Check Isomorphism

1. Compare degree sequences (must match).
2. Check for isomorphic subgraphs (e.g., triangles, paths).
3. Use graph coloring or other invariants.

Worked Example

Question: Are $G$ and $H$ isomorphic?

• $G$: Vertices $\{a,b,c,d\}$, edges $\{(a,b),(b,c),(c,d),(d,a)\}$.
• $H$: Vertices $\{1,2,3,4\}$, edges $\{(1,2),(2,3),(3,4),(4,1)\}$.

Solution:

• Both are 4-cycles (same degree sequence: $2,2,2,2$).
• A bijection $f(a)=1,f(b)=2,f(c)=3,f(d)=4$ preserves edges.
• Answer: Yes, they are isomorphic.

Visual

graph TD
    subgraph G["Graph G"]
        A["a"] --> B["b"]
        B --> C["c"]
        C --> D["d"]
        D --> A
    end
    subgraph H["Graph H"]
        1["1"] --> 2["2"]
        2 --> 3["3"]
        3 --> 4["4"]
        4 --> 1
    end

Caption: Isomorphic 4-cycles $G$ and $H$.

4. Directed Graphs

A directed graph (digraph) has edges with ordered pairs $(u,v)$, representing direction.

Key Terms

• Source vertex: No incoming edges (e.g., start of a path).
• Sink vertex: No outgoing edges (e.g., end of a path).
• Adjacency matrix: $A[i][j]=1$ if edge $(i,j)$ exists; else $0$.

Worked Example

Question: Given adjacency matrix for $G$ with vertices $\{v_1,v_2,v_3,v_4\}$:

0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

Find degrees and total edges. Solution:

• Degree of $v_1$: Outgoing edges to $v_2,v_3$ → degree 2.
• Degree of $v_2$: Outgoing edges to $v_1,v_3,v_4$ → degree 3.
• Similarly, degrees: $2,3,3,2$.
• Total edges: Sum of all 1s in matrix = 8.

Visual

Caption: Directed graph with adjacency matrix above.

5. Weighted Graphs

A weighted graph assigns a value (e.g., cost, distance) to each edge.

Key Applications

• Shortest path: Dijkstra’s algorithm (used in GPS navigation like Pathao).
• Minimum spanning tree: Kruskal’s/Prim’s (used in NTC’s fiber network optimization).

Worked Example

Question: Find the shortest path from $A$ to $D$ in this weighted graph:

A --3--> B --1--> C
 \       / \      /
  2     4   5    2
   \   /     \  /
     D --2--> E

Solution:

• Paths:
  • $A\to B\to C\to E$: $3+1+2=6$.
  • $A\to D\to E$: $2+2=4$.
• Shortest path: $A\to D\to E$ (weight 4).

Visual

graph TD
    A["A"] -->|"3"| B["B"]
    B -->|"1"| C["C"]
    A -->|"2"| D["D"]
    D -->|"2"| E["E"]
    B -->|"4"| D
    C -->|"5"| D
    C -->|"2"| E

Caption: Weighted graph for shortest-path example.

6. Special Graphs

(a) Trees

• Definition: Connected, acyclic graph with $n-1$ edges.
• Properties:
  • No cycles, exactly one path between any two vertices.
  • Example: File system directories (each folder is a node; subfolders are children).

(b) Cycles

• Definition: Graph where every vertex has degree 2 (single cycle).
• Example: Round-robin scheduling in Pathao’s driver assignments.

(c) Bipartite Graphs in Real Life

• Example: Daraz’s order processing:
  • Set U: Customers (orders).
  • Set V: Products.
  • Edges: "Customer buys Product."
  • No odd cycles because a customer cannot buy the same product in a loop (no repeated purchases in a single cycle).

Visual: Tree vs. Graph with Cycle

Caption: Tree (left) vs. graph with a cycle (right).

In the Real World

1. eSewa/Khalti Payment Networks:

   • Idea: Directed graphs model transaction flows (e.g., user → merchant → bank).
   • How: Source vertices are users; sink vertices are banks. Edges represent payment directions.

2. NEPSE Stock Market:

   • Idea: Weighted graphs represent stock correlations (edges = volatility weights).
   • How: Shortest paths find low-risk portfolios.

3. Pathao’s Driver Assignment:

   • Idea: Bipartite graphs assign drivers to rides (drivers in one set, rides in another).
   • How: No odd cycles ensure fair, conflict-free assignments.

4. NTC’s Fiber Optic Network:

   • Idea: Minimum spanning trees optimize cable routes (minimize cost while connecting all cities).

Exam Tip

• Connected Graphs: Always check for paths between all vertices. Draw small examples to verify.
• Bipartite Graphs: Look for odd cycles to disprove bipartiteness. Use 2-coloring (like a chessboard).
• Isomorphism: Compare degree sequences and subgraph structures. If they match, graphs are likely isomorphic.
• Directed Graphs: For adjacency matrices, count 1s to find degrees and edges.
• Weighted Graphs: Focus on shortest-path algorithms (Dijkstra’s) or MST (Kruskal’s/Prim’s).
• Special Graphs: Trees have $n-1$ edges; cycles have all degrees = 2. Relate to real-world examples (e.g., file systems, scheduling).

Common Pitfalls:

• Forgetting to check for odd cycles in bipartite graphs.
• Misinterpreting adjacency matrices (rows/columns may represent sources/targets).
• Overlooking degree sequences in isomorphism checks.

Final Note: Practice drawing graphs and labeling vertices/edges clearly. Use small examples (3–5 vertices) to test definitions. For proofs, assume the opposite (e.g., "suppose it’s bipartite") and derive a contradiction.