Unit 6 Summary

Math for CS · Axiom Academy

Comprehensive review of all graph concepts covered in this unit A graph consists of vertices and edges . Edges can be directed or undirected , weighted or unweighted . Handshaking Lemma: — the sum of degrees is always even. A tree is a connected acyclic graph with edges on vertices. Euler's formula for planar graphs: . Uses a queue (FIFO) for level-by-level exploration. Finds shortest paths in unweighted graphs — . Tests bipartiteness by two-coloring levels. Finds connected components by running from each unvisited vertex. Uses a stack (LIFO) or recursion for deep-first exploration. Assigns discovery and finish timestamps ; satisfies the Parenthesis Theorem. Classifies edges: tree, back, forward, cross . Back edge = cycle in directed graphs. Enables topological sort (reverse post-order on a DAG). Foundation for strongly connected components (Tarjan's, Kosaraju's). Relaxation: If d[u] + w(u,v)"> , update . All three produce a shortest-path tree via parent pointers. Social networks exhibit power-law degree distributions (scale-free). Small-world property: average path length . Community detection via modularity, Girvan-Newman, label propagation, or spectral methods. Centrality measures: degree, betweenness, closeness, eigenvector, PageRank. The internet is a weighted graph of routers and links. OSPF (link-state) uses Dijkstra's algorithm within autonomous systems. RIP (distance-vector) uses Bellman-Ford's relaxation approach.

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