Graphs and NetworksIntroduction
Every day we are surrounded by countless connections and networks: roads and rail tracks, phone lines, the internet, electronic circuits and even molecular bonds. There are even social networks between friends and families. Can you think of any other examples?
Road and Rail Networks
Computer Chips
Supply Chains
Friendships
Neural Connections
The Internet
In mathematics, all these examples can be represented as
Graph theory is the study of graphs and their properties. It is one of the most exciting and visual areas of mathematics, and has countless important applications.
We can draw the layout of simple graphs using circles and lines. The position of the vertices and the length of the edges is irrelevant – we only care about how they are connected to each other. The edges can even cross each other, and don’t have to be straight.
In some graphs, the edges only go one way. These are called
Some graphs consist of multiple groups of vertices which are not connected with each other by edges. These graphs are disconnected.
Other graphs may contain multiple edges between the same pairs of vertices, or vertices which are connected to themselves (loops).
We can create new graphs from an existing graph by removing some of the vertices and edges. The result is called a
We say that the
Order:
Order:
Degree:
Degree:
Graphs that consist of a single loop of vertices are called
Equipped with these new definitions, let’s explore some of the fascinating properties and applications of graphs.