AGT LAB Questions

I. General Graph Theory Concepts

1. Q: What is a graph? What are its basic components? A: A graph $G$ is a mathematical structure defined as a pair $(V,E)$, where $V$ is a finite set of vertices (or nodes) and $E$ is a set of edges (or arcs). Each edge connects a pair of vertices. Edges can be directed (arcs) or undirected.

2. Q: What’s the difference between a directed and an undirected graph? A: In an undirected graph, edges represent symmetric relationships; an edge $(u,v)$ means there’s a connection between $u$ and $v$. In a directed graph (digraph), edges (arcs) have a direction; an arc $(u,v)$ represents a connection from $u$ to $v$.

3. Q: What does it mean for a graph to be weighted? A: A weighted graph is a graph where each edge $(u,v)\in E$ is assigned a numerical value, $w(u,v)$, called a weight or cost.

4. Q: What is the degree of a vertex? Differentiate between in-degree and out-degree. A: In an undirected graph, the degree of a vertex $v$, denoted $deg(v)$, is the number of edges incident to it. In a directed graph, the in-degree of $v$ is the number of incoming edges, and the out-degree is the number of outgoing edges.

5. Q: What does it mean for a graph $G$ to be connected? What about strongly connected (for digraphs)? A: An undirected graph is connected if there is a path between every pair of distinct vertices $(u,v)$ in $V$. A directed graph is strongly connected if there is a directed path from $u$ to $v$ and a directed path from $v$ to $u$ for every pair of distinct vertices $(u,v)\in V$.

II. Graph Representations (Experiment 1, 2, 3)

6. Q: Describe the two main ways to represent a graph $G=(V,E)$ in a computer program. A: The two main ways are:

   • Adjacency Matrix: A $|V|\times |V|$ matrix $A$ where entry $A[i][j]$ is $1$ (or $w(i,j)$ for weighted graphs) if there’s an edge from vertex $i$ to vertex $j$, and $0$ (or $\infty$/special value) otherwise.
   • Adjacency List: An array (or map) of $|V|$ lists. The list $Adj[u]$ contains all vertices $v$ such that $(u,v)\in E$. For weighted graphs, the list stores pairs $(v,w(u,v))$.

7. Q: Compare the Adjacency Matrix and Adjacency List representations in terms of space complexity and efficiency for common operations (checking edge $(u,v)$ existence, finding neighbors of $u$). A:

   • Space Complexity: Matrix is $O(|V{|}^2)$. List is $O(|V|+|E|)$. List is better for sparse graphs ($|E|\ll |V{|}^2$).
   • Edge Check $(u,v)$: Matrix is $O(1)$. List is $O(deg(u))$ in the worst case.
   • Finding Neighbors of $u$: Matrix is $O(|V|)$. List is $O(deg(u))$.
   • Adding/Removing Edge: Matrix is $O(1)$. List is $O(1)$ on average or $O(deg(u))$.
   • Adding/Removing Vertex: Matrix is $O(|V{|}^2)$. List is more flexible, often $O(1)$ to add, $O(|V|+|E|)$ to remove.

8. Q: Your Experiment 1 used a linked representation. Explain how that structure works. How does it relate to the standard Adjacency List? A: The linked representation uses header nodes for vertices, each with info, nextnode, and arcptr. arcptr points to the Adjacency List for that vertex, implemented as a linked list of arc nodes, each containing ndptr (pointer to destination vertex) and nextarc. This is a concrete linked-list implementation of the Adjacency List concept $Adj[u]$.

III. Graph Traversal (Experiment 1)

9. Q: Explain Breadth-First Search (BFS). What kind of data structure does it use? What is it typically used for? A: BFS explores layer by layer from a source $s$. It uses a Queue. It finds the shortest path in terms of the number of edges in unweighted graphs, checks connectivity, and is used in algorithms like Edmonds-Karp.

10. Q: Explain Depth-First Search (DFS). What kind of data structure does it use (implicitly or explicitly)? What are some applications? A: DFS explores as deeply as possible before backtracking. It uses a Stack (often the call stack via recursion). Applications include cycle detection, topological sorting (for DAGs), finding connected components (like $G$‘s decomposition).

