Bài giảng lý thuyết đồ thị - Chương 4

ĐỒ THị EULER VÀ ĐỒ THị HAMILTONTrong chương này chúng ta sẽ tập trung nghiên cứu hai dạng đồ thị đặc biệt là đồ thị Euler và đồ thị Hamilton. Trong quá trình trình bày nếu không có chú thích bổ xung gì thì ta hiểu thuật ngữ đồ thị dùng để chỉ đồ thị tổng quát (Đa đồ thị vô hướng hoặc có hướng), thuật ngữ cạnh dùng để chỉ cả cạnh lẫn cung cua đồ thị.
Nội dung trích xuất từ tài liệu:
Bài giảng lý thuyết đồ thị - Chương 4 Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞChương 4 ĐỒ THN EULER VÀ ĐỒ THN HAMILTON Trong chương này chúng ta sẽ tập trung nghiên cứu hai dạng đồ thị đặc biệt là đồ thị Euler và đồthị Hamilton. Trong quá trình trình bày nếu không có chú thích bổ xung gì thì ta hiểu thuật ngữ đồthị dùng để chỉ đồ thị tổng quát (Đa đồ thị vô hướng hoặc có hướng), thuật ngữ cạnh dùng để chỉ cảcạnh lẫn cung cua đồ thị.4.1 Đồ thị EulerĐịnh nghĩa 1 Cho đồ thị G=(V,E)Đường đi đơn trong đồ thị G đi qua mỗi cạnh của nó một lần được gọi là đường đi Euler. Chu trìnhđơn trong đồ thị G đi qua mỗi cạnh của nó một lần được gọi là chu trình Euler.Ví dụ 1 Xét dồ thị vô hướng cho bởi hình sau (Hình 4.1) f a b e d c Hình 4.1Đường đi a, b, f, a, e, b, a, d, e, c, b là đường đi EulerĐường đi a, f, b, c, e, d, a, e, b, a là đường Euler và cũng là chu trình Euler.Đường đi a, b, c, e, d, a, e, b, a, f, b, a không phai là chu trình Euler và cũng không phải là đườngEulerVí dụ 2 Xét đồ thị có hướng cho bởi hình sau (Hình 4.2) v1 v2 v3 v5 v4 Hình 4.2 44NguyÔn Minh §øc - §HQG Hµ Néi Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞĐường v4, v3, v2, v4, v1, v5, v2 là đường đi EulerChu trình v1, v5, v2, v4, v3, v2, v4, v1 không phải là chu trình Euler và cũng không là đường điEuler.Chú ý: Đường đi Euler và chu trình Euler cũng có thể được định nghĩa như sau: Đường đi(chu trình)trong đồ thị G là đường đi (chu trình) Euler nếu nó đi qua tất cả các cạnh của đồ thị và mỗi cạnh điqua đúng một lần.Định nghĩa 2 Đồ thị G=(V,E) được gọi là đồ thị Euler nếu như nó có chu trình Euler và gọi là đồ thị nửa Eulernếu nó có đường đi Euler.Ví dụ 3: Đồ thị cho trong ví dụ 1 là đồ thị Euler còn đồ thị cho trong ví dụ 2 là đồ thị nữa Euler.Định lý 1(định lý Euler) Một đồ thị vô hướng liên thông có chu trình Euler khi và chỉ khi mỗi đỉnh của nó đều có bậcchẵn. (Điều kiện cần và đủ để một đồ thị liên thông có chu trình Euler là tất cả các đỉnh của nó đềucó bậc chẵn).Chứng minh Điều kiện cần: Một đồ thị liên thông có chu trình Euler thì mỗi bậc của nó đều có bậc chẵn. Thật vậy, giả sử chu trình Euler của đồ thị bắt đầu từ đỉnh v1 và tiếp theo là cạnh liên luộc vớiv1, tức là cạnh (v1,v2). Cạnh (v1,v2) góp 1 vào deg(v1). Mỗi lần chu trình đi qua một đỉnh vk củađồ thị, nó tăng thêm 2 đơn vị cho deg(vk) vì chu trình đi vào một đỉnh bằng một cạnh liên thuộc vớiđỉnh đó và đi ra bằng một cạnh liên thuộc khác, điều đó có nghĩa các đỉnh vk (k ≠ 1) đều có bậc làmột số chẵn. Cuối cùng chu trình kết thúc ở đỉnh mà nó xuất phát v1, vì vậy nó tăng thêm 1 vàodeg(v1). Do đó deg(v1) cũng phải là một số chẵn. Vậy ta kết luận nếu đồ thị liên thông có chu trìnhEuler thì mỗi đỉnh của nó đều có bậc chẵn. Điều kiện đủ: Một đồ thị liên thông mà các đỉnh đều có bậc chẵn thì tồn tại chu trình Euler trong đồ thị đó. Thật vậy, giả sử G là một đồ thị liên thông với các đỉnh đều có bậc là một số chẵn. Ta đi xâydựng một chu trình đơn bắt đầu từ đỉnh v1 tuỳ ý của đồ thị G. Trước tiên ta chọn cạnh (v1, v2), sauđó là (v2, v3),.. càng chọn được nhiều càng tốt. Đến một lúc nào đó đi mà ta đang chọn phải kết thúctại v1 với cạnh (vk,v1) vì đồ thị là hữu hạn và các đỉnh đều có bậc là một số chẵn. Điều này là chắcchắn xãy ra vì mỗi lần đường đi qua một đỉnh bậc chẵn nó chỉ đi vào bằng một cạnh nên ít nhất vẫncòn một cạnh để đi ra. Ví dụ trong đồ thị G cho bởi hình 4.3 ta bắt đầu ở đỉnh a và chọn tiếp cáccạnh (a, b), (b, c), (c, h) và (h, a). b g g c e e a e G H h d d Hình 4.3 45NguyÔn Minh §øc - §HQG Hµ Néi Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Chu trình mà ta xây dựng như trên có thể dùng hết tất cả các cạnh hoặc không. ...