Classical Graph Theory

Classical graph theory provides the foundational concepts and tools for analyzing relationships and networks using graphs, consisting of vertices and edges. From basic definitions of connectivity and planarity to complex algorithms for shortest paths and maximum flow, graph theory has broad applications in computer science, operations research, and various other fields.

Graphs: Foundations and Terminology: A graph is a fundamental structure in discrete mathematics, composed of vertices (nodes) and edges that connect these vertices. Formally, a graph G is defined as an ordered pair G = (V, E), where V is a non-empty set of vertices, and E is a set of edges. Each edge is a connection between two vertices. Edges can be directed (ordered pairs) or undirected (unordered pairs). A directed graph is also called a digraph. Key terms include: Adjacent vertices (connected by an edge), Incident edge (edge connected to a vertex), Degree of a vertex (number of edges incident to a vertex), Path (sequence of vertices connected by edges), Cycle (a path that starts and ends at the same vertex), Connected graph (a graph where a path exists between any two vertices), and Complete graph (a graph where every pair of vertices is connected by an edge). Understanding these definitions is crucial for analyzing graph properties and applying graph algorithms. A common misconception is that a graph must be planar; graphs can exist in higher dimensions and may not be able to be drawn on a plane without edges crossing. Graph theory has its roots in Euler's solution to the Königsberg bridge problem in 1736, marking its official beginning.

Representing Graphs: Adjacency Matrices and Lists: Graphs can be represented in various ways for algorithmic manipulation. Two common methods are adjacency matrices and adjacency lists. An adjacency matrix is a square matrix where the element A[i][j] is 1 if there is an edge from vertex i to vertex j, and 0 otherwise. For undirected graphs, the adjacency matrix is symmetric. While easy to implement, adjacency matrices require O(V^2) space, making them inefficient for sparse graphs (graphs with few edges). An adjacency list, on the other hand, represents a graph as an array of lists, where each list associated with a vertex contains its adjacent vertices. This representation uses O(V + E) space, making it more efficient for sparse graphs. The choice between adjacency matrices and lists depends on the graph's density and the operations to be performed. For example, checking if two vertices are adjacent is O(1) in an adjacency matrix but O(degree(v)) in an adjacency list. Consider a social network; an adjacency list would be more suitable due to its sparse nature.

Graph Connectivity: Components and Cut Vertices: Connectivity is a fundamental property of graphs. A connected component is a maximal subgraph in which every pair of vertices is connected by a path. A graph can have one or more connected components. A cut vertex (or articulation point) is a vertex whose removal increases the number of connected components. Similarly, a bridge is an edge whose removal increases the number of connected components. Identifying cut vertices and bridges is crucial for understanding the robustness of a network. Algorithms like Depth-First Search (DFS) and Breadth-First Search (BFS) can be used to find connected components, cut vertices, and bridges in O(V + E) time. Applications include network reliability analysis (identifying critical nodes and links), and identifying clusters in social networks. A key fact is that a connected graph without cut vertices is called a 2-connected graph. A common misconception is that a graph with a high average degree is necessarily highly connected. High degree doesn't guarantee that removing a single vertex won't disconnect the graph.

Eulerian and Hamiltonian Cycles: Traversing Graphs: An Eulerian cycle is a cycle that visits every edge exactly once. A graph has an Eulerian cycle if and only if every vertex has even degree. An Eulerian path is a path that visits every edge exactly once. A graph has an Eulerian path if and only if it has exactly two vertices of odd degree. A Hamiltonian cycle is a cycle that visits every vertex exactly once. Finding a Hamiltonian cycle is an NP-complete problem, meaning there is no known polynomial-time algorithm to solve it. While Eulerian cycles have a simple and efficient characterization, finding Hamiltonian cycles is significantly harder. Applications of Eulerian cycles include DNA sequencing (finding the shortest sequence that covers all fragments), and network routing. Hamiltonian cycles have applications in solving the traveling salesman problem (TSP). A common misconception is that every graph with high connectivity has a Hamiltonian cycle; this is not true.

Planar Graphs: Embedding Graphs on a Plane: A planar graph is a graph that can be drawn on a plane without any edges crossing. Determining whether a graph is planar is a fundamental problem in graph theory. Kuratowski's Theorem states that a graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (the complete graph on 5 vertices) or K3,3 (the complete bipartite graph on 3 vertices on each side). Euler's formula for planar graphs states that v - e + f = 2, where v is the number of vertices, e is the number of edges, and f is the number of faces (regions) in a planar embedding. Planar graphs have applications in circuit board design, map coloring, and graph visualization. A common misconception is that any drawing of a planar graph must be without edge crossings. While a planar graph can be drawn without crossings, existing drawings may have them. Planarity algorithms (e.g., Hopcroft-Tarjan planarity testing) determine if a graph can be drawn without edge crossings.

Graph Coloring: Vertex and Edge Coloring: Graph coloring is the assignment of colors to the vertices or edges of a graph subject to certain constraints. Vertex coloring assigns colors to vertices such that no two adjacent vertices have the same color. The minimum number of colors needed to color a graph is called its chromatic number, denoted by χ(G). Edge coloring assigns colors to edges such that no two adjacent edges have the same color. The minimum number of colors needed to edge-color a graph is called its chromatic index. The Four Color Theorem states that any planar graph can be colored with at most four colors. Graph coloring has applications in scheduling, resource allocation, and map coloring. For example, scheduling exams to avoid conflicts between students taking the same courses can be modeled as a vertex coloring problem. A greedy algorithm can be used to color a graph, but it doesn't necessarily find the optimal coloring. A common misconception is that graph coloring problems are easy to solve; finding the chromatic number of a graph is an NP-hard problem.