11. Q: Compare BFS and DFS. When would you prefer one over the other? A:

    • Structure: BFS uses Queue (level-order). DFS uses Stack (pre-order style).
    • Pathfinding: BFS finds shortest path (edge count). DFS doesn’t guarantee shortest.
    • Space: BFS can use $O(|V|)$ memory. DFS might use less $O(\text{depth})$ but $O(|V|)$ worst-case.
    • Use Cases: BFS for shortest unweighted path. DFS for cycles, topological sort.

IV. Minimum Spanning Tree (MST) (Experiment 2, 3)

12. Q: What is a Minimum Spanning Tree (MST) of a connected, undirected, weighted graph $G=(V,E,w)$? A: An MST is a subgraph $T=(V,E^{\prime })$ where $E^{\prime }\subseteq E$, $T$ is a tree, $T$ connects all vertices in $V$, and the total weight ${\sum }_{(u,v)\in E^{\prime }}w(u,v)$ is minimized.

13. Q: Explain Prim’s algorithm ($MST-PRIM(G,w,r)$). How does it build the MST? What is its core greedy strategy? A: Prim’s starts at a root $r$ and grows a tree $A$. It maintains a set $S$ of vertices in $A$. In each step, it finds the minimum-weight edge $(u,v)$ with $u\in S$ and $v\in V\setminus S$, and adds $v$ to $S$ and $(u,v)$ to $A$. Greedy choice: cheapest edge crossing the cut $(S,V\setminus S)$.

14. Q: What data structure makes Prim’s algorithm efficient? How does it affect the complexity? (Referencing $u.key$, $u.\pi$, $Q$) A: A Priority Queue $Q$ storing vertices $v\in V\setminus S$, prioritized by $v.key$ (minimum edge weight connecting $v$ to $S$).

    • Matrix/scan: $O(|V{|}^2)$.
    • Adj. List + Binary Heap: $O(|E|\log |V|)$ using $EXTRACT-MIN$ and $DECREASE-KEY$.
    • Adj. List + Fibonacci Heap: $O(|E|+|V|\log |V|)$.

15. Q: Explain Kruskal’s algorithm ($MST-KRUSKAL(G,w)$). What is its core greedy strategy? A: Kruskal’s sorts all edges $E$ by weight $w$. It iterates through sorted edges $(u,v)$, adding $(u,v)$ to the MST set $A$ if it doesn’t form a cycle with edges already in $A$. Greedy choice: consider cheapest edges first overall.

16. Q: How does Kruskal’s algorithm typically detect cycles? (Referencing $MAKE-SET$, $FIND-SET$, $UNION$) A: Uses a Disjoint Set Union (DSU) data structure. Each vertex $v$ starts in its own set via $MAKE-SET(v)$. For edge $(u,v)$, if $FIND-SET(u)\ne FIND-SET(v)$, the edge connects different components and is added to $A$, followed by $UNION(u,v)$. Otherwise, it forms a cycle and is skipped.

17. Q: Compare Prim’s and Kruskal’s algorithms. When might one be preferred over the other? A:

    • Approach: Prim’s grows one tree. Kruskal’s merges components (forest).
    • Complexity: Prim’s $O(|E|+|V|\log |V|)$ (Fib. heap). Kruskal’s $O(|E|\log |E|)$ or $O(|E|\log |V|)$ (sorting + DSU).
    • Preference: Prim’s for dense graphs ($|E|\approx |V{|}^2$). Kruskal’s for sparse graphs ($|E|\approx |V|$), or if edges are pre-sorted, or for finding Minimum Spanning Forests.

V. Euler Tours (Experiment 5)

18. Q: What is an Euler Path? What is an Euler Circuit (or Tour)? A: An Euler Path is a trail visiting every edge $e\in E$ exactly once. An Euler Circuit is an Euler path starting and ending at the same vertex.

