Overview
Graph Theory is the study of networks. A graph is made up of vertices (nodes/points) connected by edges (lines/links). It is the language of connections.
Core Idea
The core idea is abstraction of connectivity. It doesn’t matter where the nodes are or how long the edges are; all that matters is what is connected to what.
Formal Definition
A graph $G$ is an ordered pair $(V, E)$, where $V$ is a set of vertices and $E$ is a set of edges (pairs of vertices).
- Directed Graph: Edges have a direction (arrows).
- Undirected Graph: Edges are two-way connections.
Intuition
Think of a subway map. The exact twists and turns of the tunnels don’t matter for navigation; only the sequence of stations (nodes) and lines (edges) matters. That map is a graph.
Examples
- Social Networks: People are nodes; friendships are edges.
- The Internet: Computers are nodes; cables/wifi are edges.
- Seven Bridges of Königsberg: The puzzle that started graph theory (Euler). Can you cross all 7 bridges without retracing your steps? (No).
Common Misconceptions
- Misconception: It’s about $y=mx+b$ graphs.
- Correction: Those are “plots” of functions. In discrete math, a “graph” is a network structure.
- Misconception: The traveling salesman problem is easy.
- Correction: Finding the shortest path visiting every node is NP-hard (very difficult for large graphs).
Related Concepts
- Tree: A graph with no cycles (loops).
- Network Theory: The application of graph theory to real-world systems.
- Topology: Graph theory is essentially 1-dimensional topology.
Applications
- Computer Science: Algorithms for routing (GPS), searching, and sorting data.
- Biology: Modeling neural networks or metabolic pathways.
- Logistics: Optimizing delivery routes.
Criticism and Limitations
- Complexity: Many interesting graph problems (Coloring, Clique, Hamiltonian Path) are computationally intractable (NP-complete).
Further Reading
- Introduction to Graph Theory by Richard J. Trudeau
- Graph Theory by Reinhard Diestel