Types of Graphs (Directed, Undirected, Weighted)

Math for CS · Axiom Academy

Complete, bipartite, regular, planar, and DAGs Complete graphs arise when modeling full connectivity — for instance, a round-robin tournament where every team plays every other team. An equivalent characterization: a graph is bipartite if and only if it contains no odd-length cycle. The complete bipartite graph K_ m,n has every vertex in U ( |U|=m ) connected to every vertex in W ( |W|=n ). 0 -regular: isolated vertices (no edges) 1 -regular: a perfect matching 2 -regular: a disjoint union of cycles 3 -regular: called a cubic graph . The Petersen graph is a famous example. (n-1) -regular on n vertices: the complete graph K_n Planar graphs satisfy Euler's formula and have important edge bounds. We cover them in detail in the Planar Graphs lesson. Directed Acyclic Graphs (DAGs) DAGs are ubiquitous in computer science because they represent dependency structures — situations where some things must happen before others. Build systems: Makefiles are DAGs of compilation dependencies Course prerequisites: CS201 requires CS101, forming a DAG Version control: Git commits form a DAG Task scheduling: Topological sort orders tasks so dependencies come first Trees are among the most important graph types. They are the "minimally connected" graphs — removing any edge disconnects them, and adding any edge creates a cycle. We dedicate a full lesson to trees and spanning trees later in this unit. The Handshaking Lemma Revisited

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