Do Thi

Đồ thị Một số khái niệm Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này. Ta gọi tập các đỉnh là V, tập các cạnh là E , do đó đồ thị G = (V,E).

Đơn đồ thị vô hướng.

Các cạnh giữa các đỉnh không định hướng, cho phép đi theo cả 2 chiều ta gọi là đồ thị vô hướng.

Đa đồ thị vô hướng

Giữa 2 đỉnh chỉ có nhiều hơn 1 đường đi ta gọi là đa đồ thị, nếu chỉ có tối đa là 1 thì gọi là đơn đồ thị.

Đa đồ thị có hướng.

Nếu cạnh nối giữa 2 đỉnh xác định hướng đi, ta gọi là đồ thị có hướng.

Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và sẽ ký hiệu là deg(v).

deg(a) = 1, deg(b) = 4, deg(c) = 4, deg(f) = 3,deg(d) = 1, deg(e) = 3, deg(g) = 0 Định lý . Giả sử G = (V, E) là đồ thị vô hướng với m cạnh. Khi đó tổng bậc của tất cả các đỉnh bằng hai lần số cung. Hệ quả. Trong đồ thị vô hướng, số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số chẵn. Nếu e = (u, v) là cung của đồ thị có hướng G thì ta nói hai đỉnh u và v là kề nhau, và nói cung (u, v) nối đỉnh u với đỉnh v hoặc cũng nói cung này là đi ra khỏi đỉnh u và vào đỉnh v. Ta gọi bán bậc ra (bán bậc vào) của đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là deg+(v) (deg-(v))

deg-(a)=1, deg-(b)=2, deg-(c)=2, deg-(d)=2, deg-(e) = 2. deg+(a)=3, deg+(b)=1, deg+(c)=1, deg+(d)=2, deg+(e)=2. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị G = (V, E) là dãy x0, x1,…, xn-1, xn trong đó u = x0 , v = xn , (xi , xi+1) thuộc E, i = 0, 1, 2,…, n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (x0, x1), (x1, x2), …, (xn-1, xn) Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại.

Trên cả 2 đồ thị vô hướng: a, d, c, f, e là đường đi đơn độ dài 4. Còn d, e, c, a không là đường đi, do (c,e) không phải là cạnh của đồ thị. Dãy b, c, f, e, b là chu trình độ dài 4. Đường đi a, b, e, d, a, b có độ dài là 5 không phải là đường đi đơn, do cạnh (a, b) có mặt trong nó 2 lần

Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.

đồ thị G liên thông, đồ thị H không liên thông.

Trong trường hợp đồ thị là không liên thông, nó sẽ rã ra thành một số đồ thị con liên thông đôi một không có đỉnh chung. Những đồ thị con liên thông như vậy ta sẽ gọi là các thành phần liên thông của đồ thị. Đối với đồ thị có hướng có hai khái niệm liên thông phụ thuộc vào việc ta có xét đến hướng trên các cung hay không.

G - liên thông mạnh, H - liên thông yếu.

Đồ thị có hướng G = (V, E) được gọi là liên thông mạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó. Đồ thị có hướng G = (V, E) được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là vô hướng liên thông.

Đồ thị đầy đủ n đỉnh, ký hiệu bởi Kn, là đơn đồ thị vô hướng mà giữa hai đỉnh bất kỳ của nó luôn có cạnh nối.

Đồ thị vòng Cn, n≥3. gồm n đỉnh v1, v2,. . . .vn và các cạnh (v1,v2), (v2,v3) . . . (vn-1,vn), (vn,v1).

Biểu diễn đồ thị trong máy tính Đồ thị không trọng số G=(V,E), với tập đỉnh V={ 1, 2,. . . ,n} , tập cạnh E={ e1, e2,. . .,em } . Ta gọi ma trận kề của đồ thị G là ma trận. A={ ai,j : i,j=1, 2,. . . ,n} Với các phần tử được xác định theo qui tắc sau đây: ai, j = 0, nếu (i,j) ∉ E và ai,j = 1 , nếu (i,j) ∈ E, i, j=1, 2,. . .,n. Có thể biểu diễn đồ thị thông qua danh sách kề. Khi đó ứng với n đỉnh của đồ thị, ta có mảng n danh sách. Trong đó mỗi danh sách ứng với 1 đỉnh và lưu trữ các đỉnh kề với nó.

