What do roads, human ancestry, currency exchange, planning a wedding, and the internet have in common? They are all things that we can represent with a mathematical object called a network. Studying networks will allow us to gain deep insights into any system, place, or thing that is defined by its connections.
You have seen networks before, all around you! We are now going to learn how to recognise them, represent them in a consistent way, then analyse them. But first, we need to start with the language of networks to introduce the key concepts.
This subject is notorious for using many different words to refer to the same thing. This reflects the rich history of the subject, and its accessibility - networks have been studied by people all over the world in many different ways, and nobody agrees on a standard way to talk about them.
The concepts are the most important thing to remember, much more than the name that we give it. We have included alternate terminology that may be more familiar to you, but they will appear only once.
A vertex (or node) is the fundamental building block of a network and represents a single object or idea. It is drawn as a dot or circle. The plural of vertex is vertices.
An edge (or arc) is a line segment that begins and ends at a vertex. An edge represents a relationship between the objects or ideas that it links together, and the kind of relationship it represents depends on the context.
On the left is a single vertex. On the right there are two vertices with one edge between them.
On the left is a single vertex. On the right there are two vertices with one edge between them.
An edge must be drawn between exactly two vertices. Neither of these are valid edges:
An edge can’t connect at only one end, and can’t connect more than two vertices together.
A network (sometimes called a network graph, or just graph) is a collection of vertices with edges drawn between them.
Four different networks.
Let’s take a moment and notice a few things about these networks.
- Some edges have direction (they look like arrows), and some don’t.
- Sometimes a vertex is connected to itself by an edge.
- Sometimes vertices are connected to another vertex by more than one edge.
- One of the networks has numbered edges.
Keep these observations in mind - we will address each of them in the coming lessons.
Here are three more networks - these have letters or words for each vertex.
Three more networks with extra detail.
Vertices in networks are often given vertex labels. These labels can be something specific (the name of a person, city, or animal...) or it can be more abstract, like a capital letter. In the networks above, the first one has capital letters for labels, which is useful for pointing out a particular vertex to someone else. The other two networks have labels that tell us what is being represented.