D1, C2 - Graphs & Networks

Question 1

What are the points on graphs called

Answer 1

Vertices or Nodes

Question 2

What are the lines on graphs called

Answer 2

Edges or Arcs

Question 3

What is a graph that has number associated with an edge or arc called

Answer 3

Weighted graph or Network

Question 4

What is a vertex set

Answer 4

A set of all the vertices
e.g. A, B, C, …

Question 5

What is a edge set

Answer 5

A set of all the edges
e.g. AB, AC, BC, …

Question 6

What is a subgraph

Answer 6

A part of a graph

Question 7

What is the degree / valency / order of a vertex

Answer 7

The number of edges incident (coming out of the vertex)

Question 8

What are the types of degree for a vertex (2)

Answer 8

Odd
Even

Question 9

What is a walk

Answer 9

Any route through a graph from a vertex to a vertex

Question 10

What is a path

Answer 10

A walk in which no vertex is visited more than once

Question 11

What is a trail

Answer 11

A walk in which no edge is visited more than once

Question 12

What is a cycle

Answer 12

A walk in which the start and end vertex are the same. No other vertex is visited more than once

Question 13

What is a Hamiltonian cycle

Answer 13

A cycle that includes every vertex

Question 14

What is a connected graph

Answer 14

A graph will all of its vertices connected

Question 15

What is a loop

Answer 15

An edge that starts and finishes at the same vertex

Question 16

What is a simple graph

Answer 16

A graph with no loops and at most one edge connecting any pair of vertices

Question 17

What is a directed graph (digraph)

Answer 17

A graph where all the edges are directed, i.e. have direction arrows on them

Question 18

What is an undirected graph

Answer 18

A graph where the sum of the degrees (of the vertices) is equal to 2 * number of edges
Number of odd vertices = even (or zero)
Euler’s Hand-shaking Lemma

Question 19

A graph has 5 nodes and 8 edges. The valencies of the nodes are x, x-1, x+1, 2x-1, x-1. Find x

Answer 19

By Euler’s Hand-shaking Lemma
Total valency = 2 * number of edges
x + x-1 + x+1 + 2x-1 + x-1 = 2 * 8
6x - 2 = 16
x = 3

Question 20

What is a tree

Answer 20

A connected graph with no cycles

Question 21

What is a spanning tree

Answer 21

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

Question 22

What is a complete graph

Answer 22

A graph where every vertex is connected to every other vertex

Question 23

What are isometric graphs

Answer 23

Graphs which show the same information drawn differently

Question 24

What must be the same with isometric graphs

Answer 24

Number of edges
Number of vertices
Same valencies

Question 25

What does it mean if a complete graph is Kn

Answer 25

n is the number of vertices of the complete graph e.g. K5 is a complete graph with 5 vertices

Question 26

What does an adjacency matrix show

Answer 26

The number of edges between the vertices (0’s down the middle unless there is a loop)

Question 27

What does a distance matrix show

Answer 27

The weight of the arc between vertices
(-‘s down the middle)

Question 28

Can you construct a graph given an:
a) Adjacency matrix
b) Distance matrix

Answer 28

a) YES
b) NO

Question 29

If a graph is not directed, what does it mean for a distance matrix

Answer 29

Matrix should be ‘symmetrical’

Question 30

What goes down the middle diagonal for an adjacency matrix

Answer 30

0’s unless there is a loop which would be a 2

Question 31

What should you put in a distance matrix cell if there is no weight between the vertices

Answer 31

-

Question 32

If I selected the column which is (B, D) what does this mean (what goes to what)

Answer 32

B goes to D

Question 33

Are distance matrices or adjacency matrices always symmetrical

Answer 33

Adjacency matrices

Question 34

What is a planar graph

Answer 34

A graph where edges only meet at a vertex (arcs don’t cross over)

Question 35

What are the steps for The Planarity Algorithm (6)

Answer 35

1) Find a Hamiltonian Cycle
2) Draw this cycle as a polygon
3) Add in any other edges from the original graph (draw these inside the polygon)
4) List all the edges inside the polygon (may be useful to do at the start)
5) Choose any edge on the list and label it I (I for inside)
6) Look for unlabelled edges that cross ‘I’, if these edges cross each other the graph is NOT planar. If they don’t label them ‘O’ (outside). Repeat 5 until all edges are labelled (if all edges are labelled it is PLANAR)

Question 36

How do you know if the Planarity Algorithm finds a planar graph

Answer 36

All edges will be labelled O or I

Question 37

What does it mean if when performing the planarity algorithm, 2 edges labelled O (outside) intersect (or two labelled I intersect)

Answer 37

The graph is NOT planar