Comprehensive Study Notes on Graph Theory, Traversal Algorithms, Bipartiteness, and Topological Sorting

Foundations of Graph Theory and Graph Representations

  • Formal Definition of a Graph:

    • A graph is a non-linear data structure denoted as G=(V,E)G = (V, E).

    • VV represents a finite, non-empty set of vertices (also called nodes).

    • EE represents a set of edges, where each edge corresponds to a connection between a pair of vertices (u,v)(u, v) such that u,v∈Vu, v \in V.

  • Core Graph Terminology:

    • Adjacent / Neighbours: Two vertices uu and vv are adjacent (or neighbours) if they are directly connected by an edge e=(u,v)e = (u, v).

    • Incident: An edge e=(u,v)e = (u, v) is said to be incident to both vertex uu and vertex vv.

    • Degree of a Vertex (deg⁡(v)\deg(v)): The total number of edges connected to a vertex vv.

    • Directed vs. Undirected Graphs:

    • In an undirected graph, edges are bidirectional unordered pairs; the edge (u,v)(u, v) is identical to (v,u)(v, u).

    • In a directed graph (digraph), edges are ordered pairs with direction (arrows). Each vertex possesses two distinct degree metrics:

      • In-degree: The number of incoming edges directed into the vertex.

      • Out-degree: The number of outgoing edges directed away from the vertex.

    • Path: A path is an alternating sequence of vertices P=v1,v2,…,vkP = v_1, v_2, \dots, v_k such that each consecutive pair (vi,vi+1)(v_i, v_{i+1}) is joined by an edge e∈Ee \in E.

    • Distance: The distance between two vertices uu and vv is defined as the minimum number of edges on any path connecting uu to vv.

    • Cycle: A path in which the starting and ending vertices coincide (v1=vkv_1 = v_k with k>2k > 2) and the first k−1k-1 vertices are distinct.

    • Loop (Self-loop): An edge that connects a vertex directly to itself.

    • Connected Graph: An undirected graph is connected if there exists a valid path between every pair of vertices uu and vv.

    • Connected Components: Maximal connected subgraphs within a disconnected graph.

    • Tree: An undirected graph that is connected and contains no cycles (acyclic).

    • Weighted Graph: A graph in which each edge e∈Ee \in E has an associated numerical value (weight or cost).

Undirected graph showing vertex B connected to neighbors A, D, and E with degree 3Directed graph with vertices P, Q, R, S
  • Linked Lists and Trees as Restricted Directed Acyclic Graphs (DAGs):

    • A binary tree is a specialized graph characterized by:

    • Being an unweighted, directed acyclic graph (DAG).

    • Having an in-degree of at most 11 for every node.

    • Having an out-degree of at most 22 for every node.

    • Having a unique designated root node with in-degree 00, from which exactly one directed path leads to every other node.

    • A singly linked list is a specialized graph characterized by:

    • Being an unweighted DAG.

    • Having an in-degree of at most 11 and an out-degree of at most 11 for all nodes.

Binary tree structure represented as a directed acyclic graphLinked list represented as a linear directed acyclic graph
  • Real-World Graph Modeling:

    • Web Pages and Hyperlinks: Web pages represent vertices; directed hyperlinks between pages represent directed edges.

    • Program Call Graphs: Methods/functions represent vertices; function calls represent directed edges.

    • Road Networks: Intersections/locations represent vertices; streets represent edges (undirected or directed based on one-way streets).

    • Airline Flight Systems: Airports represent vertices; non-stop flights represent edges, often weighted by distance, duration, or ticket price.

    • Social Networks: Individual user profiles represent vertices; mutual friendships represent undirected edges.

    • Academic Prerequisites: Courses represent vertices; prerequisite requirements represent directed edges, forming a DAG.

    • Mazes: Decision junctions represent vertices; accessible corridors represent edges.

    • Internet Backbone: Individual routers or IP addresses represent vertices; physical optical/cable data lines represent edges.

