Chương 2: Đường đi và chu trình docx

1

Lý thuy t đ th ế ồ ị

Ch ng 2: Đ ng đi và chu trình ươ ườ

2

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

Bài toán “Königsburg Bridges” (Leonhard Euler,

1707-1783)

Xác định một chu trình đi qua tất cả 7 cây cầu,

mỗi cái đúng 1 lần.

3

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

 Định nghĩa: Xét 1 đồ thị liên thông G.

 Một đường đi Euler của G là một đường đi

đơn giản có đỉnh bắt đầu khác đỉnh kết thúc

và qua tất cả các cạnh của G. Khi này G còn

được gọi là một đường đi Euler.

 Một chu trình Euler của G là một chu trình

đơn giản đi qua tất cả các cạnh của G. Khi

này G còn được gọi là một chu trình Euler.

 Một đồ thị chứa chu trình Euler được gọi là

đồ thị Euler.

4

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

 Định lý 2.1: (Định lý Euler 1)

 Cho 1 đồ thị vô hướng G liên thông và có

hơn 1 đỉnh. Khi đó, G có chu trình Euler nếu

và chỉ nếu mọi đỉnh của G đều có bậc chẵn.

A

B

D C

E

Chu trình Euler:

DEABCEBD