19. Q: What are the necessary and sufficient conditions for an undirected graph $G$ to have an Euler Circuit? An Euler Path? A: For a connected $G$:

    • Euler Circuit: $deg(v)$ is even for all $v\in V$.
    • Euler Path: Exactly $0$ or $2$ vertices have odd $deg(v)$. If $0$, it’s a circuit. If $2$, the path connects the two odd-degree vertices.

20. Q: Explain Hierholzer’s algorithm for finding an Euler Tour. Why does it work? A: Start at $v_0$, follow unused edges forming a cycle $C_1$. If edges remain, find $v\in C_1$ with unused incident edges, start a new tour $C_2$ from $v$, splice $C_2$ into $C_1$. Repeat. Uses a stack: push vertices during traversal, pop to circuit list when stuck. Works because even degrees (or 2 odd) guarantee traversability until all edges are used.

VI. Hamiltonian Cycles (Experiment 6)

21. Q: What is a Hamiltonian Path? What is a Hamiltonian Cycle? A: A Hamiltonian Path visits every vertex $v\in V$ exactly once. A Hamiltonian Cycle is a Hamiltonian path $(v_1,v_2,...,v_{|V|})$ where $(v_{|V|},v_1)$ is also an edge in $E$.

22. Q: Is finding Hamiltonian cycles easy or hard compared to Euler tours? Why? A: Much harder. Hamiltonian Cycle is NP-complete. No simple local conditions (like $deg(v)$) guarantee existence.

23. Q: Describe the backtracking approach used in Experiment 6 to find Hamiltonian cycles. A: Build path $P=(v_1,...,v_k)$. Try adding $v_{k+1}$ adjacent to $v_k$ where $v_{k+1}\notin P$. Recurse. If $k=|V|$ and $(v_k,v_1)\in E$, cycle found. If stuck, backtrack: remove $v_k$, try different neighbor for $v_{k-1}$.

24. Q: Can you name any theorems that give sufficient (but not necessary) conditions for a Hamiltonian cycle? A:

    • Dirac’s Theorem: If $G$ has $|V|\ge 3$ and minimum degree $\delta (G)\ge |V|/2$, then $G$ is Hamiltonian.
    • Ore’s Theorem: If $G$ has $|V|\ge 3$ and $deg(u)+deg(v)\ge |V|$ for every pair of non-adjacent $u,v$, then $G$ is Hamiltonian.

VII. Maximum Flow (Experiment 7, 8)

25. Q: Define: Flow Network, Source ($s$), Sink ($t$), Capacity ($c$), Flow ($f$). A:

    • Flow Network: Directed graph $G=(V,E)$ with edge capacities $c(u,v)\ge 0$.
    • Source ($s$): Vertex with in-degree $0$ (or designated).
    • Sink ($t$): Vertex with out-degree $0$ (or designated).
    • Capacity $c(u,v)$: Max flow on edge $(u,v)$.
    • Flow $f(u,v)$: Function $f:E\to {\mathbb{R}}^{+}$ satisfying:
      • Capacity Constraint: $0\le f(u,v)\le c(u,v)$ for all $(u,v)\in E$.
      • Flow Conservation: $\forall v\in V\setminus \{s,t\}$, ${\sum }_{(u,v)\in E}f(u,v)={\sum }_{(v,w)\in E}f(v,w)$.

26. Q: What is the Maximum Flow problem? A: Find a feasible flow $f$ maximizing the net flow out of $s$, $|f|={\sum }_{(s,v)\in E}f(s,v)-{\sum }_{(u,s)\in E}f(u,s)$.

27. Q: Explain the concept of a Residual Graph ($G_f$). How is it used in Ford-Fulkerson? A: $G_f=(V,E_f)$ represents remaining capacity. For $(u,v)\in E$:

    • Forward edge $(u,v)\in E_f$ with capacity $c_f(u,v)=c(u,v)-f(u,v)$ if $f(u,v)<c(u,v)$.
    • Backward edge $(v,u)\in E_f$ with capacity $c_f(v,u)=f(u,v)$ if $f(u,v)>0$. Ford-Fulkerson finds paths in $G_f$.

