Common Types of Graphs
Graphs come in many shapes and sizes, each with unique properties that make them suitable for modeling different kinds of systems. Let’s explore some of the most common types.
1. Undirected Graphs
An undirected graph is a graph where edges have no orientation. The relationship between two vertices is symmetric. If an edge connects vertex A to vertex B, it also connects B to A. Our social network example is an undirected graph because friendship is mutual.
2. Directed Graphs (Digraphs)
In a directed graph (or digraph), every edge has a direction, pointing from a source vertex to a target vertex. These are perfect for modeling asymmetric relationships.
Example: One-Way Streets
Imagine a small downtown area with one-way streets.
- Vertices: Intersections A, B, and C.
- Edges: One-way streets. There’s a street from A to B, from B to C, and from C back to A.
The edge set E would be E = {(A, B), (B, C), (C, A)}. We use parentheses here to denote order: (A, B) is different from (B, A).
This creates a one-way traffic loop, which you can see in the visualization below. The arrows indicate the direction of flow.
3. Weighted Graphs
A weighted graph is a graph where each edge is assigned a numerical value, or weight. This weight can represent various metrics like distance, cost, time, or capacity.
Example: A Road Map
Consider a map connecting a few major cities.
- Vertices: New York, Chicago, and Los Angeles.
- Edges: The flight paths connecting them.
- Weights: The flight time in hours.
- New York to Chicago: 2 hours
- Chicago to Los Angeles: 4 hours
- New York to Los Angeles: 5 hours
Weighted graphs are crucial for solving optimization problems, such as finding the shortest path between two points.
4. Complete Graphs
A complete graph is an undirected graph where every distinct pair of vertices is connected by a unique edge. A complete graph with \(n\) vertices is denoted as \(K_n\).
For example, here is a complete graph with 4 vertices \(K_4\). Notice that each of the 4 vertices is connected to the other 3 vertices.
5. Bipartite Graphs
A bipartite graph is an undirected graph whose vertices can be divided into two disjoint and independent sets, \(U\) and \(V\), such that every edge connects a vertex in \(U\) to one in \(V\). There are no edges between vertices within the same set.
Example: Job Applicants and Positions
- Set \(U\) (Applicants): {Alice, Bob, Carol}
- Set \(V\) (Positions): {Developer, Designer, Manager}
- Edges: A line from an applicant to a position means they are qualified for that role.
6. Trees
A tree is a special type of undirected graph that is connected and has no cycles. This structure is fundamental in computer science, used for things like file systems and representing hierarchical data.
A key property is that in a tree with \(n\) vertices, there are always exactly \(n-1\) edges.