Section 8: Paths, walks and connectivity

Question 1

Euler tour

Answer 1

a closed walk in a graph which includes each edge precisely once

Question 2

Eulerian graph

Answer 2

a graph that contains an Euler tour

Question 3

A connected graph is Eulerian iff

Answer 3

every vertex has even degree

Question 4

Hamilton cycle

Answer 4

a cycle which contains every vertex

Question 5

Hamiltonian graph

Answer 5

a graph on n ≥ 3 vertices that contains a Hamilton cycle

Question 6

G contains a Hamilton cycle if

Answer 6

G is a graph on n ≥ 3 vertices and the minimum degree of G is at least n/2

Question 7

The Travelling Salesman Problem

Answer 7

A travelling salesman has to visit a number of cities before returning to his starting point: what is the minimum distance he has to travel?

Question 8

Lower bound algorithm gives

Answer 8

lower bound on the value of the optimum solution to the travelling salesman problem

Question 9

Lower bound algorithm

Answer 9

a) For any vertex v, any Hamilton cycle must contain two distinct edges incident with v.
b) If we delete v and the two edges incident with v from a Hamilton cycle, the remainder of the cycle gives a spanning
path on the graph G’ obtained from G by deleting v.

Question 10

Nearest Neighbour Heuristic

Answer 10

a) Choose a starting vertex v1.
b) For i = 2 to n
* Set S to be the set of vertices not yet visited (so S = V(G) \ {v1, . . . , vi−1})
* Choose vi to be a vertex in S such that the weight of vi−1vi is as small as possible
c) Return v1, . . . , vn.