6.1. Bài toán 7 cái cầu
Thành phố Konigsberg thuộc Phổ [nay là Kaliningrad thuộc Cộng hoà Nga], được chia làm 4 vùng bằng các nhánh sông Pregel. Các vùng này gồm 2 vùng bên bờ sông [B, C], đảo Kneiphof [A] vàmột miền nằm giữa hai nhánh sông Pregel [D]. Vào thế kỷ XVIII, người ta đã xây 7 chiếc cầu nốinhững vùng này với nhau. Người dân ở đây tự hỏi: Liệu có cách nào xuất phát tại một địa điểmtrong thành phố, đi qua 7 chiếc cầu, mỗi chiếc đúng 1 lần rồi quay trở về nơi xuất phát không ?Nhà toán học Thụy sĩ Leonhard Euler đã giải bài toán này và có thể coi đây là ứng dụng đầu tiêncủa Lý thuyết đồ thị, ông đã mô hình hoá sơ đồ 7 cái cầu bằng một đa đồ thị, bốn vùng được biểudiễn bằng 4 đỉnh, các cầu là các cạnh. Bài toán tìm đường qua 7 cầu, mỗi cầu đúng một lần có thểtổng quát hoá bằng bài toán: Có tồn tại chu trình đơn trong đa đồ thị chứa tất cả các cạnh ?.
Mô hình đồ thị của bài toán bảy cái cầu
6.2. Định nghĩa
Chu trình đơn chứa tất cả các cạnh của đồ thị được gọi là chu trình Euler.
Đường đi đơn chứa tất cả các cạnh của đồ thị được gọi là đường đi Euler.
Một đồ thị có chu trình Euler được gọi là đồ thị Euler.
Một đồ thị có đường đi Euler được gọi là đồ thị nửa Euler.
Rõ ràng một đồ thị Euler thì phải là nửa Euler nhưng điều ngược lại thì không phải luôn đúng.
6.3. Định lý
Một đồ thị vô hướng liên thông G = [V, E] có chu trình Euler khi và chỉ khi mọi đỉnh của nó đều có bậc chẵn: deg[v] 0 [mod 2] [vV]
Một đồ thị vô hướng liên thông có đường đi Euler nhưng không có chu trình Euler khi và chỉ khi nó có đúng 2 đỉnh bậc lẻMột đồ thi có hướng liên thông yếu G = [V, E] có chu trình Euler thì mọi đỉnh của nó có bán bậc ra bằng bán bậc vào: deg+[v] = deg-[v] [vV]; Ngược lại, nếu G liên thông yếu và mọi đỉnh củanó có bán bậc ra bằng bán bậc vào thì G có chu trình Euler, hay G sẽ là liên thông mạnh.
Một đồ thị có hướng liên thông yếu G = [V, E] có đường đi Euler nhưng không có chu trình Euler nếu tồn tại đúng hai đỉnh u, v V sao cho deg+[u] - deg-[u] = deg-[v] - deg+[v] = 1, còn tấtcả những đỉnh khác u và v đều có bán bậc ra bằng bán bậc vào.
6.4. Thuật toán Fleury tìm chu trình Euler
6.4.1. Đối với đồ thị vô hướng liên thông, mọi đỉnh đều có bậc chẵn
Xuất phát từ một đỉnh, ta chọn một cạnh liên thuộc với nó để đi tiếp theo hai nguyên tắc sau:
Xoá bỏ cạnh đã đi qua
Chỉ đi qua cầu khi không còn cạnh nào khác để chọn
Và ta cứ chọn cạnh đi một cách thoải mái như vậy cho tới khi không đi tiếp được nữa, đường đi tìm được là chu trình Euler.
Ví dụ: Với đồ thị ở Hình 73:
Nếu xuất phát từ đỉnh 1, có hai cách đi tiếp: hoặc sang 2 hoặc sang 3, giả sử ta sẽ sang 2 và xoá cạnh [1, 2] vừa đi qua. Từ 2 chỉ có cách duy nhất là sang 4, nên cho dù [2, 4] là cầu ta cũng phải đisau đó xoá luôn cạnh [2, 4]. Đến đây, các cạnh còn lại của đồ thị có thể vẽ như Hình 74 bằng nétliền, các cạnh đã bị xoá được vẽ bằng nét đứt.
Bây giờ đang đứng ở đỉnh 4 thì ta có 3 cách đi tiếp: sang 3, sang 5 hoặc sang 6. Vì [4, 3] là cầu nên ta sẽ không đi theo cạnh [4, 3] mà sẽ đi [4, 5] hoặc [4, 6]. Nếu đi theo [4, 5] và cứ tiếp tục đi nhưvậy, ta sẽ được chu trình Euler là [1, 2, 4, 5, 7, 8, 6, 4, 3, 1]. Còn đi theo [4, 6] sẽ tìm được chu trìnhEuler là: [1, 2, 4, 6, 8, 7, 5, 4, 3, 1].
6.4.2. Đối với đồ thị có hướng liên thông yếu, mọi đỉnh đều có bán bậc ra bằng bán bậc vào
Bằng cách "lạm dụng thuật ngữ", ta có thể mô tả được thuật toán tìm chu trình Euler cho cả đồ thị có hướng cũng như vô hướng:
Thứ nhất, dưới đây nếu ta nói cạnh [u, v] thì hiểu là cạnh nối đỉnh u và đỉnh v trên đồ thị vô hướng, hiểu là cung nối từ đỉnh u tới đỉnh v trên đồ thị có hướng.
Thứ hai, ta gọi cạnh [u, v] là "một đi không trở lại" nếu như từ u ta đi tới v theo cạnh đó, sau đó xoá cạnh đó đi thì không có cách nào từ v quay lại u.
Vậy thì thuật toán Fleury tìm chu trình Euler có thể mô tả như sau:
Xuất phát từ một đỉnh, ta đi một cách tuỳ ý theo các cạnh tuân theo hai nguyên tắc: Xoá bỏ cạnh vừa đi qua và chỉ chọn cạnh "một đi không trở lại" nếu như không còn cạnh nào khác để chọn.
6.5. Cài đặt
Ta sẽ cài đặt thuật toán Fleury trên một đa đồ thị vô hướng. Để đơn giản, ta coi đồ thị này đã có chu trình Euler, công việc của ta là tìm ra chu trình đó thôi. Bởi việc kiểm tra tính liên thông cũng nhưkiểm tra mọi đỉnh đều có bậc chẵn đến giờ có thể coi là chuyện nhỏ.
Input: file văn bản EULER.INP
Dòng 1: Chứa số đỉnh n của đồ thị [n 100]
Các dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương cách nhau ít nhất 1 dấu cách có dạng: u v k cho biết giữa đỉnh u và đỉnh v có k cạnh nối.
Output: file văn bản EULER.OUT, ghi chu trình EULER
6.6. Thuật toán tốt hơn
Trong trường hợp đồ thị Euler có số cạnh đủ nhỏ, ta có thể sử dụng phương pháp sau để tìm chu trình Euler trong đồ thị vô hướng: Bắt đầu từ một chu trình đơn C bất kỳ, chu trình này tìm được bằng cách xuất phát từ một đỉnh, đi tuỳ ý theo các cạnh cho tới khi quay về đỉnh xuất phát, lưu ý làđi qua cạnh nào xoá luôn cạnh đó. Nếu như chu trình C tìm được chứa tất cả các cạnh của đồ thị thìđó là chu trình Euler. Nếu không, xét các đỉnh dọc theo chu trình C, nếu còn có cạnh chưa xoá liênthuộc với một đỉnh u nào đó thì lại từ u, ta đi tuỳ ý theo các cạnh cũng theo nguyên tắc trên cho tớikhi quay trở về u, để được một chu trình đơn khác qua u. Loại bỏ vị trí u khỏi chu trình C và chènvào C chu trình mới tìm được tại đúng vị trí của u vừa xoá, ta được một chu trình đơn C' mới lớnhơn chu trình C. Cứ làm như vậy cho tới khi được chu trình Euler. Việc chứng minh tính đúng đắncủa thuật toán cũng là chứng minh định lý về điều kiện cần và đủ để một đồ thị vô hướng liên thôngcó chu trình Euler.
Mô hình thuật toán có thể viết như sau:
;Thuật toán trên có thể dùng để tìm chu trình Euler trong đồ thị có hướng liên thông yếu, mọi đỉnhcó bán bậc ra bằng bán bậc vào. Tuy nhiên thứ tự các đỉnh in ra bị ngược so với các cung định hướng, ta có thể đảo ngược hướng các cung trước khi thực hiện thuật toán để được thứ tự đúng.Thuật toán hoạt động với hiệu quả cao, dễ cài đặt, nhưng trường hợp xấu nhất thì Stack sẽ phải chứatoàn bộ danh sách đỉnh trên chu trình Euler chính vì vậy mà khi đa đồ thị có số cạnh quá lớn thì sẽkhông đủ không gian nhớ mô tả Stack [Ta cứ thử với đồ thị chỉ gồm 2 đỉnh nhưng giữa hai đỉnh đócó tới 106cạnh nối sẽ thấy ngay]. Lý do thuật toán chỉ có thể áp dụng trong trường hợp số cạnh cógiới hạn biết trước đủ nhỏ là như vậy.
P_4_06_2.PAS * Thuật toán hiệu quả tìm chu trình Euler program Euler_Circuit; const InputFile = 'EULER.INP'; OutputFile = 'EULER.OUT'; max = 100; maxE = 20000; {Số cạnh tối đa} var a: array[1..max, 1..max] of Integer; stack: array[1..maxE] of Integer; n, last: Integer; procedure Enter; {Nhập dữ liệu} var u, v, k: Integer; f: Text; begin Assign[f, InputFile]; Reset[f]; FillChar[a, SizeOf[a], 0]; ReadLn[f, n]; while not SeekEof[f] do begin ReadLn[f, u, v, k]; a[u, v] := k; a[v, u] := k; end; Close[f]; end; procedure Push[v: Integer]; {Đẩy một đỉnh v vào ngăn xếp} begin Inc[last]; Stack[last] := v; end; function Pop: Integer; {Lấy một đỉnh khỏi ngăn xếp, trả về trong kết quả hàm} begin Pop := Stack[last]; Dec[last]; end; function Get: Integer; {Trả về phần tử ở đỉnh [Top] ngăn xếp} begin Get := Stack[last]; end; procedure FindEulerCircuit; var u, v, count: Integer; f: Text; begin Assign[f, OutputFile]; Rewrite[f]; Stack[1] := 1; {Khởi tạo ngăn xếp ban đầu chỉ gồm đỉnh 1} last := 1; count := 0; while last 0 do {Chừng nào ngăn xếp chưa rỗng} begin u := Get; {Xác định u là phần tử ở đỉnh ngăn xếp} for v := 1 to n do if a[u, v] > 0 then {Xét tất cả các cạnh liên thuộc với u, nếu thấy} begin Dec[a[u, v]]; Dec[a[v, u]]; {Xoá cạnh đó khỏi đồ thị} Push[v]; {Đẩy đỉnh tiếp theo vào ngăn xếp} Break; end; if u = Get then {Nếu phần tử ở đỉnh ngăn xếp vẫn là u vòng lặp trên không tìm thấy đỉnh nào kề với u} begin Inc[count]; Write[f, Pop, ' ']; {In ra phần tử đỉnh ngăn xếp} end; end; Close[f]; end; begin Enter; FindEulerCircuit; end.Bài tập
Trên mặt phẳng cho n hình chữ nhật có các cạnh song song với các trục toạ độ. Hãy chỉ ra một chu trình:
Chỉ đi trên cạnh của các hình chữ nhật
Trên cạnh của mỗi hình chữ nhật, ngoại trừ những giao điểm với cạnh của hình chữ nhật khác có thể qua nhiều lần, những điểm còn lại chỉ được qua đúng một lần.