Danh sách kề có thể viết như sau: 1: (2,5) ; 2: (1,3,4,5); 3: (2,4) ; 4: (2,3,5); 5: (1,2,4)

Danh sách kề có thể viết như sau: 1: (2,4); 2: (5); 3: (5,6); 4: (2); 5: (4); 6: (6) Đối với đồ thị có trọng số thì: ai, j = +∞, nếu (i,j) ∉ E ; ai,j = 0 , nếu i = j và ai,j = wi,j , nếu (i,j) ∈ E, i, j=1, 2,. . .,n. và wi,j là trọng số trên cung (i,j). 0 ∞ 20 ∞ ∞ ∞

50 0 ∞ 20 ∞ ∞

Ma trận kề 10 ∞ 15 ∞ 0 15 ∞ 0 ∞ 30 ∞ 3

45 10 ∞ 35 0 ∞

∞ ∞ ∞ ∞ ∞ 0

Mỗi phần tử trong danh sách kề cho đồ thị có trọng số có 2 phần: chỉ số của đỉnh và trọng số trên cung tương ứng.

Duyệt đồ thị theo chiều sâu (thuật toán DFS) Ý tưởng chính của thuật toán có thể trình bày như sau: • Ta sẽ bắt đầu tìm kiếm từ một đỉnh v0 nào đó của đồ thị. • Sau đó chọn u là một đỉnh tuỳ ý kề với v0 và chưa được duyệt. • Lặp lại quá trình đối với u. Đây là thủ tục đệ quy. • Quá trình đệ quy kết thúc khi không chọn được đỉnh u nữa. Thủ tục đệ quy được viết như sau: Procedure DFS(v); (*tim kiem theo chieu sau bat dau tu dinh v; cac bien Chuaxet, Ke la bien toan cuc*) Begin Tham_dinh(v); Chuaxet[v]:=false; For u là Ke(v) do If Chuaxet[u] then DFS(u); End; (*dinh v da duyet xong*)

Duyệt toàn bộ đồ thị theo chiều sâu: Begin for v thuộc V do Chuaxet[v]:=true; for v thuộc V do if Chuaxet[v] then DFS(v); End. Độ phức tạp là : O(n+m)

Ví dụ duyệt đồ thị bắt đầu từ đỉnh số 1.

Quá trình duyệt như sau: • 1  2  4  6  5  8  9 : kết thúc đệ quy với đỉnh 9. •  quay lại 8 : kết thúc đệ quy với 8 •  quay lại 5 : kết thúc đệ quy với 5. •  quay lại 6  7  3 : kết thúc đệ quy với 3. •  quay lại 7 : kết thúc đệ quy với 7. •  quay lại 6  13 : kết thúc đệ quy với 13. •  quay lại 6: kết thúc đệ quy với 6. •  quay lại 4 : kết thúc đệ quy với 4. •  quay lại 2 : kết thúc đệ quy với 2. •  quay lại 1  12  10  11 : kết thúc đệ quy với 11. •  quay lại 10 : kết thúc đệ quy với 10 •  quay lại 12 : kết thúc đệ quy với 12. •  quay lại 1 : kết thúc đệ quy với 1, các đỉnh đều đã duyệt  kết thúc chương trình.

Duyệt đồ thị theo chiều rộng (thuật toán BFS) Ý tưởng chính của thuật toán như sau: • Sử dụng 1 hàng đợi để lưu trữ các đỉnh sẽ được duyệt. • Ban đầu đưa đỉnh bắt đầu duyệt u vào hàng đợi. • Thực hiện quá trình lặp cho đến khi hàng đợi rỗng. Mỗi bước lặp làm như sau: o Lấy 1 đỉnh v ra khỏi hàng đợi. Thực hiện các công việc cần thiết với đỉnh đó. o Xác định các đỉnh w kề với đỉnh v mà chưa duyệt. o Đưa các đỉnh w này vào hàng đợi. Thủ tục được viết như sau: Procedure BFS(u); (*Tim kiem theo chieu rong bat dau tu dinh u, cac bien Chuaxet, Ke la bien cuc bo*) Begin QUEUE:= Ø; QUEUE  u; (* nap u vao QUEUE*) Chuaxet[v]:=false; While QUEUE ≠ Ø do Begin v  QUEUE:; (*lay p tu QUEUE:*) Tham_dinh(v); For w là Ke(v) do If Chuaxet[w] them Begin QUEUE  w; Chuaxet[w]:=false; End; End; End;

