---
title: Thuc Nguyen's ADSA Course - Lecture 11. Graph Cycles
tags: Advanced Data Structures and Algorithms Course
description: View the slide with "Slide Mode".
type: slide
slideOptions:
theme: white
# transition: 'fade'
# parallaxBackgroundImage: 'https://s3.amazonaws.com/hakim-static/reveal-js/reveal-parallax-1.jpg'
---

## 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 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

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

---