Graph Theory

A graph G = (V, E) is the simplest possible structure for capturing pairwise relationships. V is a set of vertices (nodes). E is a set of edges (pairs of vertices). Graphs model: social networks (people are vertices, friendships are edges), the web (pages are vertices, hyperlinks are directed edges), circuit boards (components are vertices, wires are edges), transportation (cities are vertices, roads are edges), and the internet itself (routers are vertices, cables are edges). A graph can be directed (edges have direction, like Twitter follows) or undirected (edges are mutual, like Facebook friendships). A weighted graph assigns a number to each edge (road distance, bandwidth, cost).

The degree of a vertex is the number of edges touching it. In a directed graph, we distinguish in-degree (incoming) and out-degree (outgoing). The degree distribution P(k) tells what fraction of vertices have degree k. Many real networks follow a power law: P(k) ∝ k^{-γ} — a few hubs with huge degree, many leaves with tiny degree. This is the signature of scale-free networks (like the web and social networks). Clustering coefficient measures how much a vertex's neighbors connect to each other: C = (number of edges between neighbors) / (maximum possible). High clustering means tightly knit communities. The diameter is the longest shortest path between any two vertices — it measures how "spread out" the network is. Social networks famously have diameter ≈ 6 (six degrees of separation).

Four algorithms solve the majority of graph problems. Breadth-First Search (BFS) explores level by level from a source. It finds shortest paths in unweighted graphs (O(V+E) time) and reveals the graph's connected structure. Depth-First Search (DFS) explores as deep as possible before backtracking. It detects cycles, finds topological orderings for directed acyclic graphs (DAGs), and identifies strongly connected components.

Dijkstra's algorithm finds shortest paths from a source to all other vertices in a weighted graph with NON-NEGATIVE weights. It uses a priority queue (min-heap) and runs in O((V+E)logV). This is the algorithm behind every GPS navigation system. Bellman-Ford handles negative weights (but not negative cycles) and detects negative cycles — essential for arbitrage detection in finance.

For ALL-pairs shortest paths, Floyd-Warshall runs in O(V³) using dynamic programming: d[i][j] = min(d[i][j], d[i][k] + d[k][j]) for all k as intermediate vertices.

A tree is a connected acyclic graph: n vertices, exactly n-1 edges. Trees are the backbone of hierarchical data (file systems, DOM trees, decision trees). A spanning tree connects all vertices using a subset of edges. The Minimum Spanning Tree (MST) does so with minimum total edge weight. Prim's and Kruskal's algorithms build MSTs greedily.

A bipartite graph has vertices partitionable into two sets where all edges go between sets. Important for matching problems: assigning workers to tasks, students to schools, drivers to rides.

A graph is planar if it can be drawn without edge crossings. The Four Color Theorem (proved 1976, first computer-assisted proof) states that any planar map needs at most 4 colors so adjacent regions differ. Euler's formula: for a connected planar graph, V - E + F = 2 where F counts faces (including the outer unbounded face).

A complete graph K_n has all possible edges. A cycle C_n forms a single ring. A path P_n is a line. The Petersen graph is the canonical counterexample for many conjectures.

Graph properties scale with vertex count. Explore how functions like n², n log n, and 2^n grow — these describe algorithm runtime complexity for different graph operations.