Lý thuyết đô thị - Chương 4: Đồ thị euler và đồ thị halmiton

Chương 4 ĐỒ THỊ EULER và ĐỒ THỊ HALMITON 226/03/2011 4.1 Đồ thị Euler Lý thuyết đồ thị Định nghĩa Xét đồ thị G = (V,E) – Đường đi đơn trong G được gọi là đường đi Euler nếu nó đi qua tất cả các cạnh, mỗi cạnh một lần. – Chu trình đơn trong G được gọi là chu trình Euler nếu nó đi qua tất cả các cạnh, mỗi cạnh một lần. – Đồ thị G được gọi là đồ thị Euler nếu có chu trình Euler. – Đồ thị G được gọi là đồ thị nửa Euler nếu có đường đi Euler. 326/03/2011 4.1 Đồ thị Euler Lý thuyết đồ thị Ví dụ: Đồ thị G1có các đường đi Euler là: d1: 1 2 3 4 2 5 4 1 5 d2: 1 2 4 3 2 5 1 4 5 Đồ thị G2 có các chu trình Euler là: C1: 1 2 3 4 2 5 4 1 5 6 1 C2: 1 2 4 3 2 5 1 4 5 6 1 1 2 3 4 5 G1 1 2 3 4 5 6 G2 Đồ thị nửa Euler Đồ thị Euler 426/03/2011 4.1 Đồ thị Euler Lý thuyết đồ thị Định lý 1 Đồ thị vô hướng liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn. Hệ quả Đồ thị vô hướng liên thông G là đồ thị nửa Euler khi và chỉ khi nó có không quá 2 đỉnh bậc lẻ. 526/03/2011 4.1 Đồ thị Euler Lý thuyết đồ thị Thuật toán Fleury xác định chu trình Euler Xuất phát từ một đỉnh bất kỳ của G, đi theo các cạnh một cách tùy ý, chỉ cần tuân thủ hai quy tắc sau: i) Xóa bỏ cạnh đã đi qua và đồng thời xóa cả những đỉnh cô lập tạo thành. ii) Ở mỗi bước, chỉ đi qua cầu khi không còn cách chọn lựa nào khác. Ví dụ: Tìm chu trình ở Euler trong đồ thị a b c d efgh 626/03/2011 4.1 Đồ thị Euler Lý thuyết đồ thị Định lý 2 Đồ thị có hướng liên thông mạnh là đồ thị Euler khi và chỉ khi deg+(v) = deg-(v), ∀v∈V 726/03/2011 4.2 Đồ thị Hamilton Lý thuyết đồ thị Định nghĩa Xét đồ thị G = (V,E) – Đường đi trên G được gọi là đường đi Hamilton nếu nó đi qua tất cả các đỉnh, mỗi đỉnh một lần. – Chu trình trên G được gọi là chu trình Hamilton nếu nó đi qua tất cả các đỉnh, mỗi đỉnh một lần. – Đồ thị G được gọi là đồ thị Hamilton nếu có chu trình Hamilton. – Đồ thị G được gọi là đồ thị nửa Hamilton nếu có đường đi Hamilton. 826/03/2011 4.2 Đồ thị Hamilton Lý thuyết đồ thị Ví dụ: Đồ thị G1có các đường đi Hamilton là: d1: 3 4 2 5 1 d2: 3 4 5 1 2 Đồ thị G2 có các chu trình Hamilton là: C1: 1 2 3 4 5 6 1 C2: 1 6 5 2 3 4 1 1 2 3 4 5 G1 1 2 3 4 5 6 G2 Đồ thị Hamilton Đồ thị nửa Hamilton 926/03/2011 4.2 Đồ thị Hamilton Lý thuyết đồ thị Định lý 3 (Dirak 1952) Đơn đồ thị vô hướng G với n đỉnh (n > 2), mỗi đỉnh có bậc không nhỏ hơn n/2 là đồ thị Hamilton. Định lý 4 Đồ thị có hướng liên thông mạnh G với n đỉnh. Nếu thì G là đồ thị Hamilton. deg+(v) ≥ n/2, deg-(v) ≥ n/2, ∀v 1026/03/2011 4.2 Đồ thị Hamilton Lý thuyết đồ thị Đồ thị đấu loại là đồ thị có hướng mà trong đó hai đỉnh bất kỳ của nó được nối với nhau bởi đúng một cung. Định lý 5 i) Mọi đồ thị đấu loại là nửa Hamilton. ii) Mọi đồ thị đấu loại liên thông mạnh là Hamilton 1126/03/2011 4.2 Đồ thị Hamilton Lý thuyết đồ thị Định lý 6 (Ore, 1960) Cho đồ thị G có n đỉnh. Nếu deg(i)+deg(j)≥ n≥3 với i và j là hai đỉnh không kề nhau tùy ý thì G là Hamilton. 1226/03/2011 4.2 Đồ thị Hamilton Lý thuyết đồ thị Quy tắc để xây dựng một chu trình Hamilton (H) Quy tắc 1. Tất cả các cạnh kề với đỉnh bậc 2 phải ở trong H Quy tắc 2. Không có chu trình con (chu trình có chiều dài <n) nào được tạo thành trong quá trình xây dựng H. Quy tắc 3. Khi chu trình Hamilton mà ta đang xây dựng đi qua đỉnh i thì xóa tất cả các cạnh kề với i mà ta chưa dùng (vì không được dùng đến nữa). Điều này lại có thể cho ta một số đỉnh bậc 2 và ta lại dùng quy tắc 1. Quy tắc 4. Không có đỉnh cô lập hay đỉnh treo nào được tạo nên sau khi áp dụng quy tắc 3. 1326/03/2011 4.2 Đồ thị Hamilton Lý thuyết đồ thị Ví dụ Đồ thị sau có là đồ thị Hamilton không? 1 2 3 4 5 6 7 8 9 Giả sử G có chu trình Hamilton H. Theo quy tắc 1, tất cả các cạnh kề với đỉnh bậc 2 đều ở trong H: 12, 14, 23, 36, 47, 78, 69, 89. Ta có chu trình con là 1, 2, 3, 6, 9, 8, 7, 4, 1. Vậy G không là đồ thị Hamilton.