Chapter 2

Question 1

Define walk

Answer 1

route through a graph along arcs from one node to the next

Question 2

Define path

Answer 2

walk where no node is visited more than once

Question 3

Define trail

Answer 3

walk where no arc is visited more than once

Question 4

Define cycle

Answer 4

walk where start and end node are the same and no node visited more than once

Question 5

Define Hamiltonian cycle

Answer 5

cycle that includes all nodes

Question 6

Define connected graph

Answer 6

graph where it is possible to get from one node to any other node via arcs

Question 7

Define simple graph

Answer 7

no multiple arcs

Question 8

Define digraph

Answer 8

graphs with directions on arcs

Question 9

Define tree

Answer 9

connected graph with no cycles

Question 10

Define spanning tree

Answer 10

tree that uses all nodes of parent graph

Question 11

Define minimum spanning tree

Answer 11

spanning tree with sum of arc weights minimised

Question 12

Define complete graph

Answer 12

every node is directly connected to every other arc

Question 13

Define isomorphic graph

Answer 13

graphs that can be drawn differently but represent the same information

Question 14

Define planar graph

Answer 14

graph drawn in a plane where no arcs meet except at nodes

Question 15

Outline planarity algorithm

Answer 15

1. Identify Hamiltonian cycle
2. Draw regular polygon of HC and extra arcs on inside of HC
3. List all edges inside polygon
4. Choose any unlabelled edge and label I
5. If any edges that cross labelled edge cross each other, NON PLANAR
6. If not, label edge/s O
7. Repeat 4 & 5 till done