Graph Theory

Graph theory is the study of graphs. A graph is a mathematical structure modeling pairwise relations between objects. In computer science, graphs represent networks, state machines, routing protocols, and data organization.

Formal Definition

A graph $G$ is a pair $(V, E)$:

Vertices ($V$): A set of nodes or points.
Edges ($E$): A set of links or lines connecting pairs of vertices.

An edge connecting vertices $u$ and $v$ is denoted as $e = {u, v}$.

Types of Graphs

Type	Description	Example
Undirected Graph	Edges have no orientation. A connection between $u$ and $v$ goes both ways.	Two-way roads
Directed Graph (Digraph)	Edges have a specific direction, pointing from a source vertex to a destination vertex.	One-way streets, web page links
Weighted Graph	Each edge has an assigned numerical weight or cost.	Distance maps, network routing tables
Complete Graph	Every pair of distinct vertices is connected by a unique edge.	Peer-to-peer networks
Bipartite Graph	Vertices divide into two disjoint sets where every edge connects a vertex in one set to a vertex in the other.	Job matching configurations

Graph Properties

Adjacency: Two vertices are adjacent if an edge connects them.
Degree: The number of edges incident to a vertex. In a digraph, this splits into in-degree (incoming edges) and out-degree (outgoing edges).
Path: A sequence of edges connecting a sequence of vertices.
Cycle: A path that starts and ends on the same vertex without traversing any edge twice.
Acyclic: A graph without any cycles.

Trees

A tree is a connected acyclic undirected graph. A directed acyclic graph is a DAG. Trees function as a foundational data structure in computer science.

Every tree with $n$ vertices has $n - 1$ edges.
Adding one edge to a tree creates a cycle.
Removing one edge from a tree separates it into two disconnected components.