Weighted flight network between airports displaying route costs
  • Path Optimization Objectives:

    • Path Existence: Determining if any valid path connects vertex uu to vertex vv.

    • Hop-Count Minimization: Finding a path that minimizes the total number of intermediate edges (unweighted shortest path).

    • Cost Minimization: Finding a path that minimizes the cumulative sum of edge weights (weighted shortest path).

  • Graph Storage Representations:

    • Adjacency Matrix:

    • A 2D boolean or integer array AA of size ∣V∣×∣V∣|V| \times |V|, where vertices are indexed from 11 to NN.

    • An entry A[i][j]=1A[i][j] = 1 if an edge (vi,vj)∈E(v_i, v_j) \in E; otherwise, A[i][j]=0A[i][j] = 0.

    • For undirected graphs without self-loops, the adjacency matrix is symmetric along its main diagonal (A[i][j]=A[j][i]A[i][j] = A[j][i]), and all diagonal entries are 00.

    • Space Complexity: O(∣V∣2)O(|V|^2).

    • Edge Lookup / Insertion / Deletion Time: O(1)O(1).

    • Finding All Neighbours of Vertex vv: O(∣V∣)O(|V|), as the entire row must be scanned.

    • Adjacency List:

    • An array or map of linked lists/dynamic arrays of size ∣V∣|V|.

    • Each vertex index vv points to a list containing all vertices directly adjacent to vv.

    • Space Complexity: O(∣V∣+∣E∣)O(|V| + |E|) for directed graphs; O(∣V∣+2∣E∣)O(|V| + 2|E|) which simplifies to O(∣V∣+∣E∣)O(|V| + |E|) for undirected graphs.

    • Edge Lookup Time: O(deg⁡(v))O(\deg(v)).

    • Finding All Neighbours of Vertex vv: O(deg⁡(v))O(\deg(v)).

    • Trade-Off Summary:

    • The adjacency matrix is preferred for dense graphs where ∣E∣≈∣V∣2|E| \approx |V|^2, or when instant O(1)O(1) edge-existence queries are essential.

    • The adjacency list is vastly superior for sparse graphs where ∣E∣≪∣V∣2|E| \ll |V|^2, saving substantial memory and allowing efficient neighbour iteration.

