3.14 Graph theory: definitions and representation
Studying this course? Keep your progress in one place.
Key facts
- A graph has vertices joined by edges; the degree of a vertex is the number of edges at it.
- The sum of all degrees is the number of edges, so it is always even.
- A tree is a connected graph with no cycles; with vertices it has edges.
- A complete graph on vertices has edges.
- An adjacency matrix records edges; for an undirected graph it is symmetric.
Vertices, edges and degree
A graph is a set of vertices joined by edges, and the degree counts the edges at each vertex.
Two vertices joined by an edge are adjacent vertices; two edges sharing a vertex are adjacent edges. The degree of a vertex is the number of edges meeting at it.
Each edge has two ends, so the sum of all degrees is twice the number of edges. It is always even.
For edges , , , , : degrees are and .
A graph has 7 edges. What is the sum of the degrees?
Types of graph
Simple, complete and weighted graphs differ in which edges are allowed and whether edges carry numbers.
A simple graph has no loops and no repeated edges between the same pair of vertices. A complete graph on vertices joins every pair, so it has edges: 10 for 5 vertices and 15 for 6.
A weighted graph gives each edge a number (a distance, cost or time); an unweighted graph does not.
To model a situation, make objects vertices and connections edges: computers and cables, towns and roads, sensors and links.
How many edges does a complete graph on 6 vertices have?
Connected graphs and trees
A tree is connected with no cycles, so vertices need exactly edges.
A graph is connected if there is a path between every pair of vertices. A subgraph uses some of the vertices and edges of a graph.
A tree is a connected graph with no cycles. In the sensor network, , , , form a subgraph that is a tree: 5 vertices, 4 edges. The whole network is connected but not a tree, because –– is a cycle.
Deleting vertex leaves with no edge, so the rest is not connected.
A tree has 9 vertices. How many edges does it have?
Directed graphs
In a directed graph each edge goes one way, and vertices have an in-degree and an out-degree.
In a directed graph each edge has a direction , like a one-way street. The out-degree counts edges leaving a vertex and the in-degree counts edges entering. Both sums equal the number of edges.
One-way streets , , , , give out-degree 2 and in-degree 1, and in-degree 2. The cycle reaches every vertex, so the graph is strongly connected.
Which is true for the sums over all vertices of a directed graph?
Adjacency matrices
An adjacency matrix has a row and column per vertex, with entries counting the edges between them.
For the sensor network (order ):
An adjacency matrix of an undirected graph is symmetric, and each row sum is the degree of that vertex (). In a simple graph the diagonal is 0 and other entries are 0 or 1. For a directed graph, entry counts edges from to , so the matrix need not be symmetric.
| Undirected | Directed | |
|---|---|---|
| Matrix | Symmetric | Need not be symmetric |
| Feature | Row sum = degree | Entry : edges |
Undirected
- Matrix:
- Symmetric
- Feature:
- Row sum = degree
Directed
- Matrix:
- Need not be symmetric
- Feature:
- Entry : edges
A row of an undirected adjacency matrix is . What is the degree of that vertex?
Try an exam question
A graph has vertices and edges , , , , . (a) Write down the degree of each vertex. (b) Show that the sum of the degrees is twice the number of edges. (c) Explain why the graph is not a tree.
[4 marks]
- [1]Degrees: , , , , .
- [1]Sum of degrees .
- [1]There are 5 edges and .
- [1]–– is a cycle (a tree on 5 vertices has only 4 edges), so it is not a tree.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Write down the degree of vertex .
1 mark, marked against the mark scheme
Write down the degree of vertex .
1 mark, marked against the mark scheme