Graphs and Networks
Definitions
Graph - A diagram which shows the structure of connections between points. It has vertices (nodes) and edges. It can also have loops and multiple edges.
Simple Graph - A graph with no loops and no multiple edges.
Order (sometimes called degree) - The number of edges connecting to a vertex
Fig 1. A graph
Fig. 1 shows an example of a graph with vertices A, B, C and D:
- Vertex A has an order of 5. We say it is of odd order.
- Vertex B has an order of 3, and it therefore has an odd order.
- Vertex C has an order of 3, and is also of odd order.
- Vertex D also has an order of 3, so is an odd order.
N.B. In any graph or network, there can never be an even number of odd vertices.
Network - A graph whose edges have weights (a numerical value associated with it)
Fig 2. A network
Fig 2. shows an example of a network.
The weighted edges of a network can be anything from the time, e.g. in minutes, that it takes to get from each vertex, to the distance, e.g. in kilometres, between the vertices.
Directed Graph (Digraph) - A graph with directed edges
Fig 3. A digraph
Fig 3. shows an example of a graph with 3 directed edges.
The arrows on a digraph means you can only go that way on that egde of the digraph. A digraph can also be weighted, like in Fig 3.
Complete Graph - If there is exactly one egde joining each pair of vertices. These are known as K3, K4 etc.
Planar - If a graph can be drawn with no edges crossing in 2D. K4 is planar (see Fig. 4 c)).
Fig 4. Three examples of complete graphs
Bi-partite Graph - Vertices are in 2 groups, and the edges only connect vertices from 1 group to vertices in the other group
Fig 5. A bi-partite graph
Tree - A graph with no cycles
Spanning Tree - A tree which connects all the vertices of the graph
Fig 6. Two examples of trees
Traversable - If it is possible to travel around every edge and vertex once and only once.
Eulerian Trail/Cycle - All the vertices are even; start = finish
Semi-Eulerian Trail - There are 2 odd vertices. It is traversible but start does no equal finish
Closed Path/Trail - Starts and ends in the same place
Tour - Each vertex has been visited
Hamiltonian Cycle - A tour which contains every vertex precisely once
Representing Networks by Matrices
A matrix is a rectangular array of numbers, and is an important way of representing networks without having to rely on a diagram.
Fig 7. The network formed by the data in the matrix
| A | B | C | D | |
|---|---|---|---|---|
| A | - | 3 | - | 2 |
| B | 3 | - | 1 | 4 |
| C | - | 1 | - | - |
| D | 2 | 4 | - | - |
For example, if we use the values in the matrix on the right, we can form the network shown in Fig. 7.
Of course, this would not be the only network you could draw from this matrix. As long as the vertices join to the correct vertices, with the correct weights, the network is correct.
Similarly, if we are given the network in Fig 7, we can draw a matrix to represent the network.
Fig 8. The digraph formed by the data in the matrix
| To | |||||
|---|---|---|---|---|---|
| A | B | C | D | ||
| From | A | - | 3 | - | - |
| B | - | - | 1 | 5 | |
| C | - | 1 | - | - | |
| D | 2 | 4 | - | - | |
In order to draw a matrix when given a digraph, we label the columns 'To' and the rows 'From', or vice versa. This way, we can see the direction of the edges and draw a network to show this.
Fig. 8 shows the digraph drawn from the matrix to the right. And once again, this is not the only network that can be drawn from the information in the matrix.
Similarly, we can draw a matrix from the information given in the digraph.