Graph theory is an atlas of interconnectivity, mapping simple routes of nodes and edges to intricate highways of network flow and planar graphs. Graph representations are useful in internet routing, natural language processing, epidemiology, and more. ![[DALLE3_GraphTheory.png]] ## Concept Tree ### Basic 1. **Introduction to Graphs** - Vertices, Edges - Directed vs Undirected Graphs - Weighted Graphs 2. **Paths and Cycles** - Paths, Walks, Trails - Cycles, Hamiltonian and Eulerian Cycles 3. **Graph Traversal Algorithms** - Breadth-First Search (BFS) - Depth-First Search (DFS) ### Advanced 1. **Connectivity** - Connected and Disconnected Graphs - Strongly Connected Components - Bridges and Articulation Points 2. **Graph Coloring** - Vertex Coloring - Edge Coloring - Chromatic Number 3. **Graph Isomorphism** - Definitions and Examples - Algorithms for Checking Isomorphism ### Mastery 1. **Network Flow** - Max Flow, Min Cut - Ford-Fulkerson Algorithm - Edmonds-Karp Algorithm 2. **Planar Graphs** - Definitions and Properties - Kuratowski’s Theorem 3. **Advanced Graph Algorithms** - Dijkstra's Algorithm - Floyd-Warshall Algorithm - Kruskal's and Prim's Algorithms