Edges can be either directed or undirected. Directed edges (sometimes called arcs) are represented by arrows and symbolise a one-way relationship, while undirected edges are represented by lines and symbolise a two-way connection.
If there are directed edges in the network, we call the network a directed network (or digraph). If there are no directed edges in a network, we call the network an undirected network. Look back through the networks you’ve seen so far - the ones that have arrows are directed, and the rest are undirected.
Q: What about if there's a mix - some arrowheads, some lines?
A: Edges in undirected networks represent two-way connections. If there are directed edges in a network, then one-way connections are possible - so we turn the lines representing two-way connections into two arrows, like this:
We can still express a two-way connection using directed edges, we just have to draw in an extra (directed) edge. You typically don't see "mixed" networks - it just makes things easier if either all the edges are lines, or all the edges are arrows.
An edge that starts and ends at the same vertex is called a loop. A network that has
is called a simple network. Most networks we will see will be simple.
Here’s a quick summary of the definitions we’ve seen so far in this lesson and the previous one.
Vertex - A circle or dot in a network. Often given a vertex label.
Edge - A line segment connecting a vertex to a vertex. Can be directed (arrowhead) or undirected (no arrowhead). If it starts and ends at the same vertex, we call it a loop.
Network - A collection of vertices and edges. Can be directed (arrowheads) or undirected (no arrowheads). If there are no loops and no “repeat” edges, the network is simple.
Choose appropriate networks to find optimal solutions
Apply network methods in solving problems