2. Graphs and Networks

Question 1

What does a graph consist of?

Answer 1

Points called vertices or nodes

Lines called edges or arcs

Question 2

What is a weighted graph or network?

Answer 2

A graph that has a number associated with each edge (usually known as weight)

Question 3

What is a subgraph?

Answer 3

A part of the original graph

Question 4

What is the degree of a vertex also known as?

Answer 4

1. Order

2. Valency

Question 5

What is the degree of a vertex?

Answer 5

The number of edges incident to it

Question 6

Define the term walk

Answer 6

A route through a graph along edges from one vertex to the next

Question 7

Define the term path

Answer 7

A walk in which no vertex is visited more than once

Question 8

Define the term trail

Answer 8

A walk in which no edge is visited more than once

Question 9

Define the term cycle

Answer 9

A walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once

Question 10

What is a Hamiltonian cycle?

Answer 10

A cycle that includes every vertex

Question 11

What is a connected graph?

Answer 11

A graph where all vertices are connected

Question 12

Define the term loop

Answer 12

An edge that starts and finishes at the same vertex

Question 13

What is a simple graph?

Answer 13

A graph that has no loops and only one edge connecting any pair of vertices

Question 14

What is a directed graph (digraph)?

Answer 14

A graph which has directed edges (edges that have a direction associated with them)

Question 15

What is the relationship between the sum of the degrees of the vertices and the number of edges in an undirected graph?

Answer 15

sum of degrees of vertices = 2 x number of edges

This means the number of odd vertices must be even

Question 16

What is Euler’s handshaking lemma?

Answer 16

sum of degrees of vertices = 2 x number of edges

Question 17

Define the term tree

Answer 17

A connected graph with no cycles

Question 18

What is the spanning tree of a graph?

Answer 18

A subgraph including all of the vertices of the original graph and is also a tree

Question 19

What is a complete graph?

Answer 19

A graph in which every vertex is directly connected to every other vertex with a single edge

Question 20

What are isomorphic graphs?

Answer 20

Graphs that show the same information but may be drawn differently

Question 21

What does each entry in an adjacency matrix show?

Answer 21

The number of arcs joining corresponding vertices

Question 22

What does each entry in a distance matrix show?

Answer 22

The weight of each arc

Question 23

What is a planar graph?

Answer 23

A graph that can be drawn with no two edges crossing each other

Question 24

What are the steps to the planarity algorithm?

Answer 24

1. Identify a Hamiltonian cycle
2. Draw polygon with vertices labelled to match the ones in the Hamiltonian cycle
3. Draw edges inside polygon to match ones in original graph not already represented by polygon itself
4. Make list of all edges inside polygon, in any order
5. Choose any unlabelled edge and call it ‘I’ If all edges are labelled, the graph is planar
6. Look at all unlabelled edges that cross edge(s) just labelled
7. If there are none, go back to step 5
8. If any of these edges cross each other, the graph is non-planar
9. If none of these edges cross each other, give them the opposite label (‘I’ and ‘O’ are opposites)
10. If all edges are now labelled, the graph is planar. Otherwise go back to step 6