Kinds of edges, kinds of networks
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.
The first network has a directed edge, because sharks eat fish and not the other way around - a one-way relationship.
The second network has an undirected edge, because France and Spain share a border - a two-way relationship.
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
- no loops, and
- no two vertices connected by more than one edge
is called a simple network. Most networks we will see will be simple.
The first network is not simple because it has loops. The second network is not simple because there are “repeat” edges between some vertices. The third network is simple - no vertex is connected to itself, and no vertex is connected to any other in more than one way.
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.