Trees: Acyclic Connected Graphs: A tree is a connected graph with no cycles. Trees are fundamental data structures in computer science and graph theory. Key properties of trees include: a tree with n vertices has n-1 edges; there is a unique path between any two vertices in a tree; removing any edge disconnects the tree. A rooted tree has a designated root vertex. Important types of trees include binary trees, spanning trees, and minimum spanning trees. A spanning tree of a graph is a subgraph that is a tree and includes all the vertices of the original graph. A minimum spanning tree (MST) is a spanning tree with the minimum total edge weight. Algorithms like Kruskal's algorithm and Prim's algorithm are used to find MSTs. Trees have applications in hierarchical data representation, decision-making, and network design. A common misconception is that all trees are binary trees. While binary trees are a specific type of tree, the general definition of a tree does not require that each vertex has at most two children.

Shortest Path Algorithms: Dijkstra's and Bellman-Ford: Finding the shortest path between two vertices in a graph is a fundamental problem. Dijkstra's algorithm is a classic algorithm for finding the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights. It uses a greedy approach and has a time complexity of O(E + V log V) using a priority queue. The Bellman-Ford algorithm can handle graphs with negative edge weights, but it cannot handle graphs with negative cycles (cycles where the sum of the edge weights is negative). It has a time complexity of O(V * E). Applications of shortest path algorithms include route planning, network routing, and resource allocation. A common misconception is that Dijkstra's algorithm works correctly for graphs with negative edge weights; it can produce incorrect results in such cases. The Floyd-Warshall algorithm solves the all-pairs shortest path problem in O(V^3) time.

Maximum Flow Algorithms: Ford-Fulkerson and Edmonds-Karp: The maximum flow problem seeks to find the maximum amount of flow that can be sent from a source vertex to a sink vertex in a flow network. A flow network is a directed graph where each edge has a capacity. The Ford-Fulkerson algorithm is a general method for solving the maximum flow problem. It iteratively finds augmenting paths (paths from the source to the sink with available capacity) and increases the flow along these paths. The Edmonds-Karp algorithm is a specific implementation of the Ford-Fulkerson algorithm that uses Breadth-First Search (BFS) to find augmenting paths. It guarantees a polynomial time complexity of O(V E^2). The Max-Flow Min-Cut Theorem* states that the maximum flow in a network is equal to the minimum capacity of a cut (a partition of the vertices into two sets, one containing the source and the other containing the sink). Applications include network bandwidth allocation, transportation planning, and matching problems. A common misconception is that any path from source to sink can be used as an augmenting path. Augmenting paths must have available capacity along all edges in the path.

Matching Problems: Bipartite Matching: A matching in a graph is a set of edges with no shared vertices. A maximum matching is a matching with the largest possible number of edges. A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. The bipartite matching problem seeks to find a maximum matching in a bipartite graph. The Ford-Fulkerson algorithm can be used to solve the bipartite matching problem by converting it into a maximum flow problem. Applications include job assignment, resource allocation, and stable marriage problems. For example, assigning workers to tasks, where each worker is qualified for a subset of the tasks, can be modeled as a bipartite matching problem. A common misconception is that all matchings are equally good. The goal is to find a maximum matching, which may not be unique, but always results in the most possible edges matched.

Directed Acyclic Graphs (DAGs) and Topological Sorting: A directed acyclic graph (DAG) is a directed graph that contains no cycles. DAGs are used to represent dependencies between tasks, scheduling problems, and data flow in computer programs. A topological sort is a linear ordering of the vertices in a DAG such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. Topological sorting can be performed using Depth-First Search (DFS). The algorithm visits each vertex and adds it to the sorted list only after all its descendants have been visited. DAGs and topological sorting have applications in task scheduling, dependency resolution, and compiler optimization. For example, determining the order in which to compile source files in a software project can be modeled as a topological sorting problem. A graph can be topologically sorted if and only if it is a DAG. A common misconception is that a topological sort is unique for a given DAG; there may be multiple valid topological orderings.

NP-Completeness and Graph Problems: Many graph problems are computationally hard. A problem is NP-complete if it is in the class NP (Nondeterministic Polynomial time) and every other problem in NP can be reduced to it in polynomial time. This implies that if a polynomial-time algorithm is found for any NP-complete problem, then every problem in NP can be solved in polynomial time (which is considered highly unlikely). Examples of NP-complete graph problems include the Hamiltonian cycle problem, the graph coloring problem (determining if a graph can be colored with k colors for k > 2), and the maximum clique problem (finding the largest complete subgraph in a graph). Understanding NP-completeness is crucial for designing algorithms for hard graph problems. In practice, approximation algorithms and heuristics are often used to find near-optimal solutions for NP-complete problems. A common misconception is that NP-complete problems are impossible to solve. While finding a polynomial-time exact solution is considered unlikely, approximation algorithms can provide reasonable solutions in a reasonable amount of time.

Browse public study notes