GRAPH THEORY (Professional Elective - IV) IV Year B.Tech. CSE I -Sem JNTUH R-18

1. In the Königsberg bridges problem, explain how Eulerian path and circuit concepts helped solve the puzzle.

2. Given two adjacency matrices, develop an algorithm to determine if the corresponding graphs are isomorphic.

3. Compare and contrast the suitability of adjacency matrix, adjacency list, and incidence matrix representations for different graph applications.

4. Can a graphic sequence with all even degrees be realized as a real graph? Explain your answer using the Havel-Hakimi criterion.

5. Model a computer network topology as a graph. Explain how this model can be used to optimize data flow and minimize communication overhead.

Unit 2: Connected Graphs and Shortest Paths:

1. Prove that a graph with at least two vertices is disconnected if and only if it has a cut-vertex.

2. Given a connected graph, propose an efficient algorithm to identify all its cut-vertices and cut-edges.

3. Apply Dijkstra's algorithm to find the shortest path from Hyderabad to Delhi on a weighted road network represented as a graph.

4. Compare the time complexity of Dijkstra's algorithm and Floyd-Warshall algorithm for finding shortest paths in dense graphs.

5. Explain how shortest path algorithms can be used to optimize delivery routes for online shopping platforms.

Unit 3: Trees:

1. Using Cayley's formula, calculate the number of non-isomorphic trees with 6 vertices.

2. Explain how Kirchhoff's matrix-tree theorem can be used to analyze the number of spanning trees in a complete graph.

3. Implement Prim's or Kruskal's algorithm to find a minimum spanning tree for a given weighted graph and justify your choice of algorithm.

4. Identify and characterize special classes of graphs like bipartite graphs, chordal graphs, and Eulerian graphs by providing key properties.

5. Apply Fleury's algorithm to find an Eulerian circuit in a postal delivery network and explain its advantages over a simple Hamiltonian path.

Unit 4: Independent Sets, Coverings, and Matchings:

1. State and prove Hall's Theorem for bipartite graphs. How does it guarantee the existence of perfect matchings?

2. Run the greedy algorithm for maximum matching on a small example graph and analyze its performance compared to an optimal solution.

3. Explain the concept of edge-coloring and prove the Gupta-Vizing theorem for edge chromatic number.

4. Utilize Hajos union to prove that a complete graph with an odd number of vertices is not a Class-2 graph for edge coloring.

5. Model a course scheduling problem with resource constraints as a graph, and apply an appropriate edge-coloring technique to find a conflict-free schedule.

Unit 5: Vertex Colorings:

1. Prove Mycielski's theorem and discuss its implication for the lower bound of chromatic number.

2. Implement the greedy coloring algorithm on different types of graphs (e.g., complete graph, bipartite graph) and analyze its coloring results.

3. Explain the significance of Brooks' theorem in relating chromatic number and edge chromatic number of graphs.

4. Define equitable edge-coloring and explain its practical applications in resource allocation problems like assigning tasks to workers.

5. Formulate a real-world problem like exam scheduling with different exam durations as a graph coloring problem and propose a solution using appropriate graph colorings.