Chu trình đơn là gì trong lý thuyết đồ thị năm 2024
|
CHƯƠNG 4 ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON Trong chương này chúng ra sẽ nghiên cứu hai dạng đồ thị đặc biệt là đồ thị Euler và đồ thị Hamilton. Dưới đ�y, nếu không có giải thích bổ sung, thuật ngữ đồ thị được dùng để chỉ chung đa đồ thị vô hướng và có hướng, và thuật ngữ cạnh sẽ dùng để chỉ chung cạnh của đồ thị vô hướng cũng như cung của đồ thị có hướng. 1. ĐỒ THỊ EULER ịnh nghĩa 1. 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. Đường đi đơn trong G đi qua mỗi cạnh của nó một lần được gọi là đường đi Euler. Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler, và gọi là đồ thị nửa Euler nếu nó có đường đi Euler. Rõ ràng mọi đồ thị Euler luôn là nửa Euler, nhưng điều ngược lại không luôn đ�ng. Đồ thị G1 trong hình 1 là đồ thị Euler vì nó có chu trình Euler a, e, c, d, e, b, a. Đồ thị G3 không có chu trình Euler nhưng nó có đường đi Euler a, c, d, e, b, d, a, b, vì thế G3 là đồ thị cửa Euler. Đồ thị G2 không có chu trình cũng như đường đi Euler. Hình 1. Đồ thị G1, G2, G3 . Đồ thị H2 trong hình 2 là đồ thị Euler vì nó có chu trình Euler a, b, c, d, e, a. Đồ thị H3 không có chu trình Euler nhưng nó có đường đi Euler c, a, b, c, d, b vì thế H3 là đồ thị nửa Euler. Đồ thị H1 không có chu trình cũng như đường đi Euler. Hình 2. Đồ thị H1, H2, H3 Đ iều kiện cần và đủ để một đồ thị là một đồ thị Euler được Euler tìm ra vào năm 1736 khi ông giải quyết bài toán hóc búa nổi tiếng thế giới thời đ� về bảy cái cầu ở thành phố Konigsberg và đ�y là định lý đầu tiên của lý thuyết đồ thị. ịnh lý 1 (Euler). Đồ 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. Đ ể chứng minh định lý trước hết ta chứng minh bổ để: Nếu bậc của mỗi đỉnh của đồ thị G không nhỏ hơn 2 thì G chứa chu trình. Chứng minh. Nếu G có cạnh lặp thì khẳng định của bồ đề là hiển nhiên. Vì vậy giả sử G là đơn đồ thị. Gọi v là một đỉnh nào đ� của G. Ta sẽ xây dựng theo qui nạp đường đi v à v1 à v2 à . . . trong đ� v1 là đỉnh kề với v, còn với i≥1 chọn vi+1 # vi-l (có thể chọn vi+1 như vậy là vì deg(vi) ≥2). Do tập đỉnh của G là hữu hạn , nên sau một số hữu hạn bước ta phải quay lại một đỉnh đã xuất hiện trước đ�. Gọi đỉnh đầu tiên như thế là vk. Khi đ�, đoạn của đường đi xây dựng nằm giữa hai đỉnh vk là 1 chu trình cần tìm. Chứng minh định lý: Giả sử G là đồ thị Euler tức là tồn tại chu trình Euler P trong G. Khi đ� cứ mỗi lần chu trình P đi qua một đỉnh nào đ� của G bậc của đỉnh đó tăng lên 2. mặt khác mỗi cạnh của đồ thị xuất hiện trong P đ�ng một lần, suy ra mỗi đỉnh của đồ thị điều có bậc chẵn. ủ. Quy nạp theo số đỉnh và số cạnh của G. Do G liên thông và deg(v) là số chẵn nên bậc của mỗi đỉnh của nó không nhỏ hơn 2. Từ đ� theo bổ đề G phải chứa chu trình C. Nếu C đi qua tất cả các cạnh của G thì nó chính là chu trình Euler. Giả sử C không đi qua tất cả các cạnh của G. Khi đ� loại bỏ khỏi G tất cả các cạnh thuộc C ta thu được một đồ thị mới H vẫn có bậc là chẵn. Theo giả thiết qui nạp, trong mỗi thành phần liên thông của H điều tìm được chu trình Euler. Do G là liên thông nên trong mỗi thành phần của H có ít nhất một đỉnh chung với chu trình C. Vì vậy, ta có thể xây dựng chu trình Euler trong G như sau: bắt đầu từ một đỉnh nào đ� của chu trình C, đi theo các cạnh của C chừng nào chưa gặp phải đỉnh không cô lập của H. Nếu gặp phải đỉnh như vậy ta sẽ đi theo chu trình Euler của thành phần liên thông của H chứa đỉnh đ�. Sau đ� lại tiếp tục đi theo cạnh của C cho đến khi gặp phải đỉnh không cô lập của H thì lại theo chu trình Euler của thành phần liên thông tương ứng trong Hv.v� (xem hình 3). Quá trình sẽ kết thúc khi ta trở về đỉnh xuất phát , tức là thu được chu trình đi qua mỗi cạnh của đồ thị đ�ng một lần. Hình 3. Minh hoạ cho chứng minh định lý 1. Đồ thị vô hướng liên thông G là nửa Euler khi và chỉ khi nó có không quá 2 đỉnh bậc lẻ. Chứng minh. Thực vậy , nếu G có không quá 2 đỉnh bậc lẻ thì số đỉnh bậc lẻ của nó chỉ có thể là 0 hoặc 2. Nếu G không có đỉnh bậc lẻ thì theo định lý 1, nó là đồ thị Euler. Giả sử G có 2 đỉnh bậc lẻ là u và v. Gọi H là đồ thị thu được từ G bằng cách thêm vào G một đỉnh mới w và hai cạnh (w,u) và(w,v). Khi đ� tất cả các đỉnh của H điều có bậc chẵn, vì thế theo định lý 1, nó có chu trình Euler C. Xoá bỏ khỏi chu trình này đỉnh w và hai cạnh kề nó ta thu được đường đi Euler trong đồ thị G. Giả sử G là đồ thị Euler, từ chứng minh định lý ta có thủ tục sau để tìm chu trình Euler trong G. Procedure Euler_Cycle; Begin STACK:=Æ; CE:=Æ; Chon u la mot dinh nao do cua do thi; STACKÜu; While STACK<>Æ do Begin X:=top(STACK); (* x la phan tu dau STACK) If Ke(x)<>Æ then Begin Y:=dinh dau tien trong danh sach Ke(x); STACKÜy; (* loai bo canh (x,y) khoi do thi *) Ke(x):=Ke(x)\{y}; Ke(y):=Ke(y)\{x}; End Else Begin xÜ STACK; CEÜx; End; End; End; Giả sử G là đồ thị Euler, thuật toán đơn giản sau đ�y cho phép xác định chu trình Euler khi làm bằng tay. Thuật toán Flor Xuất phát từ một đỉnh u nào đ� của G ta đi theo các cạnh của nó một cách tuỳ ý chỉ cần tuân thủ 2 qui tắc sau: (1) Xoá bỏ cạnh đã đi qua đồng thời xoá bỏ cả những đỉnh cô lập tạo thành. (2) Ở mỗi bước ta chỉ đi qua cầu khi không còn cách lựa chon nào khác. Chứng minh tính đ�ng đắn của thuật toán. Trước tiên ta chỉ ra rằng thủ tục trên có thể thực hiện ở mỗi bước. Giả sử ta đi đến một đỉnh v nào đ�, khi đ� nếu v u thì đồ thị con còn lại H là liên thông và chứa đ�ng hai đỉnh bậc lẻ là v và u. Theo hệ quả trong H có đường đi Euler P từ v tới u. Do việc xoá bỏ cạnh đầu tiên của đường đi P không làm mất tính liên thông của H, từ đ� suy ra thủ tục có thể thực hiện ở mỗi bước. Nếu v=u thì lập luận ở trên sẽ vẫn đ�ng chừng nào vẫn còn cạnh kề với u.Như vậy chỉ còn phải chỉ ra thủ tục trên dẫn đến đường đi Euler. Thực vậy trong G không thể còn cạnh chưa đi qua khi mà ta sử dụng cạnh cuối cùng kề với u (trong trường hợp ngược lại, việc loại bỏ một cạnh nào đ� kề với một trong số những cạnh còn lại chưa đi qua sẽ dẫn đến một đồ thị không liên thông, và điều đ� là mâu thuẫn với giả thiết ii). Chứng minh tương tự như trong định lý 1 ta thu được kết quả sau đ�y cho đồ thị có hướng. ị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. |