28. Q: What is an Augmenting Path ($p$) in the context of max flow? A: A simple path $p$ from $s$ to $t$ in the residual graph $G_f$. Indicates flow can be increased along $p$ by the bottleneck capacity $c_f(p)=\min \{c_f(u,v)|(u,v)\in p\}$.

29. Q: Describe the Ford-Fulkerson method ($FORD-FULKERSON(G,s,t)$). Is it an algorithm itself? A: Method:

    1. $f\leftarrow 0$.
    2. While $\exists$ augmenting path $p$ in $G_f$: a. $c_f(p)\leftarrow \min \{c_f(u,v)|(u,v)\in p\}$. b. Augment flow $f$ along $p$ by $c_f(p)$. c. Update $G_f$.
    3. Return $f$. It’s a method; the specific algorithm depends on path choice (e.g., BFS, DFS).

30. Q: What is the Edmonds-Karp algorithm ($EDMONDS-KARP(G,s,t)$)? How does it differ from the general Ford-Fulkerson method? What is its advantage? A: Edmonds-Karp is Ford-Fulkerson where the augmenting path $p$ is always chosen as the shortest path (min edges) in $G_f$, found using BFS.

    • Difference: Specifies BFS for path finding.
    • Advantage: Guaranteed polynomial time complexity $O(|V||E{|}^2)$.

31. Q: What is the Max-Flow Min-Cut Theorem? A: The maximum value of an $s-t$ flow $|f|$ equals the minimum capacity of an $s-t$ cut $(S,T)$. Cut capacity is ${\sum }_{u\in S,v\in T,(u,v)\in E}c(u,v)$.

32. Q: You implemented Ford-Fulkerson using DFS (Task 4, Exp 8). How might its performance compare to Edmonds-Karp (using BFS)? Could it be worse? A: Yes, DFS-based Ford-Fulkerson can be much worse. It doesn’t guarantee shortest paths and can lead to $O(|f^{\ast }|\times |E|)$ augmentations, which can be exponential in input size for pathological cases, unlike Edmonds-Karp’s $O(|V||E{|}^2)$.

VIII. Graph Coloring (Experiment 9, 10)

33. Q: What is Vertex Coloring? What is the Chromatic Number $\chi (G)$? A: Vertex coloring assigns colors $C(v)$ to vertices $v\in V$ such that $C(u)\ne C(v)$ if $(u,v)\in E$. The Chromatic Number $\chi (G)$ is the minimum number of colors needed.

34. Q: What is Edge Coloring? What is the Chromatic Index ${\chi }^{\prime }(G)$? A: Edge coloring assigns colors $C(e)$ to edges $e\in E$ such that $C(e_1)\ne C(e_2)$ if edges $e_1,e_2$ share a common vertex. The Chromatic Index ${\chi }^{\prime }(G)$ is the minimum number of colors needed.

35. Q: Explain the Greedy Coloring algorithm for vertices. Is it guaranteed to find $\chi (G)$? A: Process vertices $v_1,...,v_{|V|}$. Assign $C(v_i)=\min \{k\ge 1\mid k\ne C(v_j)\text{ for all }j<i\text{ where }(v_i,v_j)\in E\}$. Not optimal (depends on order), but uses $\le \Delta (G)+1$ colors, where $\Delta (G)$ is max degree.

36. Q: How does the backtracking algorithm find the optimal vertex coloring ($\chi (G)$)? A: Tries assigning colors $1,...,k$ to vertices recursively. If $C(v)$ = $c$ is assigned, check constraints $C(v)\ne C(u)$ for adjacent, already colored $u$. If valid, recurse. If not, backtrack and try $c+1$. Explores state space to find minimum $k=\chi (G)$, potentially exponential time.

37. Q: What does Vizing’s Theorem state about edge coloring ${\chi }^{\prime }(G)$? A: For any simple graph $G$, ${\chi }^{\prime }(G)$ is either $\Delta (G)$ or $\Delta (G)+1$. Graphs are Class 1 (${\chi }^{\prime }(G)=\Delta (G)$) or Class 2 (${\chi }^{\prime }(G)=\Delta (G)+1$).

