Mathematics \ Combinatorics \ Graph Theory
Graph Theory is a fundamental area within the field of combinatorics and mathematics at large. It studies the properties of graphs, which are abstract representations used to model pairwise relations between objects. A graph consists of vertices (also called nodes) and edges (also called links or lines) connecting pairs of vertices. The formal definition of a graph \(G\) is typically given as \(G = (V, E)\), where \(V\) is a non-empty set of vertices, and \(E\) is a set of edges, which are 2-element subsets of \(V\).
Graph theory has a wide range of applications in computer science, biology, transport logistics, social sciences, and more. It provides essential tools for understanding and solving problems in network theory, algorithm design, scheduling, and many other fields.
Core Concepts in Graph Theory
1. Types of Graphs:
- Simple Graphs: These are graphs without loops (edges that connect a vertex to itself) and multiple edges between the same pair of vertices.
- Multigraphs: Graphs that may have multiple edges between the same pair of vertices.
- Directed Graphs (Digraphs): Graphs where each edge has a direction, represented as an ordered pair \((u, v)\) indicating an edge from vertex \(u\) to vertex \(v\).
- Weighted Graphs: Graphs in which each edge has a weight, commonly used to represent networks where the connections have varying strengths or capacities.
2. Degree of a Vertex:
The degree of a vertex is the number of edges incident to it. For directed graphs, we distinguish between in-degree (number of incoming edges) and out-degree (number of outgoing edges).
3. Paths and Cycles:
- A path in a graph is a sequence of vertices where each pair of consecutive vertices is connected by an edge.
- A cycle is a path that begins and ends at the same vertex with no other repeated vertices.
4. Connectivity:
- A graph is connected if there is a path between every pair of vertices.
- A graph is disconnected if it is not connected.
- Components of a graph are maximal connected subgraphs.
5. Bipartite Graphs:
A graph is bipartite if its vertex set \(V\) can be divided into two disjoint sets \(U\) and \(W\) such that every edge connects a vertex in \(U\) to a vertex in \(W\), with no edges within a set.
6. Trees:
A tree is an acyclic connected graph. Important properties of trees include:
- A tree with \(n\) vertices has exactly \(n-1\) edges.
- There is a unique path between any pair of vertices in a tree.
Important Theorems and Concepts
1. Euler’s Theorem:
For a connected graph \(G\), there exists an Eulerian Circuit (a cycle that uses every edge exactly once) if and only if every vertex has an even degree.
2. Hamiltonian Path and Cycle:
A Hamiltonian path is a path that visits every vertex exactly once. A Hamiltonian cycle is a cycle that visits every vertex exactly once and returns to the starting vertex.
3. Planarity and Euler’s Formula:
A graph is planar if it can be drawn on a plane without any edges crossing. Euler’s formula, for a connected planar graph with \(V\) vertices, \(E\) edges, and \(F\) faces, states:
\[
V - E + F = 2
\]
Applications and Computational Problems
Graph theory is used in a multitude of applications, including:
- Shortest Path Problems: Algorithms like Dijkstra’s and Bellman-Ford are used to find the shortest path in weighted graphs.
- Network Flows: Maximizing the flow in a network involves concepts like the Ford-Fulkerson algorithm and the Max-Flow Min-Cut Theorem.
- Graph Coloring: Assigning colors to vertices such that no two adjacent vertices share the same color, important in scheduling problems and register allocation in compilers.
The study of graph theory continues to expand, providing critical insights and powerful techniques for tackling complex problems in various scientific and engineering disciplines.