Introduction to Graphs
What Is a Graph?
A graph is a structure made of vertices (nodes) connected by edges (links). Graphs model relationships in almost every field: social networks, transportation, circuits, scheduling, and more.
Types of Graphs
| Type | Description |
|---|---|
| Simple Graph | No multiple edges between the same pair; no self-loops. |
| Multigraph | Allows multiple edges between the same pair of vertices. |
| Directed Graph (Digraph) | Edges have direction (arrows); relation goes one way. |
| Undirected Graph | Edges have no direction; relation is two-way. |
| Connected Graph | There is a path between any two vertices. |
| Disconnected Graph | At least one pair of vertices has no path between them. |
| Weighted Graph | Edges are assigned numerical values. |
Graph Terminology
| Term | Definition |
|---|---|
| Vertex | A node or point in the graph. |
| Edge | A connection between two vertices. |
| Adjacent | Two vertices connected by an edge. |
| Degree (deg(v)) | Number of edges incident on vertex v. |
| In-degree | Number of directed edges arriving at a vertex. |
| Out-degree | Number of directed edges leaving a vertex. |
| Loop | An edge that connects a vertex to itself. Contributes 2 to degree. |
| Path | A sequence of vertices connected by edges. |
| Simple Path | A path with no repeated vertices. |
| Circuit | A path that starts and ends at the same vertex. |
Note: degree = in-degree + out-degree (for directed graphs)
The Handshaking Theorem
For any undirected graph G = (V, E) with m edges:
Sum of all deg(v) = 2m
The sum of all vertex degrees equals twice the number of edges.
Corollary: An undirected graph always has an even number of vertices with odd degree.
Example: A graph with 10 vertices each of degree 6: Sum of degrees = 6 × 10 = 60 = 2m → m = 30 edges.
Representing Graphs
Adjacency Matrix
An n × n matrix where entry (i, j) = 1 if there is an edge from vertex i to vertex j, and 0 otherwise.
- For undirected graphs, the matrix is symmetric.
Adjacency List
Each vertex stores a list of its neighbors. More space-efficient for sparse graphs.
Trees
A tree is a connected, acyclic graph — it has no simple circuits.
Properties:
- A tree with n vertices has exactly n − 1 edges.
- There is exactly one path between any two vertices.
Types of Trees
| Type | Description |
|---|---|
| General Tree | Each vertex can have any number of children. |
| Rooted Tree | A directed tree with exactly one root (in-degree 0). |
| External Node (Leaf) | A vertex with out-degree 0 (no children). |
| Internal Node | A vertex with out-degree ≥ 1 (has at least one child). |
Real-World Applications of Graphs
- Social Networks: Vertices = people; edges = connections/friendships.
- Transportation Networks: Vertices = stops/locations; edges = routes. (Used in GPS mapping.)
- Network Security: Vertices = IP addresses; edges = data packets.
- Compilers: Used for data flow analysis and code optimization.
- Robot Planning: Vertices = robot states; edges = transitions between states.
Exercises — Introduction to Graphs
ProReviewer — locked
Drills, code labs, and full solutions.