An introduction to graphs
Introduction
In Maths, a graph is a representation of a set of objects. The objects are called vertices. Some pairs of vertices are connected together by links, which are known as edges. A pair of vertices conected together by an edge is known as a neighbour. Some vertices are connected to more than one vertex and the degree of a vertex tells us how many other vertices it is connected to. In Maths, the edges are usually weighted, or given a value that represents an abstract amount.
An example of a graph might include a map. The towns and cities represent the vertices and the roads that link them represent the edges. Another example would be the routers on the Internet. Routers are like post offices, that spend their day forwarding packets of data on the Internet on to their destination. A router does this by forwarding each packet to another router closer to where the packet needs to go, until eventually, the packets arrive at their destination. The routers are the vertices and the interconnections between the routers are the edges. Other uses of graphs include describing social networks, water supply pipes, electrical cable routes, transportation routes, train routes and many more. In fact, they can be used to describe many different types of relationships.
When you have a web of vertices interconnected like this, you often need to know the shortest path from one place (vertex) in the graph to another vertex in the graph, as there are clearly many different paths that could be taken. If you can find the edges from one vertex to another that have the smallest weighting, then you have identified the shortest route. If you can identify the shortest route, you can maximise the resources by, for example, reducing the time that any communication takes or reducing how much searching needs to be done. The Dijkstra's algorithm is an algorithm that identifies the shortest path between two vertices and we have discussed this algorithm in detail here.
Consider this example of graph:
You can see that each vertex is represents a town or city. Coventry is neighbours with Norwich, Stirling and Hull. There is an edge between Coventry and Norwich, Coventry and Stirling and Coventry and Hull, as well as edges between other neighbouring vertices. Coventry has a degree of 3 whereas Bristol has a degree of 1 and London has a degree of 4. The weighting between Plymouth and Bristol, for example, is 6 whereas the weighting between London and Glasgow is 10.
We don't know what they weightings represent because we haven't been told. They might represent the cost of transport between two places, or the travel time by train between two places, or some other value that we are investigating. This type of graph is known as an undirected graph, because the weightings are the same in both directions. There are no arrows on the graph. We could modify the diagram by adding arrows and weightings for different directions. It then becomes a directed graph. you can see this in the example below.
Simple graphs
A 'simple graph' is an undirected graph in which there are no edges to and from the same vertex (called a loop) and there is a maximum of one edge between any two given vertices. Consider the following undirected graphs:
This is not a simple graph. India has a loop for some reason, and there is more than one edge between the UK and Egypt.
This is a simple graph because it meets the three condidtions for the definition; it is undirected, there are no loops and there is a maximum of one edge between any two vertices.