Đường đi và chu trình Euler

Đồ thị G=(V,E)

Lí thuyết

Chu trình Euler của đồ thị G =(V, E): chu trình trên đồ thị chứa(đi qua)tất cả các cạnh của đồ thị, mỗi cạnh đúng 1 lần.
Đường đi Euler(không phải chu trình): đường chứa(đi qua) tất cả các cạnh của đồ thị, mỗi cạnh đúng 1 lần.
Các định lí Euler...

Giả thiết: G vô hướng, liên thông và có đúng 2 đỉnh có bậc lẻ là a và z.

Ý tưởng:

Bổ sung thêm 1 cạnh e_new nối a và z để có đồ thị G’ có chu trình Euler.
Tìm 1 chu trình Euler Euler_G’ của G’ (theo thuật giải tìm chu trình Euler trên.
Hiểu chỉnh (xoay) chu trình Euler_G’ để cho đỉnh a là đỉnh xuất phát và cạnh e_new là cạnh đầu tiên.
Loại cạnh e_new từ chu trình thì ta có một đường Euler của G.

Giả thiết: G vô hướng, liên thông và mọi đỉnh có bậc chẵn.
Ý tưởng:

B1: Chọn đỉnh a (tùy ý), xuất phát từ a đi theo các cạnh (chưa đi qua) nối tiếp nhau đến khi trở về a. Ta được một chu trình, ký hiệu là C
B2: While (Còn cạnh chưa đi qua) // có phần tử thuộc E mà không thuộc C

2.1: Chọn đỉnh a thuộc C mà có cạnh liên kết với a nhưng không thuộc C.

2.2: Xuất phát từ a đi theo các cạnh (chưa đi qua) nối tiếp nhau đến khi trở về a. Ta được một chu trình, ký hiệu là SubC.

2.3: Thay thế chu trình SubC vào chu trình C tại điểm a (thay thế cho a) à ta được chu trình C mới lớn hơn.