Graph Theory
Graph theory studies the properties of graphs, which are mathematical structures used to model
pairwise relations between objects.
1. Basic Definitions
A graph G = (V, E) consists of a set of vertices V and a set of edges E.
Types of graphs:
- Undirected vs. Directed
- Simple vs. Multigraph
- Connected vs. Disconnected
- Cyclic vs. Acyclic
2. Graph Representation
- Adjacency Matrix
- Adjacency List
- Incidence Matrix
3. Graph Traversal
- Depth-First Search (DFS)
- Breadth-First Search (BFS)
4. Connectivity
- Paths and Cycles
- Eulerian and Hamiltonian Paths/Cycles
5. Trees
A tree is a connected acyclic graph.
Properties:
- A tree with n vertices has n-1 edges
- There is a unique path between any two vertices
6. Planar Graphs
A graph is planar if it can be drawn on a plane without edge crossings.
Euler's Formula: For a connected planar graph, V - E + F = 2, where V is the number of vertices,
E is the number of edges, and F is the number of faces.
7. Graph Coloring
Assigning colors to graph elements (usually vertices or edges) such that no adjacent elements
have the same color.
The Four Color Theorem: Any planar graph can be colored using at most four colors.
Graph theory has numerous applications in computer science, including network design and
analysis.