Graph Traversal Fundamentals

  • The Objective of Traversal:

    • Starting from a designated initial vertex ss, systematically visit every reachable vertex in the graph exactly once.

    • Traversal algorithms explore connected components and construct spanning forests over the graph.

  • Cycle Handling via the Visited Mark:

    • Unlike trees, graphs may contain cycles. Without preventive mechanisms, an algorithm exploring a cycle such as A→B→C→AA \rightarrow B \rightarrow C \rightarrow A would enter an infinite loop.

    • To prevent cycling, every traversal maintains a boolean array or lookup table visited[] of size ∣V∣|V|.

    • A vertex is marked as visited upon discovery; once marked, it is never processed as a new vertex again.

  • Deterministic Tie-Breaking Rule:

    • When a vertex has multiple unvisited adjacent neighbours, all canonical tracing follows strict alphabetical or ascending numerical order.

  • General Runtime Complexity Derivation:

    • For both Breadth-First Search (BFS) and Depth-First Search (DFS), using an adjacency list yields a time complexity of:     O(∣V∣+∣E∣)O(|V| + |E|)

    • Derivation:

    • Each vertex is placed into the tracking structure (queue or stack) and removed at most once: O(∣V∣)O(|V|).

    • When processing a vertex, all its incident edges are inspected. Across the entire traversal, every directed edge is examined once; every undirected edge is examined twice (once from each endpoint).

    • Sum of degrees formula (Handshaking Lemma):       ∑v∈Vdeg⁡(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|

    • Therefore, the total edge exploration operations take O(∣E∣)O(|E|).

    • Combined time equals O(∣V∣+∣E∣)O(|V| + |E|).

    • If an adjacency matrix is used instead, scanning all potential neighbours for every vertex requires checking an entire row of length ∣V∣|V|, resulting in a time complexity of:     O(∣V∣2)O(|V|^2)

Breadth-First Search (BFS)

  • Core Philosophy:

    • Explores the graph layer by layer, expanding outward like ripples in water.

    • First processes the root/start node (Level 00), then all immediate neighbours of the start node (Level 11), then all neighbours of Level 11 nodes (Level 22), and so forth.

    • Explores paths in parallel breadth-wise before advancing to deeper levels.

  • Queue Mechanism (FIFO):

    • Operates using a First-In, First-Out (FIFO) Queue data structure.

    • ENQUEUE(x): Inserts element xx at the rear.

    • DEQUEUE(): Removes and returns the element at the front.

    • Vertices discovered earlier are dequeued earlier, enforcing strict level-by-level processing.

    • Critical Invariant: A vertex must be marked as visited immediately upon being enqueued (not when dequeued). This prevents the same vertex from being inserted into the queue multiple times by different neighbours.

  • Queue-Based BFS Algorithm: ```text BFS(G, s): for each vertex u in V: visited[u] = false dist[u] = infinity parent[u] = null

    visited[s] = true dist[s] = 0 Q.enqueue(s)

    while Q is not empty: v = Q.dequeue() process(v) for each neighbour u of v (in alphabetical order): if visited[u] == false: visited[u] = true dist[u] = dist[v] + 1 parent[u] = v Q.enqueue(u)   ```

  • Comprehensive Step-by-Step BFS Trace on a 7-Vertex Graph:

    • Graph topology consists of vertices {A,B,C,D,E,F,G}\{A, B, C, D, E, F, G\} with edges: (A,B),(A,C),(B,D),(B,E),(C,E),(C,F),(E,G),(F,G)(A, B), (A, C), (B, D), (B, E), (C, E), (C, F), (E, G), (F, G).

    • Start vertex is AA.

Graph topology of 7 vertices A through G used for BFS traversal
  • Step 0 (Initialization):

    • Mark AA visited. Distance d(A)=0d(A) = 0.

    • Queue = [ A ] (front = rear = AA).

    • Output = [].

  • Step 1 (Process A):

    • Dequeue AA. Output: A.

    • Inspect neighbours of AA in alphabetical order: B,CB, C.

    • BB is unvisited: mark visited, set d(B)=1d(B) = 1, enqueue BB.

    • CC is unvisited: mark visited, set d(C)=1d(C) = 1, enqueue CC.

    • Queue = [ B, C ].

    • Output = [ A ].

  • Step 2 (Process B):

    • Dequeue BB. Output: B.

    • Inspect neighbours of BB: A,D,EA, D, E.

    • AA is already visited: skip.

    • DD is unvisited: mark visited, set d(D)=2d(D) = 2, enqueue DD.

    • EE is unvisited: mark visited, set d(E)=2d(E) = 2, enqueue EE.

    • Queue = [ C, D, E ].

    • Output = [ A, B ].

  • Step 3 (Process C):

    • Dequeue CC. Output: C.

    • Inspect neighbours of CC: A,E,FA, E, F.

    • AA is already visited: skip.

    • EE is already visited (currently in queue): skip.

    • FF is unvisited: mark visited, set d(F)=2d(F) = 2, enqueue FF.

    • Queue = [ D, E, F ].

    • Output = [ A, B, C ].

  • Step 4 (Process D):

    • Dequeue DD. Output: D.

    • Inspect neighbours of DD: BB.

    • BB is already visited: skip.

    • No vertices added.

    • Queue = [ E, F ].

    • Output = [ A, B, C, D ].

  • Step 5 (Process E):

    • Dequeue EE. Output: E.

    • Inspect neighbours of EE: B,C,GB, C, G.

    • BB is already visited: skip.

    • CC is already visited: skip.

    • GG is unvisited: mark visited, set d(G)=3d(G) = 3, enqueue GG.

    • Queue = [ F, G ].

    • Output = [ A, B, C, D, E ].

  • Step 6 (Process F):

    • Dequeue FF. Output: F.

    • Inspect neighbours of FF: C,GC, G.

    • CC is already visited: skip.

    • GG is already visited (currently in queue): skip.

    • No vertices added.

    • Queue = [ G ].

    • Output = [ A, B, C, D, E, F ].

  • Step 7 (Process G):

    • Dequeue GG. Output: G.

    • Inspect neighbours of GG: E,FE, F.

    • Both EE and FF are already visited: skip.

    • Queue = [ ] (empty).

    • Output = [ A, B, C, D, E, F, G ].

    • Traversal terminates.

    • BFS Tree and Shortest Path Property:

  • Levels and Parent Relationships:

    • Level 00 (d=0d = 0): AA (Parent: none)

    • Level 11 (d=1d = 1): BB (Parent: AA), CC (Parent: AA)

    • Level 22 (d=2d = 2): DD (Parent: BB), EE (Parent: BB), FF (Parent: CC)

    • Level 33 (d=3d = 3): GG (Parent: EE)

  • Shortest Path Retrieval:

    • BFS guarantees that the level number equals the minimum hop distance from the start node.

    • To reconstruct the unweighted shortest path from start node AA to target GG, follow parent pointers in reverse:       G→E→B→AG \rightarrow E \rightarrow B \rightarrow A

    • Inverting yields the optimal path: A−B−E−GA - B - E - G, requiring exactly 33 edges.

    • BFS Characteristics:

  • Time Complexity: O(∣V∣+∣E∣)O(|V| + |E|) with adjacency list; O(∣V∣2)O(|V|^2) with adjacency matrix.

  • Space Complexity: O(∣V∣)O(|V|) to maintain the queue and visited array.

  • Primary Applications:

    • Unweighted single-source shortest paths.

    • Level-order tree traversals.

    • Degrees of separation in social networks ("friends of friends").

    • Web crawlers discovering documents by hop distance.

    • Connected component identification.

    • Testing for bipartiteness / 2-colourability.

Depth-First Search (DFS)

  • Core Philosophy:

    • Explores the graph by advancing along a single path as deeply as possible until a dead end is reached.

    • Upon encountering a vertex with no unvisited neighbours, it backtracks to the most recent vertex with unexplored options.

    • Resembles exploring a maze by following a path to its conclusion before retracing steps.

  • Stack Mechanism (LIFO):

    • Operates using a Last-In, First-Out (LIFO) Stack data structure, implemented explicitly or via system call stack (recursion).

    • PUSH(x): Places element xx onto the top of the stack.

    • POP(): Removes and returns the element from the top of the stack.

    • TOP(): Inspects the current top element without removing it.

    • The stack stores the active path from the search root to the current frontier node. Backtracking corresponds directly to a POP() operation.

  • DFS Algorithms (Recursive and Iterative):

    • Recursive Implementation:text DFS_recursive(u): visited[u] = true print(u) for each neighbour v of u (in alphabetical order): if visited[v] == false: DFS_recursive(v)     

  • Iterative Implementation (Using Explicit Stack): ```text DFS_iterative(G, s): visited[s] = true print(s) S.push(s)

    while S is not empty:
        v = S.top()
        if v has an unvisited neighbour u:
            visited[u] = true
            print(u)
            S.push(u)   // advance deeper
        else:
            S.pop()     // backtrack
    

        ```

  • Comprehensive Step-by-Step DFS Trace on the 7-Vertex Graph:

    • Same graph: vertices {A,B,C,D,E,F,G}\{A, B, C, D, E, F, G\}, start at AA, alphabetical tie-breaking.

    • Step 0:

    • Visit AA, output: A.

    • Stack = [ A ] (bottom to top).

    • Step 1:

    • Top is AA. First unvisited neighbour is BB.

    • Visit BB, output: B.

    • Stack = [ A, B ].

    • Step 2:

    • Top is BB. Neighbours are AA (visited), DD (unvisited), EE (unvisited).

    • First unvisited is DD. Visit DD, output: D.

    • Stack = [ A, B, D ].

    • Step 3:

    • Top is DD. Neighbour BB is already visited.

    • Dead end reached at DD. Pop DD. Stack reverts to [ A, B ].

    • Top is now BB. Next unvisited neighbour is EE.

    • Visit EE, output: E.

    • Stack = [ A, B, E ].

    • Step 4:

    • Top is EE. Neighbours are BB (visited), CC (unvisited), GG (unvisited).

    • First unvisited is CC. Visit CC, output: C.

    • Stack = [ A, B, E, C ].

    • Step 5:

    • Top is CC. Neighbours are AA (visited), EE (visited), FF (unvisited).

    • First unvisited is FF. Visit FF, output: F.

    • Stack = [ A, B, E, C, F ].

    • Step 6:

    • Top is FF. Neighbours are CC (visited), GG (unvisited).

    • First unvisited is GG. Visit GG, output: G.

    • Stack = [ A, B, E, C, F, G ].

    • Step 7 (Backtracking Phase):

    • Top is GG. Neighbours E,FE, F are both visited. Dead end: Pop G. Stack: [ A, B, E, C, F ].

    • Top is FF. All neighbours visited. Dead end: Pop F. Stack: [ A, B, E, C ].

    • Top is CC. All neighbours visited. Dead end: Pop C. Stack: [ A, B, E ].

    • Top is EE. All neighbours visited. Dead end: Pop E. Stack: [ A, B ].

    • Top is BB. All neighbours visited. Dead end: Pop B. Stack: [ A ].

    • Top is AA. All neighbours visited. Dead end: Pop A. Stack: [ ] (empty).

    • Traversal complete.

    • Final DFS Visit Order: A,B,D,E,C,F,GA, B, D, E, C, F, G.

  • Edge Classification in DFS:

    • Tree Edges: Edges traversed forward to discover an unvisited vertex for the first time. Here: (A,B),(B,D),(B,E),(E,C),(C,F),(F,G)(A, B), (B, D), (B, E), (E, C), (C, F), (F, G).

    • Back Edges: Edges (u,v)(u, v) connecting the current vertex uu to an ancestor vv already present on the active stack. Here: (C,A)(C, A) and (G,E)(G, E).

    • Fundamental Theorem of DFS on Undirected Graphs:

    • In any DFS forest of an undirected graph GG, every edge of GG is either a tree edge or a back edge. Cross edges and forward edges cannot exist in an undirected DFS.

    • Ancestor-Descendant Relationship Theorem: If TT is a depth-first search tree of graph GG and (x,y)(x, y) is an edge in GG but not in TT, then either xx is an ancestor of yy or yy is an ancestor of xx in TT.

    • Cycle Detection: The presence of at least one back edge rigorously proves the existence of a cycle (e.g., back edge (C,A)(C, A) defines cycle A−B−E−C−AA - B - E - C - A).

Graph G used to illustrate non-tree edge ancestor-descendant relationshipsDFS tree T showing tree edges and ancestor-descendant back edges
  • DFS Characteristics:

    • Time Complexity: O(∣V∣+∣E∣)O(|V| + |E|) with adjacency list; O(∣V∣2)O(|V|^2) with adjacency matrix.

    • Space Complexity: O(∣V∣)O(|V|) in the worst-case (a linear degenerate path).

    • Primary Applications:

    • Maze solving and game backtracking.

    • Cycle detection in both directed and undirected graphs.

    • Topological sorting of DAGs.

    • Connectivity and biconnectivity analysis.

    • Finding strongly connected components (Kosaraju's and Tarjan's algorithms).

Comparative Analysis: BFS versus DFS

  • Direct Comparison Table:

Feature

Breadth-First Search (BFS)

Depth-First Search (DFS)

Full Name

Breadth-First Search

Depth-First Search

Underlying Data Structure

Queue (FIFO: First-In, First-Out)

Stack (LIFO: Last-In, First-Out) or Call Stack

Exploration Trajectory

Level by level (wide exploration)

Deep along a branch until dead end, then backtrack

Generated Spanning Tree

Short and broad (shallow height)

Long and narrow (deep branches)

Order on Example Graph

A,B,C,D,E,F,GA, B, C, D, E, F, G

A,B,D,E,C,F,GA, B, D, E, C, F, G

Shortest Path (Unweighted)

Guaranteed to find minimum hop path

Not optimal; finds arbitrary reachable path

Shortest Path (Weighted)

Not optimal in general

Not optimal in general

Time Complexity (List)

O(∣V∣+∣E∣)O(|V| + |E|)

O(∣V∣+∣E∣)O(|V| + |E|)

Time Complexity (Matrix)

O(∣V∣2)O(|V|^2)

O(∣V∣2)O(|V|^2)

Space Complexity

O(∣V∣)O(|V|) (bounded by max width of graph)

O(∣V∣)O(|V|) (bounded by max depth of recursion)

Path Reconstruction

Requires storing explicit predecessor array

Directly recorded by current stack contents

Canonical Applications

Shortest paths, peer-to-peer networks, web crawlers

Topological sorting, maze solving, cycle detection

Bipartite Graphs and 2-Colouring

  • Formal Definition:

    • A graph G=(V,E)G = (V, E) is bipartite if its vertex set VV can be partitioned into two disjoint subsets UU and VV (V=U∪VV = U \cup V and U∩V=∅U \cap V = \emptyset) such that every edge e=(u,v)∈Ee = (u, v) \in E connects a vertex in UU to a vertex in VV.

    • No edge may join two vertices belonging to the same partition subset: for all (x,y)∈E(x, y) \in E, x∈U  ⟹  y∈Vx \in U \implies y \in V.

Bipartite graph illustrating connections strictly across student and course sets
  • Equivalence to 2-Colourability:

    • A graph is 2-colourable if each vertex can be assigned one of two colours (e.g., RED and BLUE) such that no two adjacent vertices share the same colour.

    • Equivalence Statement: A graph is bipartite if and only if it is 2-colourable:     Bipartite  ⟺  2-Colourable\text{Bipartite} \iff \text{2-Colourable}

    • Group UU maps to all RED vertices; Group VV maps to all BLUE vertices.

A 4-vertex cycle 2-coloured with alternating red and blue vertices
  • The Odd-Cycle Theorem (The Golden Rule):

    • A graph is bipartite if and only if it contains no odd-length cycles.     Bipartite  ⟺  No cycle of odd length (3,5,7,… )\text{Bipartite} \iff \text{No cycle of odd length } (3, 5, 7, \dots)

    • Proof Intuition:

    • In any 2-colouring, traversing an edge forces an alternation between RED and BLUE.

    • To traverse a cycle and return to the starting vertex with its original colour, the traversal must execute an even number of colour alternations.

    • If a cycle has an odd length kk, starting at RED leads to alternating colours that require the kk-th vertex to be RED, while also being adjacent to the initial RED vertex, creating a contradiction.

    • Corollaries:

    • All Trees are Bipartite: Trees contain zero cycles; thus, they trivially contain no odd cycles and are always bipartite.

    • Even Cycles are Always Bipartite: Any simple cycle of length 2k2k (4,6,8,…4, 6, 8, \dots) can be successfully 2-coloured.

    • Triangles (K3K_3) and Complete Graphs (Kn,n≥3K_n, n \ge 3) are Never Bipartite: A triangle contains 33 edges (odd); complete graphs contain triangles.

Triangle graph with 3 edges failing 2-colouringSquare cycle graph with 4 edges successfully 2-coloured
  • BFS 2-Colouring Algorithm:

    • BFS naturally classifies vertices by distance from the root. If a graph is bipartite, all vertices at even levels must belong to one colour class, and all vertices at odd levels must belong to the other.

    • Algorithm Logic:

    1. Initialize all vertices as uncoloured.

    2. For every connected component (to handle disconnected graphs):

      • Pick an uncoloured vertex ss, assign it colour RED, and enqueue it.

      • While the queue is not empty:

        • Dequeue vertex vv.

        • For each neighbour uu of vv:

        • If uu is uncoloured: assign u=opposite(v)u = \text{opposite}(v) and enqueue uu.

        • If uu is already coloured with opposite(v)\text{opposite}(v): valid, continue.

        • If uu is already coloured with the same colour as vv: Conflict detected. Terminate immediately; the graph is not bipartite.

    3. If the queue empties with no conflicts detected across all components, the graph is bipartite.

    • Algorithm Pseudocode: ```text isBipartite(G): for each vertex u in V: colour[u] = NONE

      for each vertex s in V: if colour[s] == NONE: colour[s] = RED Q.enqueue(s)

          while Q is not empty:
              v = Q.dequeue()
              for each neighbour u of v:
                  if colour[u] == NONE:
                      colour[u] = opposite(colour[v])
                      Q.enqueue(u)
                  else if colour[u] == colour[v]:
                      return NOT_BIPARTITE
      

      return BIPARTITE     ```

    • Complexity: Identical to standard BFS: O(∣V∣+∣E∣)O(|V| + |E|) time and O(∣V∣)O(|V|) space.

  • Worked 2-Colouring Trace 1 (Bipartite Graph):

    • Graph with vertices {A,B,C,D,E,F}\{A, B, C, D, E, F\}.

    • Trace starting from AA (assign RED):

Hexagonal graph with cross-chord evaluated for bipartiteness
  • Dequeue AA (RED): Neighbours B,D,FB, D, F are uncoloured; colour all BLUE, enqueue B,D,FB, D, F.

  • Dequeue BB (BLUE): Neighbour AA is RED (valid); neighbour CC is uncoloured; colour CC RED, enqueue CC.

  • Dequeue DD (BLUE): Neighbour AA is RED (valid); neighbour CC is RED (valid); neighbour EE is uncoloured; colour EE RED, enqueue EE.

  • Dequeue FF (BLUE): Neighbour AA is RED (valid); neighbour EE is RED (valid).

  • Dequeue CC (RED): Neighbour BB is BLUE (valid); neighbour DD is BLUE (valid).

  • Dequeue EE (RED): Neighbour DD is BLUE (valid); neighbour FF is BLUE (valid).

  • Queue is empty. No conflicts occur.

  • Conclusion: Graph is bipartite.

  • Partition sets:   U={A,C,E}(RED)U = \{A, C, E\} \quad (\text{RED})   V={B,D,F}(BLUE)V = \{B, D, F\} \quad (\text{BLUE})

  • All simple cycles (A−B−C−DA-B-C-D of length 44, A−D−E−FA-D-E-F of length 44, and outer cycle of length 66) are strictly even.

Graph redrawn showing clear bipartite partition between sets U and V
  • Worked 2-Colouring Trace 2 (Non-Bipartite Odd Cycle):

    • 5-cycle graph with vertices {P,Q,R,S,T}\{P, Q, R, S, T\} forming edges (P,Q),(Q,R),(R,S),(S,T),(T,P)(P, Q), (Q, R), (R, S), (S, T), (T, P).

    • Start at PP: colour PP RED, enqueue PP.

    • Dequeue PP (RED): Enqueue QQ (BLUE) and TT (BLUE).

    • Dequeue QQ (BLUE): Neighbour PP is RED (valid); colour RR RED, enqueue RR.

    • Dequeue TT (BLUE): Neighbour PP is RED (valid); colour SS RED, enqueue SS.

    • Dequeue RR (RED): Neighbour QQ is BLUE (valid); neighbour SS is inspected.

    • SS is already coloured RED.

    • Conflict: Edge (R,S)(R, S) connects two RED vertices (colour[R]==colour[S]\text{colour}[R] == \text{colour}[S]).

    • Conclusion: Graph is not bipartite due to the presence of an odd cycle of length 55.

5-cycle graph displaying edge conflict between two red vertices R and S
  • Quick Bipartite Classification Reference:

Graph Description

Bipartite?

Theoretical Justification

Path graph with 4 vertices (P4P_4)

Yes

Trees have no cycles; paths are trees.

Cycle graph with 6 vertices (C6C_6)

Yes

Cycle length is even (66).

Cycle graph with 7 vertices (C7C_7)

No

Cycle length is odd (77).

Complete graph on 4 vertices (K4K_4)

No

Contains odd cycles (triangles K3K_3).

Any arbitrary tree

Yes

Acyclic graphs contain zero odd cycles.

Square with one diagonal added

No

The diagonal splits the square into two triangles (33-cycles).

Topological Sorting of Directed Acyclic Graphs (DAGs)

  • Formal Definition:

    • For a directed acyclic graph G=(V,E)G = (V, E), a topological sort is a linear ordering of all vertices v1,v2,…,vNv_1, v_2, \dots, v_N such that for every directed edge (vi,vj)∈E(v_i, v_j) \in E, vertex viv_i strictly precedes vertex vjv_j in the ordering.

Directed acyclic graph suitable for topological sorting
  • Prerequisites and Theoretical Properties:

    • A graph admits a topological sort if and only if it is a DAG (Directed Acyclic Graph).

    • Impossibility in Cyclic Graphs: If a graph contains a directed cycle (u→v→w→uu \rightarrow v \rightarrow w \rightarrow u), then uu must precede vv, vv must precede ww, and ww must precede uu, creating an impossible circular dependency.

    • Non-Uniqueness: A single DAG typically admits multiple valid topological sorts, each representing a valid sequential execution schedule.

DAG illustrating multiple valid linear topological orderings
  • For the DAG shown above, valid topological orders include:

    • 1,2,5,4,3,6,71, 2, 5, 4, 3, 6, 7

    • 2,1,5,4,7,3,62, 1, 5, 4, 7, 3, 6

    • 2,5,1,4,7,3,62, 5, 1, 4, 7, 3, 6

    • Algorithm 1: Naive In-Degree Elimination:

  • Compute and store the in-degree of every vertex.

  • While unvisited vertices remain:

    1. Perform a linear scan over all vertices to find a vertex rr with in-degree(r)=0\text{in-degree}(r) = 0 (a source/root).

    2. Output rr.

    3. Remove rr and all its outgoing edges (r,n)(r, n), decrementing the in-degree of each neighbour nn.

  • Complexity: Scanning for a root takes O(∣V∣)O(|V|) per step over ∣V∣|V| iterations, resulting in O(∣V∣2+∣E∣)O(|V|^2 + |E|) time.

    • Algorithm 2: Optimized In-Degree Algorithm (Kahn's Algorithm with Stack/Queue):

  • Computes all in-degrees initially in O(∣V∣+∣E∣)O(|V| + |E|).

  • Uses an auxiliary container (stack or queue) to store vertices whose in-degree is currently 00, eliminating repeated linear scans.

  • Algorithm Logic: ```text TopologicalSort(G): compute in-degree for all v in V initialize Stack S

    for each v in V:
        if in-degree[v] == 0:
            S.push(v)
    
    count = 0
    while S is not empty:
        r = S.pop()
        output(r)
        count = count + 1
    for each neighbour n of r:
        in-degree[n] = in-degree[n] - 1
        if in-degree[n] == 0:
            S.push(n)
    

    if count != |V|:
    error "Graph contains a cycle; no topological sort exists"

        ```

  • Complexity: Every vertex is pushed/popped once, and every edge is decremented once, achieving optimal O(∣V∣+∣E∣)O(|V| + |E|) runtime.

    • Topological Sorting via DFS:

  • Topological sorting can also be implemented using DFS.

  • In a DAG, a vertex finishes exploration (is popped from the recursion stack) only after all its downstream descendants have finished.

  • Therefore, recording vertices in reverse order of their DFS completion/exit times produces a valid topological sort.

Solved Traversal Problems and Exam Scenarios

  • Problem 1: Validating BFS Orders on an Undirected Graph:

    • Graph Topology: Vertices 1,2,3,4,5,6,71, 2, 3, 4, 5, 6, 7 with edges forming levels relative to start vertex 11:

    • Level 00: {1}\{1\}

    • Level 11: {2,3,4}\{2, 3, 4\}

    • Level 22: {5,6}\{5, 6\}

    • Level 33: {7}\{7\}

    • Candidate Orders Evaluated:

    • (a) 1,2,5,3,4,6,71, 2, 5, 3, 4, 6, 7

    • (b) 1,3,4,2,6,5,71, 3, 4, 2, 6, 5, 7

    • (c) 1,4,2,3,5,6,71, 4, 2, 3, 5, 6, 7

    • (d) 1,2,3,4,6,5,71, 2, 3, 4, 6, 5, 7

    • Validation Rules:

    • Rule 1 (Strict Level Order): All Level kk vertices must precede any Level k+1k+1 vertex.

    • Rule 2 (Parent Queue Order): Within a level, children of the parent dequeued earlier must enter the queue and appear first.

    • Option Analysis:

    • Option (a) violates Rule 1: Vertex 55 (Level 2) appears before 33 and 44 (Level 1). Invalid.

    • Option (c) violates Rule 2: If 44 is dequeued before 22, 44 discovers 66, while 22 discovers 55. Therefore, 66 must precede 55. Invalid.

    • Option (d) violates Rule 2: If 22 is dequeued before 33 and 44, 22 discovers 55 before 66 is discovered. Thus, 55 must precede 66. Invalid.

    • Option (b) is fully consistent: Level 1 is ordered 3,4,23, 4, 2. Vertex 33 dequeues first and discovers both 66 and 55. Enqueueing them as 6,56, 5 is valid, followed by 77 at Level 3. Valid.

    • Queue Trace for Option (b):

Step

Dequeue

New Neighbours Enqueued

Queue State (Front to Rear)

Output So Far

0

—

Start: enqueue 11

[ 1 ]

[]

1

11

3,4,23, 4, 2

[ 3, 4, 2 ]

[ 1 ]

2

33

6,56, 5 (11 visited)

[ 4, 2, 6, 5 ]

[ 1, 3 ]

3

44

None (1,61, 6 visited)

[ 2, 6, 5 ]

[ 1, 3, 4 ]

4

22

None (1,51, 5 visited)

[ 6, 5 ]

[ 1, 3, 4, 2 ]

5

66

77 (3,43, 4 visited)

[ 5, 7 ]

[ 1, 3, 4, 2, 6 ]

6

55

None (2,3,72, 3, 7 visited)

[ 7 ]

[ 1, 3, 4, 2, 6, 5 ]

7

77

None

[ ] (empty)

[ 1, 3, 4, 2, 6, 5, 7 ]

  • Problem 2: Identifying Non-Valid DFS Orders:

    • Using the same graph starting from vertex 11, identify which sequence is NOT a valid DFS order:

    • (a) 1,2,5,3,6,4,71, 2, 5, 3, 6, 4, 7

    • (b) 1,4,6,7,5,3,21, 4, 6, 7, 5, 3, 2

    • (c) 1,3,5,7,6,4,21, 3, 5, 7, 6, 4, 2

    • (d) 1,3,6,4,2,5,71, 3, 6, 4, 2, 5, 7

    • Verification Method:

    • In DFS, the next visited node must be an unvisited neighbour of the current stack top.

    • If the current top has no unvisited neighbours, it must be popped, and the next node must be an unvisited neighbour of the new stack top.

    • Analysis of Option (d):

    • Start at 11: push 11.

    • To 33: unvisited neighbour of 11; push 33.

    • To 66: unvisited neighbour of 33; push 66.

    • To 44: unvisited neighbour of 66; push 44.

    • From 44: all neighbours of 44 are visited. Dead end: pop 44.

    • Stack top is now 66. Neighbours of 66 include 77, which is unvisited.

    • However, option (d) jumps to vertex 22. Vertex 22 is not adjacent to 66, and 66 still has an unvisited neighbour (77), prohibiting a backtrack past 66.

    • Conclusion: Sequence (d) is NOT a valid DFS order.

  • Problem 3: BFS on Directed Graphs with Unreachable Nodes:

    • Directed graph with vertices {A,B,C,D,E}\{A, B, C, D, E\}.

    • Directed edges:
          A→B,A→C,C→D,D→B,E→A,E→DA \rightarrow B, \quad A \rightarrow C, \quad C \rightarrow D, \quad D \rightarrow B, \quad E \rightarrow A, \quad E \rightarrow D

    • Run BFS starting at AA with outgoing neighbours taken in alphabetical order.

    • Step-by-Step Execution:

    • Start at AA: mark AA visited, enqueue [ A ].

    • Dequeue AA: Output A. Outgoing edges go to BB and CC. Both are unvisited; enqueue BB, then CC. Queue: [ B, C ].

    • Dequeue BB: Output B. BB has out-degree 00. No nodes enqueued. Queue: [ C ].

    • Dequeue CC: Output C. Outgoing edge goes to DD. DD is unvisited; enqueue DD. Queue: [ D ].

    • Dequeue DD: Output D. Outgoing edge goes to BB. BB is already visited; skip. Queue: [ ] (empty).

    • Traversal terminates.

    • Crucial Traps:

    • Unreachable Vertices: Vertex EE has out-degree 22 (pointing to AA and DD) but in-degree 00. No directed path exists from AA to EE. Consequently, EE is never visited.

    • Alphabetical Precedence: At vertex AA, neighbour BB precedes CC, ensuring BB appears before CC in the output.

    • Final BFS Output: A, B, C, D.

  • Problem 4: DFS Visit Order versus Pop (Finish) Order:

    • Undirected 5-vertex graph with edges: (1,2),(1,3),(2,4),(3,4),(4,5)(1, 2), (1, 3), (2, 4), (3, 4), (4, 5).

    • Neighbour lists in ascending numerical order:

    • 1:2,31: 2, 3

    • 2:1,42: 1, 4

    • 3:1,43: 1, 4

    • 4:2,3,54: 2, 3, 5

    • 5:45: 4

    • Execution Trace (Start = 1):

    • Step 1: Visit 11, push 11. Stack: [ 1 ].

    • Step 2: From 11, visit lowest unvisited neighbour 22, push 22. Stack: [ 1, 2 ].

    • Step 3: From 22, neighbour 11 visited; visit 44, push 44. Stack: [ 1, 2, 4 ].

    • Step 4: From 44, neighbour 22 visited; lowest unvisited neighbour is 33. Visit 33, push 33. Stack: [ 1, 2, 4, 3 ].

    • Step 5: From 33, neighbours 11 and 44 are both already visited. Dead end reached at 33. Pop 3 (first vertex to finish).

    • Step 6: Stack top is 44. Remaining unvisited neighbour is 55. Visit 55, push 55. Stack: [ 1, 2, 4, 5 ].

    • Step 7: From 55, neighbour 44 is visited. Dead end. Pop 5.

    • Step 8: Stack top is 44. All neighbours visited. Pop 4.

    • Step 9: Stack top is 22. All neighbours visited. Pop 2.

    • Step 10: Stack top is 11. All neighbours visited. Pop 1.

    • Stack is empty.

    • Summary of Orders:

    • Visit Order (Push Order): 1,2,4,3,51, 2, 4, 3, 5

    • Finish Order (Pop Order): 3,5,4,2,13, 5, 4, 2, 1