The Central Idea
An undirected graph represents relationships with no preferred direction.
A directed graph, or digraph, represents relationships that point from one vertex to another.
The distinction can be summarized by the edge notation
\[ \boxed{\{u,v\}\text{ for an undirected edge}} \]and
\[ \boxed{(u,v)\text{ for a directed edge from }u\text{ to }v}. \]Undirected Edges
In an undirected graph, an edge joins two vertices symmetrically.
If
\[ \{u,v\}\in E, \]then \(u\) is connected to \(v\) and \(v\) is connected to \(u\).
Because sets are unordered,
\[ \boxed{\{u,v\}=\{v,u\}}. \]Directed Edges
A directed edge has an orientation. It begins at one vertex and points to another.
The directed edge
\[ (u,v) \]points from \(u\) to \(v\).
In general,
\[ \boxed{(u,v)\ne(v,u)}. \]Tail and Head
For a directed edge
\[ (u,v), \]the starting vertex \(u\) is called the tail, and the destination vertex \(v\) is called the head.
Thus,
\[ \boxed{u\longrightarrow v}. \]Visual Comparison
An undirected edge is usually drawn as a line. A directed edge is usually drawn with an arrow.
Why Direction Matters
Direction changes the meaning of a connection.
If a road permits travel in both directions, an undirected edge may be appropriate. If a street permits travel only from \(A\) to \(B\), the directed edge
\[ (A,B) \]records that restriction.
The reverse movement would require a separate directed edge
\[ (B,A). \]Examples of Undirected Relationships
Undirected graphs are useful when the modeled relationship is naturally symmetric.
- two rooms connected by an unrestricted doorway;
- two computers linked by a symmetric physical connection;
- two people recorded as mutual collaborators;
- two locations joined by a two-way route;
- two objects that share a specified property.
The modeling decision should match the actual relationship being studied.
Examples of Directed Relationships
Directed graphs are useful when the relationship has an origin and a destination.
- a web page linking to another page;
- a person following another account;
- a one-way road;
- a task that must precede another task;
- a citation from one document to another;
- a transition from one system state to another.
A First Undirected Graph
Let
\[ V=\{a,b,c,d\} \]and
\[ E= \bigl\{ \{a,b\},\{a,c\},\{b,d\} \bigr\}. \]Since the edges are undirected, \(\{a,b\}\) represents the same connection as \(\{b,a\}\).
A First Directed Graph
Now let
\[ V=\{a,b,c,d\} \]and
\[ E= \bigl\{ (a,b),(a,c),(b,d) \bigr\}. \]These edges mean
\[ a\to b,\qquad a\to c,\qquad b\to d. \]No reverse directions are implied.
One Directed Edge Does Not Imply Its Reverse
If
\[ (a,b)\in E, \]we may move along that edge from \(a\) to \(b\).
But unless
\[ (b,a)\in E, \]the graph does not also contain an edge from \(b\) to \(a\).
Two Opposite Directed Edges
A directed graph may contain both
\[ (u,v) \]and
\[ (v,u). \]Together they represent two directed connections, one in each direction. They are still two distinct edges in a directed model.
Reciprocal Connections
When both
\[ (u,v)\in E \]and
\[ (v,u)\in E, \]the pair of vertices has a reciprocal or mutual directed relationship.
Reciprocal edges are common in communication and social-network models.
Adjacency in an Undirected Graph
In an undirected graph, vertices \(u\) and \(v\) are adjacent when
\[ \{u,v\}\in E. \]The relationship is symmetric:
\[ u\text{ adjacent to }v \quad\Longleftrightarrow\quad v\text{ adjacent to }u. \]Adjacency in a Directed Graph
Direction requires more precise language. In this lesson, if
\[ (u,v)\in E, \]we say that \(v\) is an out-neighbor of \(u\), and \(u\) is an in-neighbor of \(v\).
This terminology avoids treating a one-way relationship as if it were symmetric.
Out-Neighborhood
The out-neighborhood of \(u\) is the set of vertices that receive a directed edge from \(u\).
\[ \boxed{N^+(u)=\{v:(u,v)\in E\}}. \]If
\[ E=\{(a,b),(a,c),(c,a)\}, \]then
\[ N^+(a)=\{b,c\}. \]In-Neighborhood
The in-neighborhood of \(u\) is the set of vertices that send a directed edge into \(u\).
\[ \boxed{N^-(u)=\{v:(v,u)\in E\}}. \]For
\[ E=\{(a,b),(a,c),(c,a)\}, \]we have
\[ N^-(a)=\{c\}. \]Degree in an Undirected Graph
In a simple undirected graph, the degree of a vertex counts all incident edges.
\[ \deg(v)=\text{number of edges incident with }v. \]There is no need to distinguish incoming from outgoing edges because the edges have no direction.
Out-Degree
In a directed graph, the out-degree of \(v\), written \(\deg^+(v)\), counts directed edges whose tail is \(v\).
\[ \boxed{\deg^+(v)=\text{number of edges leaving }v}. \]In a simple digraph without loops,
\[ \deg^+(v)=|N^+(v)|. \]In-Degree
The in-degree of \(v\), written \(\deg^-(v)\), counts directed edges whose head is \(v\).
\[ \boxed{\deg^-(v)=\text{number of edges entering }v}. \]In a simple digraph without loops,
\[ \deg^-(v)=|N^-(v)|. \]Example: In-Degree and Out-Degree
Let
\[ E= \bigl\{ (a,b),(a,c),(b,c),(c,a),(d,c) \bigr\}. \]For vertex \(a\), the outgoing edges are
\[ (a,b),\qquad(a,c), \]so
\[ \deg^+(a)=2. \]The only incoming edge is \((c,a)\), so
\[ \deg^-(a)=1. \]Directed Degree Table
For
\[ E= \bigl\{ (a,b),(a,c),(b,c),(c,a),(d,c) \bigr\}, \]the degrees are
| Vertex | In-degree \(\deg^-\) | Out-degree \(\deg^+\) |
|---|---|---|
| \(a\) | 1 | 2 |
| \(b\) | 1 | 1 |
| \(c\) | 3 | 1 |
| \(d\) | 0 | 1 |
Total Directed Degree at a Vertex
When useful, we may combine incoming and outgoing incidences:
\[ \boxed{\deg(v)=\deg^-(v)+\deg^+(v)}. \]For vertex \(c\) in the previous example,
\[ \deg(c)=3+1=4. \]When working with digraphs, however, keeping in-degree and out-degree separate usually preserves more information.
The Directed Degree-Sum Rules
Every directed edge contributes exactly \(1\) to one out-degree and exactly \(1\) to one in-degree.
Therefore, for a finite directed graph,
\[ \boxed{\sum_{v\in V}\deg^+(v)=|E|} \]and
\[ \boxed{\sum_{v\in V}\deg^-(v)=|E|}. \]Consequently,
\[ \sum_{v\in V}\left(\deg^-(v)+\deg^+(v)\right)=2|E|. \]Example: Checking Directed Degrees
The example graph contains five directed edges.
Its out-degrees sum to
\[ 2+1+1+1=5, \]while its in-degrees sum to
\[ 1+1+3+0=5. \]Both totals equal
\[ |E|=5. \]Sources and Sinks
In a directed graph, a vertex with no incoming edges has
\[ \deg^-(v)=0. \]Such a vertex is often called a source when it has outgoing edges.
A vertex with no outgoing edges has
\[ \deg^+(v)=0. \]Such a vertex is often called a sink when it has incoming edges.
Example: Source and Sink
Let
\[ E=\{(p,q),(p,r),(q,s),(r,s)\}. \]Vertex \(p\) has
\[ \deg^-(p)=0,\qquad \deg^+(p)=2, \]so \(p\) is a source.
Vertex \(s\) has
\[ \deg^-(s)=2,\qquad \deg^+(s)=0, \]so \(s\) is a sink.
Directed Adjacency Lists
A directed adjacency list usually records outgoing neighbors.
For
\[ E=\{(a,b),(a,c),(b,c),(c,a)\}, \]the outgoing adjacency list is
- \(a:\ b,c\)
- \(b:\ c\)
- \(c:\ a\)
Each row records where a directed edge can go from that vertex.
Directed Adjacency Matrices
For a directed graph, define
\[ A_{ij}= \begin{cases} 1,&\text{if }(v_i,v_j)\in E,\\ 0,&\text{otherwise}. \end{cases} \]The row identifies the tail, and the column identifies the head.
Unlike the adjacency matrix of a simple undirected graph, a directed adjacency matrix does not have to be symmetric.
Example: Directed Adjacency Matrix
Let
\[ E=\{(a,b),(a,c),(b,c),(c,a)\}. \]Using vertex order \(a,b,c\),
\[ A= \begin{pmatrix} 0&1&1\\ 0&0&1\\ 1&0&0 \end{pmatrix}. \]The entry in row \(a\), column \(b\) is \(1\) because \(a\to b\). The entry in row \(b\), column \(a\) is \(0\) because \(b\to a\) is absent.
Degrees from a Directed Adjacency Matrix
In a simple directed graph without loops:
- the sum of row \(i\) gives \(\deg^+(v_i)\);
- the sum of column \(i\) gives \(\deg^-(v_i)\).
For
\[ A= \begin{pmatrix} 0&1&1\\ 0&0&1\\ 1&0&0 \end{pmatrix}, \]the first row sums to \(2\), so \(\deg^+(a)=2\). The first column sums to \(1\), so \(\deg^-(a)=1\).
Symmetry in an Undirected Adjacency Matrix
In a simple undirected graph,
\[ \{v_i,v_j\}\in E \]implies the same connection when the endpoints are reversed.
Therefore,
\[ A_{ij}=A_{ji}. \]The adjacency matrix is symmetric:
\[ \boxed{A=A^{T}}. \]Direction Can Change Reachability
Suppose a directed graph contains
\[ a\to b\to c. \]Following the arrows allows movement from \(a\) to \(c\) through \(b\).
The same edges do not necessarily allow movement from \(c\) back to \(a\).
This asymmetry becomes important when we study directed paths and connectivity.
Converting Direction into an Undirected View
Sometimes we care only whether two vertices have some directed connection, not which way it points.
In that case we can form an underlying undirected graph by replacing directed connections between distinct vertices with undirected edges.
For example,
\[ (a,b),\qquad(b,c),\qquad(c,a) \]become
\[ \{a,b\},\qquad\{b,c\},\qquad\{a,c\}. \]Direction Contains Additional Information
Converting a directed graph to an undirected graph can discard information.
The two directed graphs
\[ a\to b \]and
\[ a\leftarrow b \]have the same underlying undirected edge
\[ \{a,b\}. \]Once the arrow is removed, the original direction cannot be recovered from the undirected graph alone.
Choosing the Correct Graph Type
Before constructing a graph, ask what the edge is supposed to mean.
If the relationship is symmetric, an undirected graph may be appropriate. If the relationship has a source and destination, use a directed graph.
A technically correct graph with the wrong edge type can still be a poor model of the real system.
Example: Transportation
Suppose intersections are vertices.
A two-way street between intersections \(A\) and \(B\) can be modeled by
\[ \{A,B\}. \]A one-way street from \(C\) to \(D\) should instead be modeled by
\[ (C,D). \]Using one notation for both would conceal an operational difference in the network.
Example: Dependency Network
Suppose task \(A\) must be completed before task \(B\), and task \(B\) before task \(C\).
A natural directed model is
\[ A\to B\to C. \]Replacing these arrows with undirected edges would lose the precedence information.
Example: Communication Network
If a communication link allows messages in both directions, it may be modeled as an undirected edge.
If messages can flow only from one node to another, a directed edge is more appropriate.
The mathematical form should reflect the actual permitted flow.
Common Error: Reversing an Ordered Edge
In a directed graph,
\[ (u,v) \]and
\[ (v,u) \]are different edges.
Never reverse a directed edge unless the reverse edge is actually present.
Common Error: Using Set Notation for Direction
The notation
\[ \{u,v\} \]does not encode direction because
\[ \{u,v\}=\{v,u\}. \]Use an ordered pair such as \((u,v)\), or an arrow \(u\to v\), when direction matters.
Common Error: Counting In-Degree as Out-Degree
If
\[ a\to b, \]then this edge contributes \(1\) to
\[ \deg^+(a) \]and \(1\) to
\[ \deg^-(b). \]It does not contribute to \(\deg^-(a)\) or \(\deg^+(b)\).
Common Error: Assuming Directed Matrices Are Symmetric
If \(A_{ij}=1\) in a directed adjacency matrix, then
\[ v_i\to v_j. \]This does not imply
\[ v_j\to v_i. \]Therefore \(A_{ji}\) may be \(0\).
Common Error: Losing Information during Conversion
Turning a directed graph into an undirected graph can be useful, but it removes orientation.
Do not use the resulting undirected graph to infer which directions were present in the original network.
A Reliable Procedure for Classifying a Graph
- Identify what each vertex represents.
- Identify what each edge represents.
- Ask whether the relationship is symmetric.
- If direction is irrelevant, use undirected edges.
- If source and destination matter, use directed edges.
- For a digraph, distinguish incoming from outgoing neighbors.
- Compute in-degree and out-degree separately.
- Check that total in-degree and total out-degree each equal \(|E|\).
Example: Full Directed-Graph Workflow
Let
\[ V=\{p,q,r,s\} \]and
\[ E= \bigl\{ (p,q),(p,r),(q,r),(r,p),(r,s) \bigr\}. \]The out-neighborhood of \(r\) is
\[ N^+(r)=\{p,s\}, \]while the in-neighborhood is
\[ N^-(r)=\{p,q\}. \]Therefore,
\[ \deg^+(r)=2,\qquad \deg^-(r)=2. \]Across all vertices, the in-degrees sum to \(5\), the out-degrees sum to \(5\), and
\[ |E|=5. \]Practice 1: Classify the Relationship
A network records one-way streets between intersections.
Should its edges generally be directed or undirected?
Practice 2: Read a Directed Edge
What does
\[ (a,b) \]mean in a directed graph?
Practice 3: Reverse Direction
If \((a,b)\in E\), does it follow that \((b,a)\in E\)?
Practice 4: Out-Neighborhood
Let
\[ E=\{(a,b),(a,c),(b,c),(c,a),(d,c)\}. \]Find \(N^+(a)\).
Practice 5: In-Neighborhood
Using the same graph, find \(N^-(c)\).
Practice 6: In-Degree and Out-Degree
Using
\[ E=\{(a,b),(a,c),(b,c),(c,a),(d,c)\}, \]find \(\deg^-(c)\) and \(\deg^+(c)\).
Practice 7: Source and Sink
Let
\[ E=\{(p,q),(p,r),(q,s),(r,s)\}. \]Identify a source and a sink.
Practice 8: Degree-Sum Check
A directed graph has \(7\) edges.
What must the sum of all in-degrees be? What must the sum of all out-degrees be?
Practice 9: Directed Adjacency Matrix
Let
\[ E=\{(1,2),(1,3),(3,2)\}. \]Using vertex order \(1,2,3\), write the adjacency matrix.
Practice 10: Identify the Error
A student sees the directed edge
\[ x\to y \]and says, “\(x\) and \(y\) are connected, so I may travel along the same edge from \(y\) to \(x\).”
Explain the error.
Practice Answers
Practice 1
The streets are one-way, so direction matters.
\[ \boxed{\text{Use directed edges.}} \]Practice 2
The ordered pair
\[ (a,b) \]represents a directed edge whose tail is \(a\) and whose head is \(b\):
\[ \boxed{a\to b}. \]Practice 3
No. Directed edges are ordered:
\[ \boxed{(a,b)\not\Rightarrow(b,a)}. \]Practice 4
The edges leaving \(a\) are \((a,b)\) and \((a,c)\). Therefore,
\[ \boxed{N^+(a)=\{b,c\}}. \]Practice 5
The edges entering \(c\) are
\[ (a,c),\qquad(b,c),\qquad(d,c). \]Therefore,
\[ \boxed{N^-(c)=\{a,b,d\}}. \]Practice 6
Three edges enter \(c\), and one edge leaves \(c\):
\[ \boxed{\deg^-(c)=3,\qquad \deg^+(c)=1}. \]Practice 7
Vertex \(p\) has no incoming edges and has outgoing edges, so it is a source.
Vertex \(s\) has incoming edges and no outgoing edges, so it is a sink.
\[ \boxed{p\text{ is a source},\qquad s\text{ is a sink}.} \]Practice 8
Every directed edge contributes once to the in-degree total and once to the out-degree total. Therefore,
\[ \boxed{\sum\deg^-(v)=7,\qquad \sum\deg^+(v)=7}. \]Practice 9
Using vertex order \(1,2,3\),
\[ \boxed{ A= \begin{pmatrix} 0&1&1\\ 0&0&0\\ 0&1&0 \end{pmatrix} }. \]Practice 10
The arrow \(x\to y\) permits the directed relationship from \(x\) to \(y\). It does not create the reverse edge.
Travel from \(y\) to \(x\) along a directed edge would require
\[ \boxed{y\to x} \]to be present separately.
What to Remember
- An undirected edge has no preferred orientation.
- \(\{u,v\}=\{v,u\}\) for an undirected edge.
- A directed edge \((u,v)\) points from \(u\) to \(v\).
- In general, \((u,v)\ne(v,u)\).
- \(\deg^+(v)\) counts edges leaving \(v\).
- \(\deg^-(v)\) counts edges entering \(v\).
- For a finite digraph, total out-degree and total in-degree both equal \(|E|\).
- Directed adjacency matrices need not be symmetric.
- The graph type should reflect whether the modeled relationship is symmetric or directional.
Where We Go Next
So far, edges have recorded whether a connection exists and, when appropriate, which way it points.
Many networks also attach a numerical value to an edge, such as distance, cost, time, capacity, or risk.
The next lesson, Weighted Graphs, introduces those numerical edge values and shows how they enrich a graph model.