Graph Representations & Isomorphism: Matrices, Lists, and Structural Equivalence

1. Graph Representations

Graphs can be represented in multiple ways, each with distinct advantages for computation, storage, and analysis.

1.1 Adjacency Matrix

Definition: A square matrix $A$ of size $n\times n$ (for $n$ vertices) where:

• $A[i][j]=1$ if there is an edge from vertex $i$ to $j$,
• $A[i][j]=0$ otherwise.

For weighted graphs, $A[i][j]$ stores the edge weight.

How it works

• Undirected graph: Symmetric matrix ($A[i][j]=A[j][i]$).
• Directed graph: Asymmetric matrix.
• Self-loops: $A[i][i]=1$ (or weight if weighted).

Example

Consider an undirected graph with vertices $\{A,B,C\}$ and edges $(A,B),(B,C)$:

   A  B  C
A [0,1,0]
B [1,0,1]
C [0,1,0]

Advantages & Disadvantages

Applications

• Used in pathfinding algorithms (e.g., Floyd-Warshall).
• Graph multiplication for transitive closure.

---

1.2 Adjacency List

Definition: A list of linked lists (or arrays) where each vertex $v$ has a list of adjacent vertices.

How it works

• For each vertex, store its neighbors.
• Undirected graph: Each edge appears twice (once for each direction).
• Directed graph: Only store outgoing edges.

Example

For the same graph $\{A,B,C\}$ with edges $(A,B),(B,C)$:

A → [B]
B → [A, C]
C → [B]

Advantages & Disadvantages

Applications

• Breadth-First Search (BFS) and Depth-First Search (DFS).
• Kruskal’s/Prim’s algorithms for MST.

---

1.3 Incidence Matrix

Definition: A matrix $M$ of size $m\times n$ (for $m$ edges and $n$ vertices) where:

• $M[i][j]=1$ if edge $i$ is incident to vertex $j$,
• $M[i][j]=0$ otherwise.

Example

For edges $e_1=(A,B),e_2=(B,C)$:

   A  B  C
e1 [1,1,0]
e2 [0,1,1]

Advantages & Disadvantages

Applications

• Network flow problems.
• Bipartite graph matching.

---

1.4 Comparison Table

---

2. Graph Isomorphism

Two graphs $G_1$ and $G_2$ are isomorphic if there exists a bijection (one-to-one correspondence) between their vertex sets that preserves adjacency.

2.1 Necessary Conditions for Isomorphism

Before checking isomorphism, verify these necessary (but not sufficient) conditions:

1. Same number of vertices and edges.
2. Same degree sequence (multiset of vertex degrees).
3. Same connectivity (both connected/disconnected similarly).
4. Same number of cycles of each length.

Example

• Graph $G_1$: Vertices $\{A,B,C\}$, edges $(A,B),(B,C)$.
• Graph $G_2$: Vertices $\{1,2,3\}$, edges $(1,2),(2,3)$.
• Isomorphic because degree sequences match ($1,2,1$).

---

2.2 Checking Isomorphism

1. Relabel vertices to match degree sequences.
2. Compare adjacency:
   • If two vertices are adjacent in $G_1$, their images must be adjacent in $G_2$.
3. Use backtracking for small graphs.

Algorithm Steps

1. Sort vertices by degree.
2. Try all possible mappings of vertices.
3. Verify adjacency preservation.

Example (Non-Isomorphic Graphs)

• $G_1$: $\{A,B,C\}$ with edges $(A,B),(A,C)$ (star graph).
• $G_2$: $\{1,2,3\}$ with edges $(1,2),(2,3)$ (path graph).
• Not isomorphic because degree sequences differ ($2,1,1$ vs. $1,2,1$).

---

2.3 Applications of Isomorphism

• Chemistry: Molecule structure comparison.
• Computer Vision: Shape recognition.
• Database Theory: Schema matching.
• Cryptography: Pattern recognition in graphs.

---

3. Worked Examples

Example 1: Adjacency Matrix Conversion

Graph: Vertices $\{P,Q,R\}$, edges $(P,Q),(Q,R)$. Adjacency Matrix:

   P  Q  R
P [0,1,0]
Q [1,0,1]
R [0,1,0]

Example 2: Isomorphism Check

Graph $G_1$: $\{A,B,C,D\}$, edges $(A,B),(A,C),(A,D)$ (star). Graph $G_2$: $\{1,2,3,4\}$, edges $(1,2),(1,3),(1,4)$ (star). Conclusion: Isomorphic (same degree sequence $3,1,1,1$).

Example 3: Non-Isomorphic Graphs

Graph $G_1$: $\{A,B,C\}$, edges $(A,B),(B,C),(C,A)$ (triangle). Graph $G_2$: $\{1,2,3\}$, edges $(1,2),(2,3)$ (path). Conclusion: Not isomorphic (different degree sequences $2,2,2$ vs. $1,2,1$).

---

4. Common Mistakes & Clarifications

1. Adjacency Matrix for Directed Graphs:

   • $A[i][j]=1$ means edge from $i$ to $j$.
   • For undirected graphs, the matrix is symmetric.

2. Degree Sequence Mismatch:

   • If two graphs have different degree sequences, they cannot be isomorphic.

3. Connectivity Matters:

   • Two disconnected graphs with the same degree sequence may not be isomorphic if their components differ.

4. Isomorphism ≠ Homeomorphism:

   • Isomorphism preserves adjacency; homeomorphism allows edge subdivisions.

---

Exam Tip

What to Expect in TU Exams

1. Graph Representation Questions (3-5 marks):

   • Convert a given graph to adjacency matrix/list.
   • Identify sparse vs. dense graphs and choose the best representation.
   • Example: "Represent the following graph using an adjacency list."

2. Isomorphism Problems (5-7 marks):

   • Step 1: Check necessary conditions (degree sequence, edge count).
   • Step 2: Attempt a vertex mapping and verify adjacency.
   • Step 3: If stuck, argue why they are not isomorphic based on conditions.
   • Example: "Prove whether the following two graphs are isomorphic."

3. Short Answer Questions (2 marks each):

   • Define adjacency matrix, incidence matrix, or graph isomorphism.
   • State necessary conditions for isomorphism.
   • Example: "List two necessary conditions for two graphs to be isomorphic."

4. Applications (2-3 marks):

   • Explain where adjacency lists are preferred over matrices.
   • Give an example of graph isomorphism in real life (e.g., chemistry).

How to Score Full Marks

• For representations:
  • Clearly label rows/columns in matrices.
  • List vertices in consistent order (alphabetical/numerical).
• For isomorphism:
  • Always check degree sequences first (quick elimination).
  • If isomorphic, explicitly state the mapping (e.g., $A\to 1,B\to 2$).
  • If not, provide a counterexample (e.g., "Vertex A has degree 3 in $G_1$ but no vertex in $G_2$ has degree 3").
• Use diagrams if allowed (even simple sketches help).

Past Exam Patterns

• 2078: Adjacency matrix conversion + isomorphism proof.
• 2079: Compare adjacency list vs. matrix for a given graph.
• 2080: Necessary conditions for isomorphism + example.

---