Duyệt toàn bộ đồ thị theo thuật toán BFS: Begin (*khởi tạo ban đầu *) for mọi k thuộc V do Chuaxet[k]:=true; for u thuộ V do if Chuaxet[u] then BFS(v); End. Thuật toán BFS có độ phức tạp: O(n+m)

Vẫn ví dụ như trên, duyệt bằng thuật toán BFS từ đỉnh 1: Thứ tự làm như sau: Đưa đỉnh 1 vào hàng đợi, bắt đầu quá trình lặp: • Lấy đỉnh 1 ra khỏi hàng đợi. Đưa các đỉnh {2,4,12} vào hàng đợi. • Lấy 2 ra khỏi hàng đợi. • Lấy 4 ra khỏi hàng đợi. Đưa {6,7} vào. • Lấy 12 ra,và đưa {10,11} vào. • Lấy 6 ra, đưa {5,13} vào. • Lấy 7 ra, đưa {3} vào. • Lấy 10 ra. • Lấy 8 ra. • Lấy 5 ra, đưa {8,9} vào. • Lấy 13 ra. • Lấy 3 ra. • Lấy 8 ra. • Lấy 9 ra  hàng đợi rỗng  kết thúc!

Ứng dụng của thuật toán duyệt Ta thấy, tư tưởng của thuật toán duyệt là xuất phát từ 1 đỉnh u, và đi thăm các đỉnh v còn lại trong đồ thị nếu như tồn tại 1 đường đi từ đỉnh u đến v. Như vậy ta sẽ giải quyểt được 2 bài toán như sau: • Tìm 1 đường đi giữa 2 đỉnh bất kỳ. • Kiểm tra tính liên thông của đồ thị và tìm các thành phần liên thông trong đồ thị. Để xác định được 1 đường đi từ đỉnh u đến đỉnh v, ta cần phải làm như sau: • Dùng thủ tục duyệt theo chiều sâu với đỉnh u. • Trong quá trình duyệt có sử dụng mảng các biến trạng thái Chuaxet[k] (hay Free[k]) để kiểm tra đỉnh k đã được duyệt chưa. • Để xác định đường đi ta dùng mảng biến lưu trữ vết Truoc[k] = t, có nghĩa là từ đỉnh t sẽ chuyển đến đỉnh k. Bổ sung vào các thủ tục DFS và BFS như sau: Đối với DFS bổ sung code như sau: Đối với BFS bổ sung code như sau: If Chuaxet[u] then Begin Truoc[u]:= v; Chuaxet[u] = false; DFS(u); End;

If Chuaxet [u] then Begin QUEUE  u; Chuaxet[u]:= false; Truoc[u]:= p; End;

Xác định đường đi từ u đến v như sau: While (v ≠ u) do Begin In giá trị v ra ngoài màn hình; v = Truoc[v] ; // gán v bằng đỉnh mà từ nó nhảy đến v hiện tại End; In giá trị u ra màn hình; Để xác định số thành phần liên thông trong đồ thị thì ta dùng thêm 1 biến count đế đếm. Khi đó các bước phải làm như sau: • Khởi tạo các mảng biến cần thiết, và count = 0. • Xét với mọi đỉnh u trong đồ thị, nếu như đỉnh u chưa được duyệt thì: o Tăng giá trị của biến count lên 1 đơn vị o Thực hiện các thuật toán duyệt đối với đỉnh u. • Nếu kết quả biến count = 1 thì đồ thị liên thông. Trong trường hợp còn lại thì giá trị của count chính là số thành phần liên thông của đồ thị. Viết thêm code để xác định số thành phần liên thông: Count :=0; Count :=0; If Chuaxet[u] then If Chuaxet[u] then Begin Begin Count := Coutn + 1; Count := Coutn + 1; DFS(u); BFS(u); End; End;

