Đồ thị Euler và đồ thị Hamilton

Đồ thị Euler

Leonhard Euler là người đầu tiên mô hình hóa bài toán rời rạc này thành một hệ thống hoàn chỉnh là Lý thuyết đồ thị hiện nay.

Definition 40 (Chu trình Euler)

Chu trình đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần, được gọi là chu trình Euler (hay Euler circuit, Euler circle, Euler tour).

Definition 41 (Đường đi Euler)

Đường đi đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần, được gọi là đường đi Euler.

Lúc này, bài toán \(7\) cây cầu nổi tiếng của thành phố Konigsberg (nay là thành phố Kaliningrad thuộc Liên bang Nga) trở thành bài toán xác định xem có tồn tại chu trình Euler hay không.

Definition 42 (Đồ thị Euler)

Đồ thị có chu trình Euler được gọi là đồ thị Euler (hay Eulerian graph, unicursal graph).

Definition 43 (Đồ thị nửa Euler)

Đồ thị có đường đi Euler được gọi là đồ thị nửa Euler (hay Semi-Eulerian graph, Traversable graph).

Các định lí và thuật toán trên đồ thị Euler

Theorem 15

Một đồ thị vô hướng liên thông \(G = (V, E)\) có chu trình Euler khi và chỉ khi mọi đỉnh của nó đều có bậc chẵn.

Chứng minh chiều thuận

Chiều thuận. Nếu \(G\) có chu trình Euler thì khi đi theo chu trình đó, mỗi đỉnh sẽ đi vào một lần và đi ra một lần nên bậc của nó tăng lên \(2\). Áp dụng cho mỗi lần gặp một đỉnh thì cuối cùng bậc của mỗi đỉnh phải là số chẵn

Chiều ngược. Nếu mọi đỉnh của đồ thị đều có bậc chẵn, ta cần xây dựng cách tìm chu trình Euler.

Corollary 3

Một đồ thị vô hướng liên thông \(G = (V, E)\) có đường đi Euler khi và chỉ khi nó có đúng hai đỉnh bậc lẻ.

Chứng minh

Điều kiện của đường đi Euler “lỏng hơn” chu trình vì điểm đầu không cần phải trùng với điểm cuối. Do đó nếu \(G\) có đường đi Euler thì đỉnh bắt đầu và kết thúc sẽ có bậc lẻ, các đỉnh còn lại có bậc chẵn. Ngược lại nếu đồ thị liên thông có đúng hai đỉnh bậc lẻ, khi đó ta vẽ cạnh nối hai đỉnh đó thì tất cả đỉnh của đồ thị đều có bậc chẵn, nghĩa là tồn tại chu trình Euler. Loại bỏ cạnh đó thì ta có đường đi Euler.

Đồ thị Hamilton

Khái niệm đường đi và chu trình Hamilton được đưa ra bởi William Rowan Hamilton (1856).

Definition 44 (Chu trình Hamilton và đồ thị Hamilton)

Đồ thị \(G = (V, E)\) được gọi là đồ thị Hamilton (hay Hamilton graph) nếu tồn tại chu trình đơn đi qua tất cả các đỉnh.

Chu trình đơn đi qua tất cả các đỉnh gọi là chu trình Hamilton (hay Hamiltonian circuit, Hamilton circle).

Người ta quy ước rằng đồ thị chỉ gồm một đỉnh là đồ thị Hamilton nhưng đồ thị gồm hai đỉnh liên thông không phải là đồ thị Hamilton.