What is a graph in the context of discrete mathematics, and what is the difference between a directed and an undirected graph?
1 Answer
What is a Graph in Discrete Mathematics?
In simple terms, a graph is a mathematical structure used to model relationships between objects. It consists of two basic components:
- Vertices (or Nodes): These are the "objects" or "points" in the graph.
- Edges (or Links / Arcs): These are the lines that connect pairs of vertices, representing a relationship between them.
Formally, a graph $G$ is defined as an ordered pair $G = (V, E)$, where:
- $V$ is a set of vertices.
- $E$ is a set of edges, where each edge connects two vertices in $V$.
Analogy: Think of a map of airline routes.
The cities are the vertices.
The flights between cities are the edges.
Simple Example
Let's imagine a small social network.
- Vertices (V): A set of people {Alice, Bob, Charles, Diana}.
- Edges (E): A set of friendships {{Alice, Bob}, {Bob, Charles}, {Charles, Alice}, {Charles, Diana}}.
This graph shows that Alice is friends with Bob and Charles, Bob is friends with Alice and Charles, and so on.
Here is a visual representation of that graph:
The Difference: Directed vs. Undirected Graphs
The primary difference lies in whether the relationship represented by the edges has a direction.
1. Undirected Graphs
In an undirected graph, the edges represent a mutual or symmetric relationship. If there is an edge between vertex A and vertex B, the relationship goes both ways. It's a two-way street.
- Edges: An edge is represented as an unordered pair of vertices, like
{A, B}. This means the edge from A to B is the same as the edge from B to A. - Visual Representation: Edges are drawn as simple lines without arrowheads.
- Real-World Example: Facebook Friends. If you are friends with someone on Facebook, they are also friends with you. The relationship is mutual. Other examples include two-way roads between cities or connections in an electrical circuit.
Example of an Undirected Graph:
The social network graph above is a perfect example of an undirected graph. The edge {Alice, Bob} implies a mutual friendship.
2. Directed Graphs (or Digraphs)
In a directed graph, the edges represent a one-way relationship. An edge from vertex A to vertex B does not necessarily mean there is a relationship from B to A. It's a one-way street.
- Edges (often called Arcs): An edge is represented as an ordered pair of vertices, like
(A, B). This means the edge goes from A to B. The edge(A, B)is completely different from the edge(B, A). - Visual Representation: Edges are drawn as arrows to indicate the direction of the relationship.
- Real-World Example: Twitter/Instagram Followers. You can follow someone on Twitter, but they don't have to follow you back. The relationship isn't automatically mutual. Other examples include one-way streets, links from one webpage to another, or the flow of tasks in a project plan.
Example of a Directed Graph:
Let's model a "follows" relationship.
- Vertices (V): {Alice, Bob, Charles, Diana}
- Edges (E): {(Alice, Bob), (Bob, Alice), (Charles, Alice), (Charles, Diana), (Diana, Charles)}
This means:
Alice follows Bob, and Bob follows Alice (a mutual relationship represented by two directed edges).
Charles follows Alice (but Alice does not follow Charles).
* Charles and Diana follow each other.
Here is a visual representation:
Summary Table
| Feature | Undirected Graph | Directed Graph (Digraph) |
| :--- | :--- | :--- |
| Relationship | Symmetric / Two-way | Asymmetric / One-way |
| Edge Notation | Unordered set: {u, v} | Ordered pair: (u, v) |
| Edge Meaning | {u, v} is the same as {v, u} | (u, v) is different from (v, u) |
| Visual | Edges are lines | Edges are arrows (arcs) |
| Classic Example | Facebook Friends | Twitter Followers |
| Use Case | Modeling computer networks, maps of two-way roads | Modeling web links, task dependencies, flowcharts |