Ltdt6

Lý thuyết đồ thị

\ 47 [

§6. CHU TRÌNH EULER, ĐƯỜNG ĐI EULER, ĐỒ THỊ EULER

I. 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ối nhữ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ểm trong 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ên củ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ểu diễ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 ?. C

C

A

D

A

D

B B

Hình 18: Mô hình đồ thị của bài toán bảy cái cầu

II. ĐỊNH NGHĨA 1. Chu trình đơn chứa tất cả các cạnh của đồ thị được gọi là chu trình Euler 2. Đường đi đơn chứa tất cả các cạnh của đồ thị được gọi là đường đi Euler 3. Một đồ thị có chu trình Euler được gọi là đồ thị Euler 4. 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 III. ĐỊNH LÝ 1. 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) (∀v∈V) 2. 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ẻ 3. 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) (∀v∈V); Ngược lại, nếu G liên thông yếu và mọi đỉnh của nó 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. 4. 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ất cả những đỉnh khác u và v đều có bán bậc ra bằng bán bậc vào.

Lê Minh Hoàng

Lý thuyết đồ thị

\ 48 [

IV. THUẬT TOÁN FLEURY TÌM CHU TRÌNH EULER 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ị sau: 5

2

5

2 7

1

4

7 1

4

8 3

6

8 3

6

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 đi sau đó xoá luôn cạnh (2, 4). Đến đây, các cạnh còn lại của đồ thị có thể vẽ như trên bằng nét liề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ình Euler là: (1, 2, 4, 6, 8, 7, 5, 4, 3, 1). 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. V. 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 Lê Minh Hoàng

Lý thuyết đồ thị

\ 49 [

1

2

4

3

EULER.INP 4 1 2 1 1 3 2 1 4 1 2 3 1 3 4 1

EULER.OUT 1 2

3

1

3

4

1

PROG06_1.PAS * Thuật toán Fleury tìm chu trình Euler program Euler_Circuit; const max = 100; var a: array[1..max, 1..max] of Integer; n: Integer; procedure Enter; {Nhập dữ liệu từ thiết bị nhập chuẩn Input} var u, v, k: Integer; begin FillChar(a, SizeOf(a), 0); ReadLn(n); while not SeekEof do begin ReadLn(u, v, k); a[u, v] := k; a[v, u] := k; end; end; {Thủ tục này kiểm tra nếu xoá một cạnh nối (x, y) thì y có còn quay lại được x hay không}

function CanGoBack(x, y: Integer): Boolean; var Queue: array[1..max] of Integer; {Hàng đợi dùng cho Breadth First Search} First, Last: Integer; {First: Chỉ số đầu hàng đợi, Last: Chỉ số cuối hàng đợi} u, v: Integer; Free: array[1..max] of Boolean; {Mảng đánh dấu} begin Dec(a[x, y]); Dec(a[y, x]); {Thử xoá một cạnh (x, y) ⇔ Số cạnh nối (x, y) giảm 1} FillChar(Free, n, True); {sau đó áp dụng BFS để xem từ y có quay lại x được không ?} Free[y] := False; First := 1; Last := 1; Queue[1] := y; repeat u := Queue[First]; Inc(First); for v := 1 to n do if Free[v] and (a[u, v] > 0) then begin Inc(Last); Queue[Last] := v; Free[v] := False; if Free[x] then Break; end; until First > Last; CanGoBack := not Free[x]; Inc(a[x, y]); Inc(a[y, x]); {ở trên đã thử xoá cạnh thì giờ phải phục hồi} end; procedure FindEulerCircuit; {Thuật toán Fleury} var Current, Next, v, count: Integer;

Lê Minh Hoàng

Lý thuyết đồ thị

\ 50 [

begin Current := 1; Write(1:5); {Bắt đầu từ đỉnh Current = 1} count := 1; repeat Next := 0; for v := 1 to n do if a[Current, v] > 0 then begin Next := v; if CanGoBack(Current, Next) then Break; end; if Next <> 0 then begin Dec(a[Current, Next]); Dec(a[Next, Current]); {Xoá bỏ cạnh vừa đi qua} Write(Next:5); {In kết quả đi tới Next} Inc(count); if count mod 16 = 0 then WriteLn; {In ra tối đa 16 đỉnh trên một dòng} Current := Next; {Lại tiếp tục với đỉnh đang đứng là Next} end; until Next = 0; {Cho tới khi không đi tiếp được nữa} WriteLn; end; begin Assign(Input, 'EULER.INP'); Reset(Input); Assign(Output, 'EULER.OUT'); Rewrite(Output); Enter; FindEulerCircuit; Close(Input); Close(Output); end.

VI. 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ên thuộ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ới khi 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èn và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ớn hơ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 đắn củ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ông có chu trình Euler. Mô hình thuật toán có thể viết như sau: ; <Mô tả các phương thức Push (đẩy vào) và Pop(lấy ra) một đỉnh từ ngăn xếp Stack, phương thức Get cho biết phấn tử nằm ở đỉnh Stack. Khác với Pop, phương thức Get chỉ cho biết phần tử ở đỉnh Stack chứ không lấy phần tử đó ra>; while Stack ≠∅ do begin x := Get; if then {Từ x còn đi hướng khác được} begin Push(y);

Lê Minh Hoàng

Lý thuyết đồ thị

\ 51 [

; end else {Từ x không đi tiếp được tới đâu nữa} begin x := Pop; ; end; end;

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 đỉnh có 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ứa toà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 106 cạ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. PROG06_2.PAS * Thuật toán hiệu quả tìm chu trình Euler program Euler_Circuit; const 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; begin FillChar(a, SizeOf(a), 0); ReadLn(n); while not SeekEof do begin ReadLn(u, v, k); a[u, v] := k; a[v, u] := k; end; 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; begin Pop := Stack[last]; Dec(last); end;

{Lấy một đỉnh khỏi ngăn xếp, trả về trong kết quả hàm}

function Get: Integer; begin Get := Stack[last]; end;

{Trả về phần tử ở đỉnh (Top) ngăn xếp}

procedure FindEulerCircuit; var

Lê Minh Hoàng

Lý thuyết đồ thị

\ 52 [

u, v, count: Integer; begin 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(Pop:5, ' '); {In ra phần tử đỉnh ngăn xếp} if count mod 16 = 0 then WriteLn; {Output không quá 16 số trên một dòng} end; end; end; begin Assign(Input, 'EULER.INP'); Reset(Input); Assign(Output, 'EULER.OUT'); Rewrite(Output); Enter; FindEulerCircuit; Close(Input); Close(Output); 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. C

B

E

M

J

F

K

A

D

H

I

N

L

M D A B C M F G N L I J K N H E M

Lê Minh Hoàng

G