Thuật toán tìm đường đi ngắn nhất Ford-Bellman Thuật toán này Ford-Bellman xác định tất cả các đường đi ngắn nhất từ một đỉnh u cho trước đến các đỉnh v còn lại trong đồ thị. Tư tưởng thuật toán như sau: • Sử dụng mảng D[v] là giá trị khoảng cách bé nhất đi từ đỉnh u đến đỉnh v. Ban đầu chỉ có D[u] = 0, còn tất cả các đỉnh v còn lại đều có D[v] = ∞. • Để tối ưu các giá trị D[v] thì ta cần chọn các đỉnh trung gian k, để sau đó so sánh giá trị D[v] hiện tại với tổng khoảng cách D[k] và A[k][v]. Lưu ý ở đây A[k][v] chính là trọng số trên cạnh (kv). • Như vậy với mỗi đỉnh trung gian k ta cần phải tối ưu (n-1) đỉnh còn lại. Hơn nữa ta có n cách chọn giá trị của k. Như vậy ta có 2 vòng lặp lồng nhau. • Giả sử ở thời điểm T1, chúng ta dùng đỉnh k1 là đỉnh trung gian, và tối ưu được giá trị tại đỉnh k2. Đến thời điểm T2 , chúng ta chọn k2 là đỉnh trung gian thì lại có thể tối ưu được giá trị tại đỉnh k1. Như vậy việc chọn 1 đỉnh là trung gian phụ thuộc vào (n-1) đỉnh còn lại.Để vét hết các khả năng, ta cũng cho mỗi đỉnh được chọn làm trung gian (n-1) lần. Như vậy ta có vòng lặp thứ 3 nằm ngoài 2 vòng lặp trên. • Tuy nhiên để hiệu quả hơn, tại mỗi bước của vòng lặp ngoài cùng ta kiểm tra xem các giá trị tại các đỉnh có thay đổi không,nếu đã tối ưu và không thay đổi nữa thì ta sẽ dừng chương trình. Về cơ bản thuật toán mô tả như sau: Procedure Ford_Bellman (u) Begin for i:=1 to n-1 do // số lần chọn một đỉnh làm trung gian for k thuộc V\{u} do // chọn 1 đỉnh là trung gian for v thuộc V do // tối ưu với tất cả các đỉnh còn lại if d[v] > d[k] +a[k][v] then // nếu đk tối ưu xảy ra begin d[v]:=d[k]+a[k][v]; // gán giá trị tối ưu mới Truoc[v]:= k; // lưu lại vết di chuyển. end; End; Một số chú ý: • Thuật toán trên làm việc với đồ thị có trọng số không âm,hoặc không có chu trình mà tổng trọng số là âm. • Thuật toán trên làm việc với ma trận kề sẽ có độ phức tạp là O(n3). 0

45 0

10

50

50

1 20

20

2

15

45

35

3

∞

0

50

50

1 20

20

5

10

2

15

4

10

45

3

0

10

30

∞

45

0

35

15

∞

3

45 0

10

30

15

10

4

10

50

1 20

20

5

10

2

15

4

10

45

35

3

25

0

50

45

1 20

20

5

4

10

45

35 30

15

∞

3

45 0

10

30

15

∞

3

50

28 10

2

15

3

25

3

5

K= 0 K = 1 K=2 K= 3 Ví dụ trên thực hiện với đỉnh xuất phát là 0. Ta chọn các giá trị trung gian k = 0, 1, 2, 3 sau đó các giá trị D[v] không tối ưu hơn được nữa, và chương trình dừng ở đây.

