## Lecture 13. Graph Paths & Cycles
- Eulerian Graph
- Hamiltonian Graph
- Knight's tour problem
---
### Eulerian Graph
- An **Eulerian trail** (or **Eulerian path**) is a trail in a finite graph that visits every **edge** exactly once.
- An **Eulerian circuit** (or **Eulerian cycle**) is an Eulerian trail that starts and ends on the same vertex
- They were first discussed by **Leonhard Euler** while solving the famous **Seven Bridges of Königsberg** (1736).
---
#### Eulerian Graph
- Seven Bridges of Königsberg
<img src="https://cdn.ucode.vn/uploads/1/upload/chzBTopX.png"/>
---
#### Eulerian Graph
- Seven Bridges of Königsberg
<img src="https://cdn.ucode.vn/uploads/1/upload/chzBTopX.png"/>
- $\rightarrow$ no solution
---
#### Eulerian Graph
- **Eulerian graph**: a graph with an Eulerian circuit
- A graph that has an Eulerian trail but not an Eulerian circuit is called **semi-Eulerian**.
---
#### Eulerian Graph
Drawing a shape with a continuous stroke
<img src="https://cdn.ucode.vn/uploads/1/upload/vunYZSRU.png" class="element-left content-img" />
---
#### Eulerian Graph
Drawing a shape with a continuous stroke
<img src="https://cdn.ucode.vn/uploads/1/upload/nHeFEHkL.png" class="element-left content-img" />
---
#### Euler's Theorem
- **Euler's Theorem**: A connected graph has an Euler cycle if and only if **every vertex has even degree**.
- A connected graph has an Eulerian path but does not have Eulerian cycle if and only if it has only **two vertices with odd degree**.
---
#### Fleury's algorithm
- An algorithm for constructing Eulerian trails and circuits
- An elegant but inefficient algorithm
---
#### Fleury's algorithm
- Start at a vertex of odd degree, or, if the graph has none, it starts with an arbitrarily chosen vertex.
- At each step it chooses the **next edge** in the path to be one which is **not a bridge**.
---
#### Fleury's algorithm
<img src="https://cdn.ucode.vn/uploads/1/upload/NXtjiViD.png" class="element-left content-img" width="80%" />
---
#### Fleury's algorithm
- The graph traversal in Fleury's algorithm is linear in the number of edges, i.e. $O(|E|)$ $\times$ the complexity of **detecting bridges** $\rightarrow$ $O(|E|^2)$
---
#### Fleury's algorithm
```python=
# Python program print Eulerian Trail in a given Eulerian or Semi-Eulerian Graph
from collections import defaultdict
# This class represents an undirected graph using adjacency list representation
class Graph:
def __init__(self, vertices):
self.V = vertices # No. of vertices
self.graph = defaultdict(list)
# function to add an edge to graph
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
# This function removes edge u-v from graph
def rmv_edge(self, u, v):
for index, key in enumerate(self.graph[u]):
if key == v:
self.graph[u].pop(index)
for index, key in enumerate(self.graph[v]):
if key == u:
self.graph[v].pop(index)
# A DFS based function to count reachable vertices from v
def dfs_count(self, v, visited):
count = 1
visited[v] = True
for i in self.graph[v]:
if not visited[i]:
count = count + self.dfs_count(i, visited)
return count
# The function to check if edge u-v can be considered as next edge in
# Euler Tour
def is_valid_next_edge(self, u, v):
# The edge u-v is valid in one of the following two cases:
# 1) If v is the only adjacent vertex of u
if len(self.graph[u]) == 1:
return True
else:
'''
2) If there are multiple adjacents, then u-v is not a bridge
Do following steps to check if u-v is a bridge
2.a) count of vertices reachable from u'''
visited = [False] * self.V
count1 = self.dfs_count(u, visited)
'''2.b) Remove edge (u, v) and after removing the edge, count
vertices reachable from u'''
self.rmv_edge(u, v)
visited = [False] * self.V
count2 = self.dfs_count(u, visited)
# 2.c) Add the edge back to the graph
self.add_edge(u, v)
# 2.d) If count1 is greater, then edge (u, v) is a bridge
return count1 == count2
# Print Euler tour starting from vertex u
def print_euler_util(self, u):
# Recur for all the vertices adjacent to this vertex
for v in self.graph[u]:
# If edge u-v is not removed and it's a a valid next edge
if self.is_valid_next_edge(u, v):
print("%d-%d " % (u, v)),
self.rmv_edge(u, v)
self.print_euler_util(v)
'''The main function that print Eulerian Trail. It first finds an odd
degree vertex (if there is any) and then calls printEulerUtil()
to print the path '''
def print_euler_tour(self):
# Find a vertex with odd degree
for u in range(self.V):
if len(self.graph[u]) % 2 != 0:
# Print tour starting from odd vertex
print("\n")
self.print_euler_util(u)
break
g1 = Graph(4)
g1.add_edge(0, 1)
g1.add_edge(0, 2)
g1.add_edge(1, 2)
g1.add_edge(2, 3)
g1.print_euler_tour()
g2 = Graph(3)
g2.add_edge(0, 1)
g2.add_edge(1, 2)
g2.add_edge(2, 0)
g2.print_euler_tour()
g3 = Graph(5)
g3.add_edge(1, 0)
g3.add_edge(0, 2)
g3.add_edge(2, 1)
g3.add_edge(0, 3)
g3.add_edge(3, 4)
g3.add_edge(3, 2)
g3.add_edge(3, 1)
g3.add_edge(2, 4)
g3.print_euler_tour()
```
---
#### Hierholzer's algorithm
A better algorithm:
- Step 1: Choose any starting vertex $v$, and follow a trail of edges from that vertex until returning to $v$ $\rightarrow$ a closed tour, but may not cover all the edges of the initial graph.
Note:
- It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, when the trail enters another vertex w there must be an unused edge leaving w.
---
#### Hierholzer's algorithm
- Step 2: As long as there exists a vertex $u$ that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from $u$, following unused edges until returning to $u$, and **join the tour** formed in this way to the previous tour.
- Since we assume the original graph is connected, repeating the previous step will exhaust all edges of the graph.
---
#### Hierholzer's algorithm
Complexity: $O(|E|)$
---
#### The Domino problem
- A classical Eulerian cycle problem
- There are $N$ dominoes. You want to put all the dominoes in a row so that the numbers on any two adjacent dominoes, written on their common side, coincide.
---
#### The Domino problem
- Let the numbers written on the bottoms be the vertices of the graph, and the dominoes be the edges of this graph (each Domino with numbers $(a,b)$ are the edges $(a,b)$ and $(b, a)$ ).
- Then our problem is reduced to the problem of finding the **Eulerian path** in this graph.
---
### Hamiltonian Graph
- A **Hamiltonian path** (or traceable path) is a path in an undirected or directed graph that visits **each vertex exactly once**.
- A **Hamiltonian cycle** (or Hamiltonian circuit) is a cycle that visits each vertex exactly once.
---
#### Hamiltonian Graph
<img src="https://cdn.ucode.vn/uploads/1/upload/GpHHndYV.png" class="element-left content-img" />
---
#### Hamiltonian Graph
- A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle
- Removing any edge from a Hamiltonian cycle produces a Hamiltonian path.
---
#### Hamiltonian Graph
- **Hamiltonian graph**: a graph with an Hamiltonian circuit
- A graph that has an Hamiltonian path but not an Hamiltonian circuit is called **semi-Hamiltonian**.
---
#### Hamiltonian Graph
- Determining whether Hamiltonian paths and cycles exist in graphs (the Hamiltonian path problem and Hamiltonian cycle problem) are **NP-complete**.
- A straight forward algorithm: **brute-force approach** (traversal through all permutations of the vertext list)
---
#### Hamiltonian Graph
- Dirac's Theorem (1952) — A simple graph with $n$ vertices ($n\geq 3$) is Hamiltonian if every vertex has degree $\tfrac{n}{2}$ or greater.
- Ore's Theorem (1960) — A simple graph with n vertices ($n\geq 3$) is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is $n$ or greater.
---
#### Hamiltonian Graph
- Rahman–Kaykobad (2005) — A simple graph with $n$ vertices has a Hamiltonian path if, for every non-adjacent vertex pairs the sum of their degrees and their shortest path length is greater than $n$.
---
### Knight's tour problem
A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits **every square exactly once**.
<img src="https://upload.wikimedia.org/wikipedia/commons/c/ca/Knights-Tour-Animation.gif"/>
---
#### Knight's tour problem
<img src="https://upload.wikimedia.org/wikipedia/commons/d/da/Knight%27s_tour_anim_2.gif"/>
---
#### Knight's tour existence
It's proved that for any $m × n$ board with $m ≤ n$, a closed knight's tour is always possible unless one or more of these three conditions are met:
- $m$ and $n$ are both odd
- $m \in \{1, 2, 4\}$
- $m = 3$ and $n \in \{4, 6, 8\}$.
---
#### Knight's tour: Number of tours
| $n$ | No. of tours on an $n \times n$ board |
| --------: | --------: |
| 1 | 1 |
|2 |0|
|3| 0|
|4| 0|
|5| 1,728|
|6| 6,637,920|
|7| 165,575,218,320|
|8| 19,591,828,170,979,904|
Note:
https://oeis.org/A165134
---
#### Knight's tour: Finding tours
- Brute-force algorithms
- Heuristic algorithm
---
#### Knight's tour: Brute-force
```pyhon=
def solve_knight_tour(n):
# Initialization of Board matrix
board = [[-1 for i in range(n)] for i in range(n)]
dx = [2, 1, -1, -2, -2, -1, 1, 2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]
# the Knight is initially at the first block
board[0][0] = 0
# Step counter for knight's position
pos = 1
if not attempt(n, board, 0, 0, dx, dy, pos):
print("Solution does not exist")
else:
# print the solution
for i in range(n):
for j in range(n):
print(board[i][j], end=' ')
print()
def attempt(n, board, curr_x, curr_y, dx, dy, pos):
if pos == n ** 2:
return True
# Try all next moves from the current coordinate x, y
for i in range(8):
new_x = curr_x + dx[i]
new_y = curr_y + dy[i]
if 0 <= new_x < n and 0 <= new_y < n and board[new_x][new_y] == -1:
board[new_x][new_y] = pos
if attempt(n, board, new_x, new_y, dx, dy, pos + 1):
return True
# Backtracking
board[new_x][new_y] = -1
return False
if __name__ == "__main__":
# Chessboard Size
n = 6
solve_knight_tour(n)
```
---
#### Knight's tour: complexity
- There are $m \times n$ cells and for each, we have a maximum of $8$ possible moves to choose from, so the worst running time is $O(8^{m \times n})$.
---
#### Knight's tour: Warnsdorff's rule
- **Warnsdorff's rule** is a heuristic for finding a single knight's tour.
- The knight is moved so that it always proceeds to the square from which the knight will have the **fewest onward moves**.
- In graph-theoretic terms, each move is made to the adjacent vertex with the **least degree**.
- $\rightarrow$ ~ linear time when there is a solution
---
## The end
---
{"metaMigratedAt":"2023-06-17T19:46:15.066Z","metaMigratedFrom":"YAML","breaks":true,"description":"View the slide with \"Slide Mode\".","slideOptions":"{\"theme\":\"white\"}","title":"Thuc Nguyen's ADSA Course - Lecture 13. Graph Cycles","contributors":"[{\"id\":\"476f9158-9a39-4a2d-bb09-ce08dd7eb978\",\"add\":23430,\"del\":11433}]"}