Lesson 5 of 11Article18 min
Graph Theory Basics
A graph G=(V,E) models networks, dependencies, and maps. Degree, paths, cycles, and connectivity are the everyday vocabulary.
Vertices and edges
A graph G=(V,E) models networks, dependencies, and maps. Degree, paths, cycles, and connectivity are the everyday vocabulary.
- Bipartite: colourable with 2 colours; no odd cycles.
- Euler path: exactly 0 or 2 odd-degree vertices.
- Hamilton path: visits each vertex once — NP-hard to decide in general.
- Directed graphs: edges have orientation; DAGs model dependencies.