Graph Theory
A graph G = (V, E) consists of vertices (nodes) V and edges (links) E connecting pairs of vertices. Graph theory models networks, relationships, and structures in computer science — from social networks to routing algorithms.
Types of Graphs
Undirected graphs have unordered edge pairs; directed graphs (digraphs) have ordered pairs. Simple graphs have no loops or multiple edges. Multigraphs allow multiple edges. Weighted graphs assign values to edges. Complete graphs (Kₙ) connect every pair of vertices.
Graph Representation
Graphs are represented as adjacency matrices (n×n matrix, entry 1 if edge exists), adjacency lists (list of neighbours for each vertex), or incidence matrices. Adjacency lists are space-efficient for sparse graphs; matrices enable fast edge lookups.
Paths and Connectivity
A path is a sequence of vertices connected by edges. A cycle is a path that starts and ends at the same vertex. A graph is connected if a path exists between every pair of vertices. Strongly connected digraphs have paths in both directions between every pair.
Euler and Hamilton
An Euler path traverses every edge exactly once (exists iff exactly 0 or 2 vertices have odd degree). An Euler circuit is a closed Euler path (all vertices even degree). A Hamiltonian path visits every vertex exactly once. Finding Hamiltonian paths is NP-complete.
Trees
A tree is a connected acyclic graph. Properties: n vertices, n−1 edges, unique path between any two vertices. A spanning tree of G includes all vertices with minimum edges. Rooted trees have a designated root with parent-child relationships. Binary trees have at most two children per node.
Planar Graphs
A planar graph can be drawn without edge crossings. Euler's formula: V − E + F = 2 (for connected planar graphs, where F is faces). K₅ and K₃,₃ are non-planar. Kuratowski's theorem: a graph is planar iff it contains no subdivision of K₅ or K₃,₃.
Graph Colouring
Graph colouring assigns colours to vertices such that no adjacent vertices share a colour. The chromatic number χ(G) is the minimum colours needed. Applications include scheduling, register allocation, and map colouring. The four colour theorem states that planar graphs need at most 4 colours.
Summary
Graph theory provides powerful abstractions for modelling and solving problems involving connections and networks. Understanding graph types, representations, traversals, trees, and colouring is essential for algorithm design and analysis.