CHƯƠNG 6
GV: TRẦN QUỐC VIỆT
1
Giới thiệu 2 ứng dụng:
Bài toán luồng cực đại (Max-flow
problem)
Bài toán ghép cặp (Matching problem)
2
3
Mạng (network) là một đồ thị có hướng có trọng số G = (V,E) trên đó ta chọn một đỉnh gọi là đỉnh phát (source vertex) và 1 đỉnh gọi là đỉnh thu (sink vertex).
Ví dụ
3
5 5
sink
source
2 2 6
8 4 4
4
3
Một mạng G = (V,E) với đỉnh phát là a, đỉnh thu là z, c(e) N là trọng số của cung e. Với mỗi đỉnh x, ta đặt: = {e E | e tới trong x} In(x) Out(x) = {e E | e tới ngoài x}
b 3 d
5 5 In(c)={ac, bc}
z
a
2 2 6
Out(c)={cd, ce}
8 4 4
5
c 3 e
Một hàm tải (flow function) trên G được định nghĩa bởi ánh xạ:
φ: E N
thỏa các điều kiện
(i) 0 ≤ φ(e) ≤ c(e), e E (Giới hạn của luồng)
(i) φ(e) = 0, e In(a) Out(z) (Giá trị luồng)
(e)
(e)
za,
\Vx , (iii) (Cân bằngluồng)
e
In(x)
e
Out(x)
6
b d 3,1 c[u,v]/f[u,v]
5,4 5,4 2,1
z
a
2,1 6,2
4,1
8,2
4,1
4,0 3,1 (2,0) c e
3,0 1,0
g
7
(fa) = 0 (zg) = 0 (ab) = 4 (ac) = 1 (fc) = 0 (gc) = 0 (bd) = 1 (be) = 1 (bc) = 2 (cd) = 2 (ce)=1 (dz) = 4 (ez) = 1 (ed) = 1
f
Một phép cắt (cut) xác định bởi 1 tập hợp con P của V,
P ký hiệu (P, ) là tập hợp:
}
P (P, ) = {
x|xy
vàP
Py
P\VP
Trong đó
)P(P,
gọi là 1 phép cắt a-z nếu aP và
Phép cắt P
z
Trọng số (capacity) của một phép cắt được định
nghĩa là:
c(P,
)P
c(e)
8
e
)P(P,
b 3 d
5 5
z
a
2 2 6
P={a,b, c}
8 4 4
P={d, e,z}
(P,P)={bd,be,cd,ce}
c(P,P)=16
9
c 3 e
Gọi là một hàm tải trên mạng G và P V\{a,z}
thì:
(e)
(e)
e
)P(P,
P),P(e
d b
P
Ví dụ: 3,1
5,4 5,4 2,1
z
a
2,1 6,2
4,1
8,2
4,1
4,0 3,1 (2,0) c e
g
3,0 1,0
10
f
lượng tải vào z, nghĩa là:
(e)
(e)
Với mọi hàm tải φ trên mạng G, lượng tải khỏi a bằng
Out(a)
e
e
In(z)
d b 3,1
5,4 5,4 2,1
z
a
2,1 6,2
4,1
8,2
4,1
4,0 (2,0) 3,1 c e
g
1,0 3,0
11
f
Đặt P = V \ {a,z}, khi đó:
(e)
(e)
(e)
(e)
Out(a)
e
e
In(z)
P),P(e
e
)P(P,
12
Với mọi hàm tải φ và với mọi phép cắt a-z trong mạng
G, ta có:
|
|
c(P,
)P
13
Thêm vào G một đỉnh a0 và cạnh a0a (hướng từ a0 đến a), c(a0a)=. Ta được mạng G’. Trong G’ đặt ’(a0a) = | | và ’(e) = (e), eE Ta có:
|
| |' |
(e)
' P)},
P(e
{a
' (e) }) {a
e
P(P,
0
0
(e)
c(e)
c(P,
)P
e
)P(P,
e
)P(P,
14
Với mọi hàm tải φ và mọi phép cắt a-z trong mạng G.
c(P,
)P
|φ|= nếu và chỉ nếu thỏa 2 điều kiện:
e
,P(
P),
(e)
0
e
(P,
),P
(e)
c(e)
(i) (ii)
|
|
c(P,
)P
Khi thì là hàm tải có tải trọng lớn nhất và là phép cắt a-z có trọng số nhỏ nhất
(P,
)P
15
với một phép căt a-z
Cho một mạng G, đỉnh phát a và đỉnh thu z, (
)PP,
Một chuyền a-z K là một đường đi vô hướng
nối a với z
Ký hiệu s(e) = c(e)-(e) gọi là độ lệch tải của e Ta định nghĩa:
: e K
)e(K
: e K và có hướng từ a đến z
-
16
: e K và e có hướng từ z đến a
Input: Mạng G, đỉnh phát a và đỉnh thu z Output: Tập P của phép cắt a-z tối thiểu
(P,
)P
Bắt đầu bằng 1 hàm tải bất kỳ trên G 1. Đánh dấu mọi đỉnh đều chưa xét, gán nhãn cho a là (-,(a)) với (a)=. Đặt p0=a. 2. Xét p0.
a. Cạnh e=p0q với q chưa có nhãn và s(e)>0 thì gán nhãn
cho q là (p0
+, min((p0), s(e)))
b. Cạnh e=qp0 với q chưa có nhãn và (e)>0 thì gán nhãn
cho q là (p0
-, min((p0), (e)))
3. Nếu đỉnh z đã được gán nhãn 4, ngược lại 5. 4. Xác định một dây chuyền (vô hướng) từ a đến z dựa vào thành phần thứ 1 của nhãn. Cập nhật lại như sau: (e) = (e) + (z) K(e). Về bước 1.
5. Tìm 1 đỉnh p đã có nhãn nhưng chưa xét. Nếu tồn
tại p, đặt p0 = p, bước 2. Ngược lại dừng.
Sau khi thuật toán kết thúc. P là tập hợp các
đỉnh đã có nhãn và đã xét.
19
G với hàm tải ban đầu:
b 6,5 d
6,6 5,5 3,0
z
a
3,1
6,1 5,2
20
c e 1,1
Lặp lần 1:
Gán nhãn cho đỉnh a là (-,(a)), với (a)=∞ Đặt p0=a
b 6,5 d
6,6 5,5 3,0
z
3,1
(-,∞) a
6,1 5,2
21
c e 1,1
Xét các đỉnh kề với p0: Cạnh e1=(a,b) có s(e1)=0 nên không xét Cạnh e2=(a,c) có s(e2)=3>0 nên gán nhãn cho đỉnh c là: (a+,min{(p0),s(e2)}) =(a+,3)
b 6,5 d
6,6 5,5 3,0
z
3,1
(-,∞) a
6,1 5,2
Đỉnh z chưa được gán nhãn, đỉnh c đã gán nhãn nhưng chưa xét, đặt p0=c
22
e 1,1 c (a+,3)
Xét các đỉnh kề với p0: Cạnh e3=(c,e) có s(e3)=0 nên không xét Cạnh e4=(c,d) có s(e4)=2>0 nên gán nhãn cho đỉnh d là: (c+,min{(p0),s(e4)}) =(c+,2)
(c+,2) b 6,5 d
6,6 5,5 3,0
z
3,1
(-,∞) a
6,1 5,2
Đỉnh z chưa được gán nhãn, đỉnh d đã gán nhãn nhưng chưa xét, đặt p0=d
23
e 1,1 c (a+,3)
p0=d: Cạnh e5=(d,z) có s(e5)=0 nên không xét Cạnh e6=(b,d) có (e6)=5>0 nên gán nhãn cho đỉnh b là: (d-,min{(p0), (e6)}) =(d-,2)
b 6,5 d (d-,2)
(c+,2) P0 6,6 5,5 3,0
z
3,1
(-,∞) a
6,1 5,2
Đỉnh z chưa được gán nhãn, đỉnh b đã gán nhãn nhưng chưa xét, đặt p0=b
24
e 1,1 c (a+,3)
p0=b: Cạnh e7=(b,e) có s(e7)=3>0 nên gán nhãn cho đỉnh e là: (b+,min{(p0), s(e7)}) =(b+,2)
(c+,2) b 6,5 d (d-,2) p0
6,6 5,5 3,0
z
3,1
(-,∞) a
6,1 5,2
Đỉnh z chưa được gán nhãn, đỉnh e đã gán nhãn nhưng chưa xét, đặt p0=e
25
(b+,2) e 1,1 c (a+,3)
p0=e: Cạnh e8=(e,z) có s(e8)=5>0 nên gán nhãn cho đỉnh z là: (e+,min{(p0), s(e8)}) =(e+,2)
(c+,2) b 6,5 d (d-,2)
6,6 5,5 3,0
3,1
z (e+,2)
(-,∞) a
6,1 5,2
(b+,2)
Đỉnh z đã được gán nhãn, tìm chuyền a-z K: acdbez
26
e 1,1 c (a+,3)
Cập nhật lại hàm tải: = +(z)K
: e K
)e(K
: e K và có hướng từ a đến z
-
: e K và e có hướng từ z đến a
6,3 b d
6,6 5,5 3,2
z
a
3,3
(e+,2)
6,3 5,4
27
c e (1,1)
Lặp lần 2:
Gán nhãn cho đỉnh a là (-,(a)), với (a)=∞ Đặt p0=a
6,3 b d
6,6 5,5 3,2
z
3,3
a (-,∞)
p0
6,3 5,4
28
c e (1,1)
Lặp lần 2:
Gán nhãn cho đỉnh a là (-,(a)), với (a)=∞ Đặt p0=a
6,3 b d
6,6 5,5 3,2
z
3,3
a (-,∞)
p0
6,3 5,4
Đỉnh z chưa gán nhãn, đỉnh c đã gán nhãn nhưng chưa
được xét, đặt p0=c
29
c e (1,1) (a+,1)
b 6,5 d
6,6 5,5 3,0
z
a
3,1
6,1 5,2
c 1,1 e b 6,5 d
6,6 5,5 3,0
z
a
3,1
6,1 5,2
30
c 1,1 e
Khi kết thúc thuật toán Ford-Fulkerson thì φ là 1 hàm
tải tối đại và
là 1 phép cắt a-z tối tiểu.
)P(P,
31
Trong một mạng G, tải trọng của 1 hàm tải tối đại
bằng trọng số của một phép cắt a-z tối tiểu.
32
6,5
B D
6,6 5,5
3,0 3,1
A Z
5,2 6,1
33
C E 1,1
6,3
B D
6,6 5,5
3,2 3,3
A Z
5,4 6,3
34
C E 1,1
7
B E
4 6 5 4
A C Z
4
3
5 7 12
35
D F 9
7,5
B E
4,4 6,5 5 4,1
A C Z
4,4
3,3
5,2 7,7 12,12
36
D F 9,9
Cho một đồ thị lưỡng phân G = (X,Y,E) với X là tập hợp các đỉnh trái và Y là tập hợp các đỉnh phải của G. Một bộ ghép (matching) của G là một tập hợp các cạnh của G đôi một không có đỉnh chung. Bài toán cặp ghép (matching problem) của G là tìm một bộ ghép tối đại (có số lượng các cạnh là lớn nhất) của G.
37
Xét 1 bộ ghép M của G. Khi đó:
◦ Các đỉnh trong M được gọi là các đỉnh đã được
ghép.
◦ Một đường pha (alternating path) là một đường
trong G bắt đầu bằng 1 đỉnh chưa ghép thuộc X và các cạnh lần lượt là thuộc rồi không thuộc M.
◦ Một đường mở (augmenting path) là 1 đường pha
kết thúc bằng một đỉnh chưa ghép thuộc Y.
38
◦ Từ 1 đỉnh u chưa ghép thuộc X, ta có thể xây
dựng 1 cây pha (alternating tree) gốc u gồm tất cả các đường pha bắt đầu từ u.
◦ Một cây pha chứa ít nhất 1 đường mở được gọi
là 1 cây mở (augmenting tree). Ngược lại sẽ được gọi là một cây đóng (Hungarian tree), gốc u của cây đóng này gọi là đỉnh đóng (Hungarian acorn).
39
1. Đặt mọi đỉnh thuộc X là chưa kiểm tra. Đặt M=. 2. Nếu mọi đỉnh thuộc X chưa ghép đều đã kiểm tra thì dừng. Nếu không, chọn một đỉnh uX chưa ghép và chưa kiểm tra để xây dựng 1 cây pha gốc u.
3. Nếu cây pha này là cây mở thì bước 4. Nếu không, đánh dấu u là đã kiểm tra bước 2. 4. Mở rộng M bằng cây mở như sau: Trên đường mở, loại bỏ các cạnh trong M và thêm vào các cạnh ngoài M. Đánh dấu mọi đỉnh thuộc X là chưa kiểm tra. Quay về bước 2.
40
Bộ ghép nhận được sau khi áp dụng thuật
toán Hungarian vào đồ thị lưỡng phân G là tối đại.
41
Một bộ ghép M của đồ thị lưỡng phân
G=(X,Y,E) được gọi là X-đầy đủ (X-complete matching) nếu M chứa mọi đỉnh của X. Với AX, đặt (A) là tập hợp các đỉnh yY kề với một đỉnh xA. Khi này, G có 1 bộ ghép X-đầy đủ nếu và chỉ nếu AX, |(A)||A|.
42
A a
B b
C c
D d
E e
F f
G g
43
H h
A a
B b
C c
D d
E e
F f
G g
44
H h