38. Q: Explain the concept of Face Coloring for planar graphs (Experiment 10). A: Assign colors to faces $F$ of a planar embedding of $G$ such that adjacent faces (sharing edge boundary) get different colors.

39. Q: How can you use the Dual Graph $G^{\ast }$ to solve the face coloring problem? A: Construct $G^{\ast }$: one vertex $v_f$ for each face $f$ in $G$. Edge $(v_f,v_{f^{\prime }})$ exists in $G^{\ast }$ if faces $f,f^{\prime }$ share an edge in $G$. Face coloring $G$ is equivalent to vertex coloring $G^{\ast }$.

40. Q: What is the famous theorem related to face coloring planar graphs? Did your algorithm likely rely on it directly? A: The Four Color Theorem: $\chi (G^{\ast })\le 4$ for any planar $G$. My greedy algorithm on $G^{\ast }$ colors faces but doesn’t guarantee using only $4$ colors; it applies the principle but doesn’t prove the theorem.

IX. Maximum Weight Matching (Experiment 11)

41. Q: What is a Matching $M$ in a graph $G=(V,E)$? What is a Maximum Cardinality Matching? A: A matching $M\subseteq E$ such that no two edges in $M$ share a vertex. Maximum Cardinality Matching has the largest possible $|M|$.

42. Q: What is a Bipartite Graph? A: $G=(V,E)$ where $V$ can be partitioned into two disjoint sets $U,W$ ($V=U\cup W,U\cap W=\varnothing$) such that every edge $(u,w)\in E$ connects $u\in U$ to $w\in W$.

43. Q: What problem does the Hungarian Algorithm solve? A: Finds a maximum weight matching in a weighted bipartite graph $G=(U\cup W,E,w)$. Finds $M\subseteq E$ maximizing ${\sum }_{(u,w)\in M}w(u,w)$.

44. Q: Can you briefly explain the high-level idea behind the Hungarian algorithm (Kuhn-Munkres)? What are concepts like ‘labels’ $l(v)$ and ‘equality subgraph’ $G_l$? A: Maintains labels $l(v)$ for $v\in V$. The equality subgraph $G_l$ contains edges $(u,w)$ where $u\in U,w\in W$ such that $l(u)+l(w)=w(u,w)$. Find augmenting path in $G_l$. If none, update labels $l(v)$ based on slack $s(u,w)=l(u)+l(w)-w(u,w)$ to expand $G_l$. Repeat until max matching found in $G_l$.

45. Q: What is the time complexity of the Hungarian Algorithm? A: Standard implementation is $O(|V{|}^3)$ where $|V|$ is vertices per partition ($n$ if $|U|=|W|=n$). Can be $O(n(|E|+n\log n))$ or $O(n|E|)$ with heaps. (Here $|V|$ refers to $n$, the size of one partition, consistent with typical analysis).

X. Implementation & Practical Aspects

46. Q: When implementing Prim’s algorithm (Exp 2), matrix vs priority queue. What practical differences? A: Matrix (Task 1) is $O(|V{|}^2)$. Priority Queue (Task 2) is $O(|E|\log |V|)$ (binary heap), much faster for sparse graphs ($|E|\ll |V{|}^2$).

47. Q: In Kruskal’s algorithm (Exp 3), why is the efficiency of the Disjoint Set Union ($FIND-SET$, $UNION$) operations important? A: Kruskal’s performs $|E|$ $FIND-SET$s and $|V|-1$ $UNION$s. Efficient DSU (path compression, union by rank/size) makes this part nearly linear $O(|E|\alpha (|V|))$, where $\alpha$ is inverse Ackermann. The overall $O(|E|\log |E|)$ is then dominated by sorting.

48. Q: For user input tasks, challenges in parsing graph input? A: Format definition, input validation (indices in $[0,|V|-1]$?, weights $\ge 0$?), mapping symbolic names (‘a’) to indices ($0$), choosing internal representation (matrix vs list).

49. Q: Why is visualization useful in graph algorithms (Exp 3, 6, 9, 10)? Tools? A: Understanding structure/progress, debugging logic/representation, communication. Tools: Python (NetworkX, Matplotlib), Graphviz, Gephi.