Graph Theory Lab

Mathematical Principles & Theorems

Investigates discrete graphs \(G = (V, E)\). Dijkstra's algorithm computes single-source shortest paths in \(\mathcal{O}(|E| + |V|\log |V|)\) for non-negative edge weights. Kruskal's algorithm constructs a Minimum Spanning Tree (MST) using greedy edge selection and Disjoint Set Union (DSU). An Eulerian circuit exists iff all vertices have even degree. The Four Color Theorem guarantees any planar graph can be vertex-colored using at most 4 colors.

Operating Instructions

• Select graph layout preset or click on canvas to add vertices and weighted edges.
• Select algorithm: Dijkstra Shortest Path, Kruskal Minimum Spanning Tree, BFS, DFS, or Graph Coloring.
• Choose source/target vertices and step through execution to observe priority queue and frontier updates.
• Review generated adjacency matrix, degree sequence, and total path cost readouts.