Graphs and Networks

Question 1

What does a graph consist of

Answer 1

Points (vertices/nodes), the list of which may be referred to as the vertex set
Lines (edges/arcs), the list of which may be referred to as the edge set

Question 2

Weighted graph or network

Answer 2

If a graph has a number (weight) associated with each edge

Question 3

Subgraph of G

Answer 3

A graph, each of whose vertices belong to G and each of whose edges belong to G

A part of the original graph

Question 4

The number of edges incident to a vertex

Answer 4

Degree/valency/order
A loop counts as 2
A vertex has either odd or even degree

Question 5

Walk

Answer 5

A finite sequence of arcs such that the end vertex of one arc is the start vertex of the next

Question 6

Path

Answer 6

A walk in which no vertex appears more than once

Question 7

Trail

Answer 7

A walk in which no edge is visited more than once

Question 8

Cycle/circuit

Answer 8

A closed path - finishes at the start vertex

Question 9

Hamiltonian cycle

Answer 9

A cycle that visits every vertex exactly once

Question 10

When is a graph connected?

Answer 10

If all its vertices are connected

Question 11

Loop

Answer 11

An edge which starts and finishes at the same vertex

Question 12

Simple graph

Answer 12

One with no loops and no more than one edge connecting any pair of vertices

Question 13

Directed edges

Answer 13

Where the edges have a direction associated to them

Known as a digraph

Question 14

Euler’s handshaking lemma

Answer 14

In any undirected graph, the sum of the degrees of the vertices is equal to 2x the amount of edges. As a consequence, the number of odd vertices must be even, including possibly zero.

Question 15

Tree

Answer 15

A connected graph with no cycles

Question 16

Spanning tree of a graph

Answer 16

A subgraph which includes all the vertices of a graph and is also a tree

Question 17

Complete graph

Answer 17

A graph in which every vertex is connected by a single edge to every other vertex
Symbolised by K
no. of nodes

Question 18

Isomorphic graphs

Answer 18

Have the same number of vertices of the same degree connected differently

Question 19

Adjacency matrix

Answer 19

A table which shows the amount of connections between the vertices of a graph. Each entry describes the number of arcs joining the corresponding vertices

Question 20

How many connections is a loop?

Answer 20

2

Question 21

Distance matrix

Answer 21

The matrix associated with a weighted graph, the entries represent the weight of each arc, not the number, only write the weight if an edge connects them, no paths

Question 22

Matrix for a directed graph

Answer 22

The values in the matrix represent the distance from the value on the left to the one on the top

Question 23

Planar graph

Answer 23

One that can be drawn in a plane such that no two edges meet except at a vertex

Question 24

When can you use the planarity algorithm?

Answer 24

When a graph contains a Hamiltonian cycle

Question 25

Planarity algorithm setup

Answer 25

1. Find a Hamiltonian cycle
2. Draw a regular polygon with a neighbouring vertex for each connected vertices in the Hamiltonian cycle
3. Draw the edges that weren’t in the Hamiltonian cycle inside the polygon
4. Draw the polygon again with no edges inside
5. Make a key to highlight the lines on the original polygon depending on whether they go on the inside or the outside.

Question 26

Planarity algorithm execution

Answer 26

6. Draw one edge from the first polygon on the inside of the second
7. Note that line with an (i) next to it and then note any that cross that line with an (o) next to them and draw on the outside of the second polygon, ticking next to the note of the original line
8. Work down the list noting any that cross the next line as in the opposite region to them
9. Repeat until all lines have been drawn and ticked or it doesn’t work at which stage it isn’t planar