= Graph theory
{wiki}
<Graph theory> studies <vertices> and the <edges> connecting them: which <graph paths> exist, how efficiently we can travel, and which connections are indispensable. A road map becomes a <graph> when junctions are <vertices> and road segments are <edges>; a communications network uses routers and links instead. The drawing helps us see connections, but its apparent lengths need not be the costs being optimized. Record travel times or transmission costs separately in a <weighted graph>.
The appeal of <graph theory> is that one model serves many practical questions. <Graph paths> describe routes, <connected components of a graph> identify isolated regions, and <minimum spanning trees> connect all locations cheaply. The <shortest path problem> asks a different question: find the cheapest journey between specified locations. Our four-<vertex> example below makes that distinction concrete and shows how the <Dijkstra algorithm> discovers a route without trying every <graph path>.
Back to article page
