4.1.1 Định nghĩa về đồ thị hữu hạn
a) Đồ thị hữu hạn (Graph) là một cặp tập hợp; ký hiệu là G = {X.A}, trong đó X = {x1, x2,...., xn} là tập hữu hạn các điểm (đỉnh, nút). A = {(i, j)} là tập hợp các cạnh (cung) nối tất cả hoặc một phần các điểm xiX lại với nhau, cách nối điểm i với điểm j, ký hiệu là (i, j).
Thí dụ 4.1 G = {X.A}, trong đó X = {x1, x2, x3, x4, x5, x6, x7} và A = {(1,2), (2,1), (1,4),(1,3), (2,5), (4,3), (3,5), (3,6), (3,7), (5,7), (4,6), (6,7)}
Hình 4.1
Đồ thị vô hướng: Ký hiệu {GX.A}trong đó X là tập các đỉnh (nút, điểm) và A là tập các nhánh. Nhánh là một cặp không kể đến thứ tự hai đỉnh khác nhau xi và xj nào đó với xi X, xjX, ký hiệu là (i, j). Vậy (xi, xj) = (xj, xi) trong đồ thị vô hướng.
Cung còn được gọi là cạnh có hướng. Cung (xi, xj) được gọi là nối đỉnh xi với đỉnh xj. Cấp của một đỉnh là số cung nối tới nó. Cấp của đồ thị là cấp cực đại trong các cấp của các đỉnh của nó.
Một đường đi từ đỉnh x1 đến đỉnh xt là bộ t nút khác nhau x1, x2, ..., xk sao cho (xk , xk+1)A với k= 1, 2, ..., t-1.
Chu trình (mạch vòng) là bộ t đỉnh: x1, x2,..., xt sao cho x1,...., xt-1 là một đường đi, xt ≡ x1 và có ít nhất ba đỉnh khác nhau (tức là t - 1 ≥ 3).
Đồ thị vô hướng được gọi là liên thông nếu ứng với mỗi cặp xi, xjX đều có một đường đi từ xi
đến xj.
Số các đỉnh của đồ thị thường ký hiệu là n còn số nhánh là m.
Đồ thị có hướng: Ký hiệu là G = {X.A} nhưng mỗi nhánh là là một cặp có thứ tự. Vì vậy (xi , xj)
≠ (xj, xi). Nhưng đồ thị không được chứa cung tự nối dạng (xi, xi).
x1
x4
x6
x3
x2 x5
x7
x1
x2
x4
x3 x5
Hình 4.2 Thí dụ 4.2: Hình 4.2 là một đồ thị có hướng
G = {X.A}.Với X = {x1, x2, x3, x4, x5} và A
={(x1,x2),(x2,x1),(x1,x3),(x1,x4),(x3,x2),(x4,x3), (x3,x5)}. Ta sẽ nói là cung (xi, xj) ký hiệu (i, j) là đi từ đỉnh i đến đỉnh j.
Đồ thị vô hướng tương ứng với một đồ thị có hướng là đồ thị nhận được khi không tính đến hướng trên các cungnữa.
Đồ thị có hướng là liên thông nếu đồ thị vô hướng tương ứng là liên thông
PTIT PTIT
120 Mỗi đường đi trong đồ thị vô hướng tương ứng đều gọi là một đường đi trong đồ thị có hướng.
Nhưng đồ thị có thể chứa cả hai cung (i, j) và (j, i), nên để xác định một đường đi phải nói rõ cả dãy đỉnh x1, ..., xt và dãy cung a1,...., at-1. Khi đó nếu một cung ak có dạng "thuận" ak = (ik, ik+1) thì ta nói ak là cung tiến trong đường đi này. Ngược lại nếu ak = (ik+1, ik) thì ak là cung lùi.
Chu trình cũng được định nghĩa như ở đồ thị vô hướng, nhưng ở đây cho phép chu trình chỉ gồm hai đỉnh khác nhau.Một đường đi hoặc chu trình được gọi là có hướng nếu nó chỉ chứa các cung tiến. Trong hình 4.2 thì (1,3), (3,2), (2,1) là một chu trình có hướng. Nhưng (1,3), (1,2), (3,2) là một chu trình không có hướng vì (1,3) và (3,2) là cung lùi.
Đường đi tối giản là đường đi qua một đỉnh của đường đi đó chỉ một lần. Tương tự chu trình tối giản là chu trình mà trong đó mỗi đỉnh của đồ thị chỉ gặp một lần, từ đỉnh đầu tiên đến đỉnh cuối cùng.
4.1.2 Các yếu tố khác của đồ thị a. Ánh xạ và ánh xạ ngược:
- Một ánh xạ của đỉnh xi trong đồ thị G = {X.A}ký hiệu là Г(xi) là tập hợp các đỉnh cuối của tất cả các cung có đỉnh đầu là xi. Thí dụ trong hình 4.2: Г(x1) = {x2, x3, x4}.
- Ánh xạ ngược của một đỉnh xj trong đồ thị G ={X.A}ký hiệu Г-1(xi) là tập hợp các đỉnh đầu của tất cả các cung có đỉnh cuối là xj. Chẳng hạn trong hình 4.3: Г-1(x3) = {x1, x4}.
b. Cây
Đồ thị vô hướng được gọi là cây nếu nó liên thông và không chứa chu trình. Mỗi đỉnh cấp 1 của cây gọi là một lá.
Định lý 4.1:
- Mỗi cây có hơn một đỉnh sẽ có lá.
- Đồ thị vô hướng là một cây khi và chỉ khi nó liên thông và có n- 1 cung.
- Với bất kỳ hai đỉnh xi ≠ xj trên cây đều có tồn tại duy nhất một đường đi từ xi tới xj. - Nếu thêm một cạnh mới vào một cây thì đồ thị mới nhận được có đúng một chu trình.
Cây bao trùm:(cây tối đại) của đồ thị liên thông, vô hướng G X.A là một cây trong G mà chứa tất cả các đỉnh của G. Vậy cây bao trùm là cây T có dạng T = {X.A1} trong đó A1A. Định lý 4.2 Giả sử {GX.A} là một đồ thị vô hướng liên thông và A0A . Nếu các cung của A0
không tạo thành một chu trình nào thì có thể bổ sung thêm các cung của đồ thị vào A0 để được tập mới A1 sao cho {X. A1} là một cây bao trùm.
Trong hệ thống kỹ thuật, người ta thường sử dụng các loại cây sau đây:
- Cây người chào hàng: Là một đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh chỉ qua một lần.
- Cây có chiều dài ngắn nhất: Là một đường đi nhận được từ đồ thị bằng cách loại ra khỏi nó các cung theo trình tự giảm dần chiều dài của cung và kiểm tra tính liên thông của đồ thị, hoặc đưa dần vào các cung vào đồ thị theo trình tự tăng dần chiều dài cung và cấm không được tạo thành chu trình.
- Cây Steiner: Nếu cho phép đưa thêm vào tập hợp đỉnh của đồ thị những đỉnh phụ thì độ dài của cây ngắn nhất có thể giảm xuống. Đỉnh phụ đưa thêm vào đồ thị có 3 nhánh cách nhau 1200 được gọi là đỉnh Steiner.
c. Lát cắt: là tập hợp các nhánh sao cho nếu loại chúng ra khỏi đồ thị thì đồ thị trở nên không liên thông.
PTIT PTIT
121 Lát cắt gọi là phân chia hai đỉnh xi và xj của đồ thị, nếu sau khi loại lát cắt này ra khỏi đồ thị thì hai đỉnh xi và xj không còn liên hệ với nhau nữa.
Lát cắt tối giản là lát cắt không chứa trong nó những lát cắt khác.
d. Đồ thị phẳng và đồ thị không phẳng:
- Đồ thị G = (X.A) được gọi là đồ thị phẳng nếu nó có thể biểu diễn được trên mặt phẳng hoặc mặt cầu sao cho không có bất kỳ hai cạnh nào cắt nhau.
- Đồ thị không thỏa mãn điều kiện trên gọi là đồ thị không phẳng.
e. Đồ thị đối ngẫu
Đối với một đồ thị G = (X. A), giữa một cặp đỉnh nào đó ta gọi là đỉnh vào (đỉnh đầu) và đỉnh ra (đỉnh cuối) ta có thể xây dựng được một đồ thị đối ngẫu G' = {X'.A} theo trình tự sau đây:
- Vẽ thêm một cung nối liền hai đỉnh "vào" và "ra" của đồ thị G = {X.A}.
- Trong mỗi "diện" của G = {X.A}("diện" là một phần của đồ thị được giới hạn bởi các cung mà bên trong nó không chứa các cung khác của đồ thị), kể cả diện ngoài (diện ngoài là phần mặt phẳng không giới hạn bởi các cung của đồ thị) ta đặt một đỉnh x' trong tập X' của đồ thị đối ngẫu sẽ được xây dựng.
- Nối các đỉnh trong tập X' lại với nhau bởi các cung, cắt các cung tương ứng của đồ thị phẳng ban đầu, số cung của đồ thị đối ngẫu đúng bằng số cung của đồ thị phẳng ban đầu.
Hướng của cung trong đồ thị đối ngẫu được xác định như sau: Nếu cung của đồ thị đối ngẫu đi từ một đỉnh nằm bên trong một diện của đồ thị phẳng ban đầu cắt cung của G ={X.A} có hướng thuận với chiều kim đồng hồ theo mạch vòng của đa diện, thì hướng của cung đang xét trong đồ thị đối ngẫu sẽ đi từ bên trong diện ra bên ngoài diện và ngược lại. Nếu cung của đồ thị phẳng ban đầu không có hướng thì cung tương ứng của G' = {X'.A} cũng không có hướng.
Hình 4.3a và 4.3b cho một thí dụ về cách xây dựng đồ thị đối ngẫu.
``
- Tính đối ngẫu của đường và lát cắt trong đồ thị phẳng
Đối với một đồ thị phẳng G = {X.A}, tương ứng với một cặp đỉnh "vào", "ra", ta có thể dựng một đồ thị đối ngấu G' = {X'.A}.
1
2 3
4 5
6
2'
3'
4'
5' 6'
1'
1'
2'
5'
3' 6'
4' a1
a2
a3
a4
a5
a6
a7
a8
a9
a1
a2
a3
a4
a5
a6
a9 a8
a7
Hình 4.3 a Hình 4.3 b
PTIT PTIT
122 Đường đi trong G = {X.A} sẽ tương ứng với lát cắt trong G' = {X'.A} và ngược lại. Ta có cặp đối ngẫu sau:
- Ý nghĩa mạng của đối ngẫu:
Giả sử ta phải chuyển lượng hàng bi > 0 từ mỗi đỉnh i = 1, 2, ..., n-1 tới đỉnh n theo một mạng riêng của mình. Khi đó nghiệm tối ưu của bài toán dòng trên mạng cho ta cách vận chuyển tốt nhất.
Lại giả sử có một công ty vận tải mở dịch vụ vận chuyển từ mọi đỉnh i đến đỉnh n (theo mạng của họ) với giá vận chuyển một đơn vị hàng là pi. Nếu (i, j) là một cung trong mạng riêng của ta và phí tổn vận chuyển một đơn vị hàng trên cung này là cij, thì ta có thể tự chuyển hàng từ i đến j rồi giao cho công ty vận tải chuyển nốt đến đỉnh n, với giá đơn vị là cij + pi. Công ty vận tải biết các véc tơ b và c và tìm cách bao hết việc vận chuyển hàng của ta, kể cả trên cung (i, j). Khi đó họ phải ra giá để cạnh tranh là pi ≤ cij + pj và pn = 0. Với giá đủ hấp dẫn này, coi như ràng buộc, mục đích của họ tất nhiên là làm cực đại doanh thu
1 n
1 i
i ib
p .Vậy bài toán của công ty chính là bài toán đối ngẫu với bài toán tự vận chuyển của ta. Định lý đối ngẫu mạnh của quy hoạch tuyến tính nói rằng doanh thu tối ưu của công ty đúng bằng phí tổn tối ưu khi ta tự vận chuyển bằng mạng riêng. Nói cách khác, nếu hai phía đều tìm cách vận chuyển tối ưu và giá của công ty đặt ra đúng thì cước phí là như nhau.
4.1.3. Biểu diễn đồ thị dưới dạng ma trận a. Ma trận liên hệ trực tiếp
Giả sử cho đồ thị G = {X .A}, ma trận liên hệ trực tiếp của nó được ký hiệu là A = {aij}, được xác định như sau:
0
aij 1
Thí dụ 4.3 Cho đồ thị G = {X.A} như hình 4.4. Khi đó ma trận liên hệ trực tiếp của đồ thị cho ở bảng 4.1
Trong G = {X.A} Trong G' = {X'.A}
Đường đi Lát cắt Lát cắt Đường đi
, nếu trong G = {X.A} có cung (i, j) (kể cả cung tự nối) , nếu trong G = {X.A} không có cung (i, j)
0 1 1 0 0 0
0 1 0 0 1 0
0 0 0 0 0 0
0 0 1 0 0 0
1 0 0 1 0 0
1 0 0 0 1 0
Bảng 4.1 PTIT PTIT
123
`
Với mỗi đồ thị G = {X.A}ta có một ma trận liên hệ trực tiếp tương ứng, xác định đầy đủ cấu trúc của đồ thị. Tổng các phần tử theo dòng trong bảng 4.1 cho ta số cung đi khỏi đỉnh xi, còn tổng các phần tử theo cột cho ta số cung đi vào đỉnh xi.
b. Ma trận liên hệ cung nút
Cho đồ thị G = {X.A} có n đỉnh và m cung. Ma trận liên hệ cung nút của đồ thị, ký hiệu là B = {bij}, có kích thước m×n với các phần tử được xác định như sau:
0
1 - 1 bij
Thí dụ 4.4 Đối với đồ thị cho ở hình 4.4 thì ma trận cung nút có dạng như ở bảng 4.2 Bảng 4.2
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
x1 1 1 0 0 0 0 0 -1 -1 0
x2 -1 0 0 1 0 0 0 0 0 0
x3 0 -1 0 0 -1 0 0 0 0 0
x4 0 0 0 0 1 -1 0 0 0 0
x5 0 0 0 -1 0 1 -1 1 0 0
x6 0 0 0 0 0 0 1 0 1 0
Vậy mỗi cột của B có đúng hai phần tử khác không là 1 và -1; chỉ đỉnh đầu và đỉnh cuối của cung tương ứng của cột này. Khi xét các hàng ta thấy hàng i ứng với đỉnh i và ràng buộc sẽ là:
i
I(i) j
ji O(i)
j ij T
ix x - x b
a
trong đó aTix là hàng i của ma trận B. Như vậy, các phần tử khác 0 (là 1 hoặc -1) trên hàng i của B ở cột nào thì có nghĩa là cung tương ứng cột đó có nối tới đỉnh i (1 ứng với cung đi ra từ đỉnh i, -1 ứng với cung đi vào đỉnh i). Ma trận B gọi là ma trận nối cung - nút hoặc gọi tắt là ma trận nối.
Nhận xét rằng tổng tất cả các hàng của B là véc tơ 0. Vì vậy n hàng của B là phụ thuộc tuyến tính. Vì vậy, có thể bỏ đi một hàng (nếu bài toán là chấp nhận được), thường là hàng ứng với đỉnh ra của đồ thị.
x1
x6
x2
x5
x3
x4
a1
a3
a2
a4 a5
a6
a7 a8
a9
a10
Hình 4.4
, nếu xi là đỉnh đầu của cung aj
, nếu xi là đỉnh cuối của cung aj
, nếu xi không phải là đỉnh đầu hoặc đỉnh cuối của cung aj hoặc nếu cung aj là cung tự nối
PTIT PTIT
124 4.2 Bài toán đường đi ngắn nhất
4.2.1 Ý nghĩa và nội dung bài toán
Bài toán đường đi ngắn nhất là một bài toán quan trọng nảy sinh từ nhiều bài toán thực tế về vận tải, mạng thông tin, điều khiển tối ưu,...Có thể phát biểu một dạng toán học chung cho các bài toán như vậy thành bài toán dòng trên mạng như sau. Cho một đồ thị có hướng G = {X.A}. Mỗi cung (i, j) có cước phí cij > 0 chính là độ dài của cung. Để tìm đường ngắn nhất từ một đỉnh s đến một đỉnh r ta sẽ thấy cần tính nhiều hoặc thậm chí đường ngắn nhất từ mọi đỉnh khác đỉnh r tới đỉnh r.
Vì vậy người ta gọi bài toán đường ngắn nhất là bài toán tìm đường đi ngắn nhất từ mọi đỉnh trong X tới một đỉnh r thuộc X cho trước, gọi là đỉnh gốc. Để đưa về bài toán dòng trên mạng, đặt bi = 1 cho mỗi đỉnh i ≠ r và
r i
i
r - b
b
Ta có thể giải bài toán đường ngắn nhất bằng thuật toán đơn hình mạng. Đường ngắn nhất từ đỉnh i tới đỉnh r chính là các cung thuộc cây bao trùm tối ưu T nối từ đỉnh i đến đỉnh r (đây là đường đi có hướng, trong đường đi không có cung lùi). Có nhiều cách để giải bài toán tìm đường đi ngắn nhất, nhưng trong khuôn khổ bài giảng này ta nghiên cứu một thuật toán tỏ ra có hiệu quả nhất, đó là thuật toán gán nhãn do Dijkstra công bố năm 1959. Ý tưởng của thuật toán là lần lượt tìm đường đi ngắn nhất từ mỗi đỉnh đến đỉnh gốc ký hiệu là n, bắt đầu từ đỉnh có đường đi này ngắn hơn cả, rồi theo thứ tự đỉnh có đường ngắn hơn làm trước. Cụ thể là lần lượt gán cho các đỉnh của đồ thị một số gọi là nhãn của đỉnh. Cho đỉnh vào của đồ thị là x1 có nhãn bằng 0, sau đó các cung đi từ x1 đến các đỉnh xj, jГ(x1), ta chọn cung có độ dài nhỏ nhất và gán nhãn cố định cho nó.Tiếp theo trong các cung đi từ một đỉnh đã có nhãn cố định đến một đỉnh có nhãn tạm thời ta lại chọn cung sao cho độ dài của nó cộng với nhãn của đỉnh đã được gán nhãn là nhỏ nhất, giá trị này được gán cho đỉnh cuối của đường đi này. Quá trình tiếp tục cho đến khi đỉnh cuối (đỉnh gốc) được gán nhãn cố định.
4.2.2 Thuật toán Dijkstra
Cho đồ thị G = {X.A}, tìm đường đi ngắn nhất từ xs đến xt, ký hiệu L(xi) là nhãn của đỉnh xi (i = n
1, ). Thuật toán như sau:
Bước 1: Đặt L(x1) = L(xs) = +0 và coi đây là nhãn cố định.
Đặt L(xi) = +∞ với i≠1 và xem các đỉnh này có nhãn tạm thời.
Gán xp ≡ xs
Bước 2: Với tất cả các đỉnh xiГ(xp) có nhãn tạm thời sẽ được thay đổi nhãn tạm thời mới theo điều kiện sau:
L(xi) = Min{L(xi); L(xp) + cpi} (4.1) Bước 3: Trong số các đỉnh đang có nhãn tạm thời (cũ và mới thay đổi) ta tìm một đỉnh j có nhãn tạm thời thỏa mãn điều kiện:
L*(xj) = Min{L(xi)│L(xi) có nhãn tạm thời mới} (4.2) Coi nhãn của đỉnh xj ứng với điều kiện (4.2) là nhãn cố định và đặt xp ≡ xj chuyển sang bước sau.
Bước 4:
a. Nếu chỉ cần tìm đường đi ngắn nhất từ đỉnh xs đến đỉnh xt thì có hai trường hợp xảy ra:
- Khi xp≡xt thì L(xp) là chiều dài đường đi ngắn nhất cần tìm. Thuật toán dừng.
- Khi xp ≠ xt quay lại bước 2.
PTIT PTIT
125 b. Nếu cần tìm đường đi ngắn nhất từ đỉnh xs đến các đỉnh còn lại của đồ thị, thì có hai trường hợp xảy ra:
- Khi nhãn của tất cả các đỉnh là nhãn cố định thì trị số nhãn của đỉnh xj (j ≠ s) là chiều dài đường đi ngắn nhất từ đỉnh xs đến đỉnh xj trong đồ thị G = {X.A}.
- Nếu đồ thị vẫn còn đỉnh có nhãn tạm thời thì quay lại bước 2.
Thí dụ 4.5 Cho đồ thị G ={X.A} thể hiện bởi ma trận khoảng cách cho ở bảng 4.3. Các trị số trong các ô biểu thị độ dài đường đi từ i đến j.(đơn vị tính: km)
Hãy vẽ đồ thị G và tìm đường đi ngắn nhất từ đỉnh x1 đến tất cả các đỉnh còn lại.
Bảng 4.3
x1 x2 x3 x4 x5 x6 x7 x8 x9
x1 10 3 6 12
x2 10 18 2 13
x3 18 25 20 7
x4 25 5 16 4
x5 5 10
x6 20 10 14 15 9
x7 2 4 14 24
x8 6 23 5
x9 12 13 9 24 5
Giải bài toán bằng thuật toán Dijkstra:
Hình 4.5 Vòng lặp 1:
Bước 1: Đặt L(x1) = +0; L(xi) = +∞ i ≠ 1. Đặt xp ≡ x1 → B2
Bước 2: Г(xp) = Г(x1) = {x2, x7, x8, x9}, các đỉnh x2, x7, x8, x9 được thay nhãn tạm thời như sau:
L(x2) = Min{L(x2); L(xp)+cp2} = Min{+∞; 0 + 10} = 10 L(x7) = Min{L(x7); L(xp)+cp7} = Min{+∞; 0 + 3} = 3 L(x8) = Min{L(x8); L(xp)+cp8} = Min{+∞; 0 + 6} = 6 L(x9) = Min{L(x9); L(xp)+cp9} = Min{+∞; 0 + 12} = 12 Bước 3: Gán nhãn có định
x1
x2 x3
x4
x6
x7
x9
x8 x5
10
3
12
2 13
6 15
18 18
25 7 20
4 14
5 24
9
23
10 5
PTIT16
PTIT
126 L*(xi) = Min{L(x2), L(x7), L(x8), L(x9), L(x3), L(x4), L(x5), L(x6)
= Min{10, 3, 6, 12, +∞, +∞, +∞, +∞, +∞} = 3- ứng với đỉnh x7. Gán xp ≡ x7 → B4 Bước 4: Đồ thị còn có nhãn tạm thời → B2
Vòng lặp 2:
Bước 2: Г(xp) = Г(x7) = {x2, x4, x6, x9}, các đỉnh x2, x4, x6, x9 được thay nhãn tạm thời như sau:
L(x2) = Min{L(x2); L(xp)+cp2} = Min{10; 3 + 2} = 5 L(x4) = Min{L(x4); L(xp)+cp4} = Min{+∞; 3 + 4} = 7 L(x6) = Min{L(x6); L(xp)+cp6} = Min{+∞; 3 + 14} = 17 L(x9) = Min{L(x9); L(xp)+cp9} = Min{12; 3 + 24} = 12 Bước 3: Gán nhãn có định
L*(xi) = Min{L(x2), L(x8), L(x9), L(x4), L(x6), L(x3), L(x5),
= Min{5, 6, 12, 7, 17 +∞, +∞, +∞, +∞, +∞} = 5- ứng với đỉnh x2. Gán xp ≡ x2 → B4 Bước 4: Đồ thị còn có nhãn tạm thời → B2
Vòng lặp 3:
Bước 2: Г(xp) = Г(x2) = {x3, x9}, các đỉnh x3, x9 được thay nhãn tạm thời như sau:
L(x3) = Min{L(x3); L(xp)+cp3} = Min{+∞; 5 + 18} = 23 L(x9) = Min{L(x9); L(xp)+cp9} = Min{12; 5 + 13} = 12 Bước 3: Gán nhãn có định
L*(xi) = Min{L(x8), L(x9), L(x4), L(x6), L(x3), L(x5),
= Min{ 6, 12, 7, 17, 23 +∞} = 6- ứng với đỉnh x8. Gán xp ≡ x8 → B4 Bước 4: Đồ thị còn có nhãn tạm thời → B2
Vòng lặp 4:
Bước 2: Г(xp) = Г(x8) = {x5, x6, x9}, các đỉnh x5, x6, x9 được thay nhãn tạm thời như sau:
L(x5) = Min{L(x5); L(xp)+cp5} = Min{+∞; 6 + 23} = 29 L(x6) = Min{L(x6); L(xp)+cp6} = Min{17; 6 + 15} = 17 L(x9) = Min{L(x9); L(xp)+cp9} = Min{12; 6 + 5} = 11 Bước 3: Gán nhãn có định
L*(xi) = Min{L(x9), L(x4), L(x6), L(x3), L(x5),
= Min{ 11, 7, 17, 23, 29} = 7- ứng với đỉnh x4. Gán xp ≡ x4 → B4 Bước 4: Đồ thị còn có nhãn tạm thời → B2
Vòng lặp 5:
Bước 2: Г(xp) = Г(x4) = {x3,x5, x6}, các đỉnh x3,x5, x6 được thay nhãn tạm thời như sau:
L(x3) = Min{L(x3); L(xp)+cp3} = Min{23; 7 + 25} = 23 L(x5) = Min{L(x5); L(xp)+cp5} = Min{29; 7 + 5} = 12 L(x6) = Min{L(x6); L(xp)+cp6} = Min{17; 7 + 16} = 17 Bước 3: Gán nhãn có định
L*(xi) = Min{L(x9), L(x6), L(x3), L(x5),
= Min{ 11, 17, 23, 12} = 11- ứng với đỉnh x9. Gán xp ≡ x9 → B4 Bước 4: Đồ thị còn có nhãn tạm thời → B2
Vòng lặp 6:
Bước 2: Г(xp) = Г(x9) = {x6}, các đỉnh x6 được thay nhãn tạm thời như sau:
L(x6) = Min{L(x6); L(xp)+cp6} = Min{17; 11 + 9} = 17 Bước 3: Gán nhãn có định
PTIT PTIT
127 L*(xi) = Min{L(x6), L(x3), L(x5)}
= Min{ 17, 23, 12} = 12- ứng với đỉnh x5. Gán xp ≡ x5 → B4 Bước 4: Đồ thị còn có nhãn tạm thời → B2
Vòng lặp 7:
Bước 2: Г(xp) = Г(x5) = {x6}, các đỉnh x6 được thay nhãn tạm thời như sau:
L(x6) = Min{L(x6); L(xp)+cp6} = Min{17; 12 + 10} = 17 Bước 3: Gán nhãn có định
L*(xi) = Min{L(x6), L(x3)}
= Min{ 17, 23} = 17- ứng với đỉnh x6. Gán xp ≡ x6 → B4 Bước 4: Đồ thị còn có nhãn tạm thời → B2
Vòng lặp 8:
Bước 2: Г(xp) = Г(x6) = {x3}, các đỉnh x3 được thay nhãn tạm thời như sau:
L(x3) = Min{L(x3); L(xp)+cp3} = Min{23; 17 + 20} = 23 Bước 3: Gán nhãn có định
L*(xi) = Min{L(x3)}
= Min{ 23} = 23- ứng với đỉnh x3. Gán xp ≡ x6 → B4 Bước 4: Đồ thị không còn nhãn tạm thời. Stop.
Chú ý: - Để tìm lộ trình đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại ta bắt đầu từ đỉnh gốc lần ngược lại liên tiếp theo quan hệ sau:
L*(xj) - cij = L*(xi) (4.3) trong đó xj là đỉnh nằm liền kề trước đỉnh xi trên đường đi ngắn nhất từ đỉnh xs đến đỉnh xj.
- Nếu đường đi ngắn nhất từ đỉnh xs đến đỉnh xt là duy nhất thì các cạnh hoặc cung (i, j) của đường đi ngắn nhất này tạo nên một cây có gốc là xs và ngọn là xt.Nếu đường đi này không duy nhất thì có nhiều cây tương ứng.
- Thuật toán Dijkstra chỉ áp dụng được khi cij ≥ 0. Trong trường hợp tổng quát, cij có thể âm, khi đó có thuật toán giải riêng.
4.3 Mạng liên thông
4.3.1 Nội dung và ý nghĩa của bài toán
a. Nội dung bài toán: Cho đồ thị vô hướng đối xứng GX.A, với tập X = {x1, x2,.., xn}; tập A
= {a1, a2,..., am}, mỗi cạnh của đồ thị gán một số không âm, gọi là độ dài của cạnh. Hãy tìm một cây bao trùm có tổng độ dài các cạnh là nhỏ nhất?
Theo định nghĩa cây là một đồ thị liên thông và không chứa chu trình. Cây của một đồ thị liên thông n đỉnh gồm n-1 cạnh không chứa chu trình.
b. Ý nghĩa của bài toán:
Nếu coi các đỉnh của đồ thị là các điểm cần đặt máy điện thoại cố định thuê bao thì nên thiết kế mạng đường dây theo những cạnh nào để tổng chiều dài đặt dây là nhỏ nhất tính từ tổng đài nội hạt đến các thuê bao. Hoặc phải thiết kế hệ thống cáp truyền thông như thế nào để cung cấp thông tin đến các địa phương trong vùng từ một trung tâm viễn thông sao cho tiết kiệm cáp nhất. Nếu xem các đỉnh của đồ thị là những thành phố và các trung tâm huyện lỵ, muốn xây dựng mạng lưới giao thông nối liền tất cả các điểm đó lại sao cho tổng kinh phí xây dựng là nhỏ nhất.
4.3.2 Thuật toán Prim
Ta có thể tìm cây bao trùm của đồ thị sao cho tổng độ dài các cạnh thuộc cây là nhỏ nhất theo thuật toán đơn giản sau đây do Prim đề xuất. Đầu tiên ta chọn một cạnh ngắn nhất trong đồ thị làm
PTIT PTIT