Thuật toán tìm đường đi ngắn nhất Dijkstra Thuật toán này xác định đường đi ngắn nhất giữa 2 đỉnh cụ thể từ u đến v. Tư tưởng của thuật toán như sau: • Dùng một tập S lưu trữ các đỉnh đã được duyệt. Cách đơn giản nhất phân biệt giữa đỉnh đã duyệt với đỉnh chưa duyệt là dùng mảng biến trạng thái Free[k]. • Dùng mảng phụ D[k] xác định giá trị khoảng cách ngắn nhất đi từ u đến k. Ban đầu ta chỉ gán D[u] = 0 và D[k] = ∞ với v ≠ u. • Bắt đầu quá trình duyệt các đỉnh k khác u và quá trình lặp chỉ kết thúc khi : o Đã đạt đến đỉnh đích v . o Hoặc không thể duyệt tiếp được nữa. • Mỗi bước của quá trình duyệt như sau: o Xác định đỉnh k trong số các đỉnh chưa được duyệt, sao cho D[k] là bé nhất. o Nếu k được chọn chính là đỉnh đích v ta kết thúc vòng lặp. o Nếu giá trị D[k] được chọn là ∞ (tức là không chọn thêm được nữa) ta cũng kết thúc vòng lặp. o Trong trường hợp còn lại, ta đưa k vào tập S (gán Free[k] = 0) và tối ưu các đỉnh còn lại theo nguyên tắc sau: nếu D[t] > D[k] + A[k][t]  D[t] = D[k] + A[k][t]; Thuật toán được mô tả như sau: Procedure Dijstra (u, v); Begin while True do begin Tìm đỉnh k thoả mãn Free[k] = 1 và D[k] nhỏ nhất ; if D[k] = ∞ hoặc k = v then BREAK; For v thuộc V do If Free[v] = 1 và d[v]>d[k]+a[k][v] then begin d[v]:=d[k]+a[k][v]; Truoc[v]:=u; end; end; End; Một số chú ý: • Thuật toán làm việc với đồ thị có trọng số không âm,hoặc không có chu trình mà tổng trọng số âm. • Độ phức tạp của thuật toán là O(n2). Ví dụ với U = 0, V = 5 0

45 0

10

50

∞

∞

1

10

20 35

20

∞

15

3

∞

∞ 3

0

45 0

10

30

15 2

4

5

Bước 1: K = 0

50

1 20

20

45

50 10 35

10

15

3

∞

0

45

5

Bước 2: K = 2

1 20

20

45

50

2

10

15

4

10 35

3

25

∞ 3

45

0

0

10

30

15

∞ 3

50

0

10

30

15 2

4

5

Bước 3: K = 3

50

1 20

20

45

45

4

10 35

45 0

10

30

15

0

50

1 20

20

45

45

35 30

15

28 2

10

15

3

25

3

5

Bước 4: K = 5

4

10

28 2

10

15

3

25

3

5

Bước 5: K = 1.

Thuật tóan tìm đường đi ngắn nhất Floyd- Warshall Thuật toán này xác định đường đi ngắn nhất giữa mọi cặp đỉnh trng đồ thị. Tư tưởng thuật toán như sau: • Để xác định đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị, thì ta phải xác định tất cả n*(n-1) giá trị, tương ứng với các cặp (u,v) trên đồ thị. • Khi đó ta dùng luôn ma trận trọng số Anxn làm ma trận lưu kết quả. Khi đó A[i][j] là giá trị khoảng cách ngắn nhất đi từ đỉnh i đến đỉnh j. • Tư tưởng thuật toán này cũng khá đơn giản: o Chọn 1 đỉnh là trung gian, giả sử là đỉnh k. o Tối ưu hóa đường đi từ đỉnh u đến đỉnh v theo k. Tức là ta so sánh A[u][v] với tổng A[u][k] và A[k][v]. Nếu đi từ u đến v dài hơn so với đi từ u qua k rồi đến v thì ta sẽ tối ưu giá trị A[u][v]. o Ta thấy có n cách chọn đỉnh k, với mỗi k có n cách chọn đỉnh xuất phát u và với mỗi u ta có n cách chọn đỉnh kết thúc v. Như vậy ta có 3 vòng lặp lồng nhau. Cũng ứng dụng tư tưởng này để xác định các thành phần liên thông của đồ thị. Đây là thuật toán Warshall. Tư tưởng chính là: • Nếu từ u đế k có đường đi, tức là A[u][k] = 1 và từ k đến v cũng có đường đi, tức là A[k] [v] = 1 thì chắc chắn có đường đi từ u đến v  A[u][v] = 1. Cả 2 thuật toán đều có độ phức tạp là : O(n3). Thuật toán được mô tả như sau: Procedure Floyd_Warshall Begin For k = 1 to n do For u = 1 to n do For v = 1 to n do If A[u][v] > A[u][k] + A[k][v] then A[u][v] = A[u][k] + A[k][v]; End;

Đồ thị

Procedure Warshall Begin For k = 1 to n do For u = 1 to n do For v = 1 to n do If A[u][k] = 1 và A[k][v] = 1 then A[u][v] = 1; End;

Các ma trận ban đầu

Kết quả thực hiện