Graphs and Terminology

Math for CS · Axiom Academy

The universal language of connections A graph is one of the most versatile structures in computer science. At its core, a graph is just a collection of objects (vertices) and connections between them (edges). This simple idea models an enormous range of real-world systems. Whenever you see a relationship between things — people who know each other, cities connected by roads, tasks that depend on other tasks — you are looking at a graph. People are vertices. Friendships are edges. Facebook's social graph has billions of nodes. Algorithms find communities, suggest friends, and detect influence. Web pages are vertices. Hyperlinks are directed edges. Google's PageRank algorithm uses graph theory to rank search results. Intersections are vertices. Roads are weighted edges (distance or time). GPS apps use shortest-path algorithms like Dijkstra's to find routes. Software packages are vertices. Dependencies are directed edges. npm install and apt-get resolve dependency graphs daily. Routers are vertices. Cables are edges with bandwidth capacities. Network flow algorithms maximize throughput and detect bottlenecks. Variables are vertices. Conflicts are edges. Graph coloring assigns CPU registers efficiently — a direct application of the chromatic number.

This is the written version of the interactive lesson above. See the full Math for CS course.