Routing Problems Flashcards
Eurerial and Hamiltonian
Eularain trail
Trail that visits every edge exactly one
Eularian circuit
Eularian trail starting and ending at the same vertex
Euler graph
A graph that contains an Eularian circuit
Theorem 4.1
A connected (multi) graph G is eulerian iff the degree of each vertex in G is even
Theorem 4.2
A connect (multi) graph G possesses an eulerian trail iff G has exactly 2 vertices of odd degree
Fleury’s algorithm
- Choose any vertex V if G
- Set current trail to empty sequence of edges
- Select any edge incident with current vertex, only choosing a bridge if there is no alternative
- Add e to the current trail set and set current vertex to V
- Delete e from graph. Delete any isolated vertices
- Repeat until all edges are deleted
Chinese postman problem algorithm
- Determine all odd vertices (2k)
- Consider all possible combinations of odd vertices (k pairs)
- Choose combination with least total weight
- Add “extra” edges to graph
- Use Fleury’s algorithm
Eulerian circuit of a connected (multi) digraph
A directed circuit of D that contains all arcs of D
Eulerian digraph
Contains a directed eulerian circuit
Theorem 4.4 (Directed Eulerian Circuit)
A strongly connected (multi) digraph D is eulerian iff the indegree and outdegree are equal for each vertex D
Theorem 4.5
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
Hamiltonian path
Path in a graph that visits each vertex exactly once
Hamiltonian cycle
Cycle that visits every vertex exactly once
Hamiltonian graph
Graph possessing a hamiltonian cycle
Theorem 4.6
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
Dirac’s theorem (thm 4.4)
Let G be a connected graph of order p>=3. If the minimum degree >= p/2 then G is hamiltonian
Sufficient, not necessary
Corollary of Dirac
Let G be a connected graph of order p. If the minimum degree >= (p-1)/2 then G contains a hamiltonian path.
Bondy and Chvátal’s Theorem
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
Closure
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
Theorem 4.6 (2nd one??)
A graph is hamiltonian iff its closure is hamiltonian
Corollary of 2nd 6.6
Let G be a graph of order p>=3. If the closure cl(G) is complete, then G is hamiltonian
Ore’s Theorem (thm 4.7)
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 🤦🏼
Triangle inequality
Not done🙄
Nearest neighbour
- Start at node i. Find nearest node from i, add to route
- From last node in route, find nearest node not yet visited. Add to route
- Repeat until all nodes in route. Go to i
Closest insertion heuristic
- Start at node a and find nearest node to a. Add node to cycle: a-b-a
- Find nearest node to the cycle (any node in the cycle). Insert new node
- Repeat
Cheapest insertion
- Start at a. Find cheapest from a and add. a-b-a
- 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
- Repeat
