Routing Problems

Question 1

Eularain trail

Answer 1

Trail that visits every edge exactly one

Question 2

Eularian circuit

Answer 2

Eularian trail starting and ending at the same vertex

Question 3

Euler graph

Answer 3

A graph that contains an Eularian circuit

Question 4

Theorem 4.1

Answer 4

A connected (multi) graph G is eulerian iff the degree of each vertex in G is even

Question 5

Theorem 4.2

Answer 5

A connect (multi) graph G possesses an eulerian trail iff G has exactly 2 vertices of odd degree

Question 6

Fleury’s algorithm

Answer 6

1. Choose any vertex V if G
2. Set current trail to empty sequence of edges
3. Select any edge incident with current vertex, only choosing a bridge if there is no alternative
4. Add e to the current trail set and set current vertex to V
5. Delete e from graph. Delete any isolated vertices
6. Repeat until all edges are deleted

Question 7

Chinese postman problem algorithm

Answer 7

1. Determine all odd vertices (2k)
2. Consider all possible combinations of odd vertices (k pairs)
3. Choose combination with least total weight
4. Add “extra” edges to graph
5. Use Fleury’s algorithm

Question 8

Eulerian circuit of a connected (multi) digraph

Answer 8

A directed circuit of D that contains all arcs of D

Question 9

Eulerian digraph

Answer 9

Contains a directed eulerian circuit

Question 10

Theorem 4.4 (Directed Eulerian Circuit)

Answer 10

A strongly connected (multi) digraph D is eulerian iff the indegree and outdegree are equal for each vertex D

Question 11

Theorem 4.5

Answer 11

A strongly connected (multi) digraph D possesses an eulerian trail iff D has 2 distinct vertices u and v such that od(u)=id(u) +1, id(v)=od(v)+1 and od(w)=id(w) for all other vertices w in V(D).
Trail begins at u, ends at v

Question 12

Hamiltonian path

Answer 12

Path in a graph that visits each vertex exactly once

Question 13

Hamiltonian cycle

Answer 13

Cycle that visits every vertex exactly once

Question 14

Hamiltonian graph

Answer 14

Graph possessing a hamiltonian cycle

Question 15

Theorem 4.6

Answer 15

If G is hamiltonian, then k(G-S)<=|S| for every nonempty propper subset S in V(G) of G, then G is not hamiltonian
Neccessary, not sufficient

Question 16

Dirac’s theorem (thm 4.4)

Answer 16

Let G be a connected graph of order p>=3. If the minimum degree >= p/2 then G is hamiltonian
Sufficient, not necessary

Question 17

Corollary of Dirac

Answer 17

Let G be a connected graph of order p. If the minimum degree >= (p-1)/2 then G contains a hamiltonian path.

Question 18

Bondy and Chvátal’s Theorem

Answer 18

Let U and V be distinct non adjacent vertices of a graph G of order p such that deg(u)+deg(v)>=p. Then G is hamiltonian iff G+uv is hamiltonian

Question 19

Closure

Answer 19

The graph obtained from G by iteratively joining pairs of nonadjacent vertices whose degree sum is at least p (in the resulting graph at each stage) until no such pair remains
cl(G) is unique, regardless of sequence of edges added

Question 20

Theorem 4.6 (2nd one??)

Answer 20

A graph is hamiltonian iff its closure is hamiltonian

Question 21

Corollary of 2nd 6.6

Answer 21

Let G be a graph of order p>=3. If the closure cl(G) is complete, then G is hamiltonian

Question 22

Ore’s Theorem (thm 4.7)

Answer 22

If deg(u)+deg(v)>=p for all pairs u, v of distinct nonadjacent vertices of a graph G of order p>=3 then… FINISH 🤦🏼

Question 23

Triangle inequality

Answer 23

Not done🙄

Question 24

Nearest neighbour

Answer 24

1. Start at node i. Find nearest node from i, add to route
2. From last node in route, find nearest node not yet visited. Add to route
3. Repeat until all nodes in route. Go to i

Question 25

Closest insertion heuristic

Answer 25

1. Start at node a and find nearest node to a. Add node to cycle: a-b-a
2. Find nearest node to the cycle (any node in the cycle). Insert new node
3. Repeat

Question 26

Cheapest insertion

Answer 26

1. Start at a. Find cheapest from a and add. a-b-a
2. Consider each node that isn’t part of the cycle. Find an edge such that d(i, k) +d(k, j) - d(i, j) is at its minimum. Insert node between i and j
3. Repeat