Bài giảng Lý thuyết đồ thị

LÝ THUYẾT ĐỒ THỊ
1
THÔNG TIN VỀ GIÁO VIÊN
• Thời gian, địa điểm làm việc: Bộ môn Khoa học máy tính -
Khoa Công nghệ thông tin - Học viện Kỹ thuật Quân sự.
• Địa chỉ liên hệ: Bộ môn Khoa học máy tính - Khoa Công
nghệ thông tin - Học viện Kỹ thuật Quân sự.
• Điện thoại, email: ngohuuphuc76@gmail.com
• Các hướng nghiên cứu chính: Xử lý ảnh, Trí tuệ nhân tạo, 
Nhận dạng mẫu, Tính toán mềm, Xử lý tiếng nói.
2
TT Họ tên giáo 
viên
Học 
hàm
Học vị Đơn vị công tác (Bộ môn)
1 Ngô Hữu Phúc GVC Tiến sỹ Bộ môn Khoa học máy tính
2 Vi Bảo Ngọc TG Thạc sỹ Bộ môn Khoa học máy tính
THÔNG TIN CHUNG VỀ MÔN 
HỌC
• Tên học phần: Lý thuyết đồ thị
• Mã học phần: 
• Số tín chỉ: 3
• Học phần (bắt buộc hay lựa chọn): tự chọn
• Các học phần tiên quyết: Đại số tuyến tính, Giải tích đại cương, Tin 
học cơ bản
• Các yêu cầu đối với học phần (nếu có):
• Giờ tín chỉ đối với các hoạt động: 
– Nghe giảng lý thuyết: 30 tiết
– Làm bài tập trên lớp: 15 tiết
– Thảo luận: 6 tiết
– Thực hành, thực tập (ở PTN, nhà máy, thực tập...): 9 tiết
– Hoạt động theo nhóm:
– Tự học: 90 tiết
• Khoa/Bộ môn phụ trách học phần, địa chỉ: Bộ môn Khoa học máy
tính - Khoa Công nghệ thông tin - Học viện Kỹ thuật Quân sự.
3
4CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 1 KHÁI NIỆM ĐỒ THỊ
• Đồ 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.
• Phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối
hai đỉnh nào đó của đồ thị.
Định nghĩa 1 (Đơn đồ thị).
 Đơn đồ thị vô hướng G = (V,E) bao gồm V là tập các đỉnh khác
rỗng, và E là tập các cặp không có thứ tự gồm hai phần tử khác
nhau của V gọi là các cạnh.
Hình 1. Sơ đồ mạng máy tính đơn kênh thoại. 
5Định nghĩa 2 (Đa đồ thị).
 Đa đồ thị vô hướng G= (V, E) bao gồm V là tập các đỉnh khác rỗng, và
E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là
các cạnh. Hai cạnh e1 và e2 được gọi là cạnh lặp (bội hay song song) nếu
chúng cùng tương ứng với một cặp đỉnh.
 Mỗi đơn đồ thị là đa đồ thị, nhưng không phải đa đồ thị nào cũng là đơn
đồ thị, vì trong đa đồ thị có thể có hai (hoặc nhiều hơn) cạnh nối một cặp
đỉnh nào đó.
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN
BÀI 1 KHÁI NIỆM ĐỒ THỊ 
Hình 2. Sơ đồ mạng máy tính đa kênh thoại. 
6Định nghĩa 3 (Giả đồ thị).
 Giả đồ thị vô hướng G = (V, E) bao gồm V là tập các đỉnh khác rỗng
và E là tập các cặp không có thứ tự gồm hai phần tử (không nhất thiết
phải khác nhau) của V gọi là cạnh.
Với v Є V, nếu (v,v) Є E thì ta nói có một khuyên tại đỉnh v.
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 1 KHÁI NIỆM ĐỒ THỊ
Nhận xét: giả đồ thị là loại đồ thị vô hướng tổng quát nhất vì nó có thể
chứa các khuyên và các cạnh lặp. Đa đồ thị là loại đồ thị vô hướng có
thể chứa cạnh bội nhưng không thể có các khuyên, còn đơn đồ thị là loại
đồ thị vô hướng không chứa cạnh bội hoặc các khuyên.
7CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN
BÀI 1 KHÁI NIỆM ĐỒ THỊ 
Định nghĩa 4 (Đơn đồ thị có hướng). 
 Đơn đồ thị có hướng G = (V, E) bao gồm V là tập các đỉnh
khác rỗng và E là tập các cặp có thứ tự gồm hai phần tử
khác nhau của V gọi là các cung.
8CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 1 KHÁI NIỆM ĐỒ THỊ
Định nghĩa 5 (Đa đồ thị có hướng). 
 Đa đồ thị có hướng G = (V, E) bao gồm V là tập các đỉnh
khác rỗng và E là tập các cặp có thứ tự gồm hai phần tử
khác nhau của V gọi là các cung. Hai cung e1, e2 tương ứng
với cùng một cặp đỉnh được gọi là cung lặp.
9CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 2 BẬC CỦA ĐỈNH
Định nghĩa 1: 
 Hai đỉnh u và v trong đồ thị (vô hướng) G=(V,E) được gọi
là liền kề nếu (u,v) Є E. Nếu e = (u,v) thì e gọi là cạnh liên
thuộc với các đỉnh u và v. Cạnh e cũng được gọi là cạnh nối
các đỉnh u và v. Các đỉnh u và v gọi là các điểm đầu mút của
cạnh e.
Định nghĩa 2:
 Bậc của đỉnh v trong đồ thị G=(V,E), ký hiệu deg(v), là số
các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được
tính hai lần cho bậc của nó.
 Đỉnh v gọi là đỉnh treo nếu deg(v)=1 và gọi là đỉnh cô lập
nếu deg(v)=0.
10
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 2 BẬC CỦA ĐỈNH
Xét ví dụ:
Ta có: deg(v1)=7, deg(v2)=5, deg(v3)=3, deg(v4)=0, 
deg(v5)=4, deg(v6)=1, deg(v7)=2.
Đỉnh v4 là đỉnh cô lập và đỉnh v6 là đỉnh treo.
11
Định lý 1. 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ố cạnh.
Chứng minh. Rõ ràng mỗi cạnh e = (u, v) được
tính một lần trong deg(u) và một lần trong deg(v).
Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng
hai lần số cạnh.
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.
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 2 BẬC CỦA ĐỈNH
12
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 2 BẬC CỦA ĐỈNH
Chứng minh. Thực vậy, gọi O và U tương ứng là 
tập đỉnh bậc lẻ và tập đỉnh bậc chẵn của đồ thị. 
Ta có:
Do deg(v) là chẵn với v là đỉnh trong U nên tổng
thứ nhất ở trên là số chẵn.
===> tổng thứ hai (chính là tổng bậc của các đỉnh
bậc lẻ) cũng phải là số chẵn,
Do tất cả các số hạng của nó là số lẻ, nên tổng này
phải gồm một số chẵn các số hạng. Vì vậy, số đỉnh
bậc lẻ phải là số chẵn.

OvUv
vvm )deg()deg(2
13
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 2 BẬC CỦA ĐỈNH
Định nghĩa 3.
 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. Đỉnh u(v) sẽ được gị là đỉnh đầu
(cuối) của cung (u,v).
Định nghĩa 4.
 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))
14
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 2 BẬC CỦA ĐỈNH
Định lý 2.
Cho G =(V, E) là một đồ thị có hướng. Khi đó:

VvVv
vvm )(deg)(deg
Chứng minh: Kết quả có ngay là vì mỗi cung được tính một
lần cho đỉnh đầu và một lần cho đỉnh cuối.
Xét ví du: Ta có:
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.
15
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 3 ĐƯỜNG ĐI. CHU TRÌNH. ĐỒ THỊ LIÊN THÔNG
Định nghĩa 1 (Đường đi).
Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số
nguyên dương, trên đồ thị vô hướng G = (V, E) là dãy x0, x1,,
xn-1, xn; trong đó u = x0, v = xn, (xi , xi+1) 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.
16
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 3 ĐƯỜNG ĐI. CHU TRÌNH. ĐỒ THỊ LIÊN THÔNG
Ví dụ 1. 
Trên đồ thị vô hướng cho trong hình:
 a, d, c, f, e là đường đi đơn độ dài 4.
 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.
17
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 3 ĐƯỜNG ĐI. CHU TRÌNH. ĐỒ THỊ LIÊN THÔNG
Định nghĩa 2. (Liên thông) 
Đồ 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 là liên thông, còn đồ thị H là không liên thông. 
Hình 2. Đồ thị G và H 
18
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 3 ĐƯỜNG ĐI. CHU TRÌNH. ĐỒ THỊ LIÊN THÔNG
Định nghĩa 3.
Ta gọi đồ thị con của đồ thị G = (V, E) là đồ thị H = (W, F),
trong đó WV và FE.
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 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ị.
Ví dụ 2. Đồ thị H trong hình 2 gồm 3 thành phần liên thông
H1, H2, H3.
19
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 3 ĐƯỜNG ĐI. CHU TRÌNH. ĐỒ THỊ LIÊN THÔNG
Định nghĩa 4.
 Đỉnh v được gọi là đỉnh rẽ nhánh nếu việc loại bỏ v cùng với
các cạnh liên thuộc với nó khỏi đồ thị làm tăng số thành phần
liên thông của đồ thị.
 Cạnh e được gọi là cầu nếu việc loại bỏ nó khỏi đồ thị làm
tăng số thành phần liên thông của đồ thị.
Ví dụ 3. Trong đồ thị G ở hình 2, đỉnh c, d và e là đỉnh rẽ
nhánh, còn các cạnh (c,d) và (c,e) là cầu.
20
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 3 ĐƯỜNG ĐI. CHU TRÌNH. ĐỒ THỊ LIÊN THÔNG
Định nghĩa 5. 
 Đồ thị có hướng G = (V, A) đượ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ó.
Định nghĩa 6.
 Đồ thị có hướng G = (V, A) đượ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.
Hình 3. Đồ thị liên thông mạnh G và đồ thị liên thông yếu H 
21
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 4 ĐƠN ĐỒ THỊ ĐẶC BIỆT
Đồ thị đầy đủ: Đồ thị đầy đủ n đỉnh, ký hiệu là Kn, là đơn đồ
thị mà hai đỉnh phân biệt bất kỳ của nó luôn liền kề.
Như vậy, Kn có n(n −1)/2 cạnh và 
mỗi đỉnh của Kn có bậc là n−1.
Xét ví dụ:
22
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 4 ĐƠN ĐỒ THỊ ĐẶC BIỆT
Đồ thị vòng: Đơn đồ thị n đỉnh v1, v2, ..., vn (n≥3) và n cạnh 
(v1,v2), (v2,v3), ..., (vn-1,vn), (vn,v1) được gọi là đồ thị vòng, ký 
hiệu là Cn. Như vậy, mỗi đỉnh của Cn có bậc là 2.
Xét ví dụ:
23
Đồ thị bánh xe: Từ đồ thị vòng Cn, thêm vào đỉnh vn+1 và 
các cạnh (vn+1,v1), (vn+1,v2), ..., (vn+1,vn), ta nhận được đơn 
đồ thị gọi là đồ thị bánh xe, ký hiệu là Wn. 
Như vậy, Wn có n+1 đỉnh, 2n cạnh, 
một đỉnh bậc n và n đỉnh bậc 3.
Xét ví dụ:
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 4 ĐƠN ĐỒ THỊ ĐẶC BIỆT
24
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 4 ĐƠN ĐỒ THỊ ĐẶC BIỆT
Đồ thị lập phương: Đơn đồ thị 2n đỉnh, tương ứng với 2n xâu 
nhị phân độ dài n và hai đỉnh kề nhau khi và chỉ khi 2 xâu nhị 
phân tương ứng với hai đỉnh này chỉ khác nhau đúng một bit 
được gọi là đồ thị lập phương, ký hiệu là Qn. 
• Như vậy, mỗi đỉnh của Qn có bậc là n 
số cạnh của Qn là n.2
n-1
Đồ thị lập phương Q1, Q2, Q3
25
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 4 ĐƠN ĐỒ THỊ ĐẶC BIỆT
Đồ thị phân đôi (đồ thị hai phe): Đơn đồ thị G=(V,E) sao cho
V=V1UV2, V1∩V2=∅, V1≠∅, V2≠∅ và mỗi cạnh của G được nối
một đỉnh trong V1 và một đỉnh trong V2 được gọi là đồ thị phân
đôi.
 Nếu đồ thị phân đôi G=(V1UV2,E) sao cho với mọi v1ЄV1,
v2 Є V2, (v1,v2) Є E thì G được gọi là đồ thị phân đôi đầy đủ.
 Nếu |V1|=m, |V2|=n thì đồ thị G được ký hiệu là Km,n.
 Như vậy, Km,n có m.n cạnh, các đỉnh của V1 có bậc n và các
đỉnh của V2 có bậc m.
26
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 4 ĐƠN ĐỒ THỊ ĐẶC BIỆT
Ứng dụng của các đồ thị đặc biệt:
+ Các mạng cục bộ (LAN):
Đồ thị phân đôi đầy 
đủ K1,n
Đồ thị vòng Cn Đồ thị bánh xe Wn
27
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
1. Ma trận kề, ma trận trọng số
Xét đơn đồ thị G=(V,E)
Ma trận kề:
Ma trận A={ai,j : i,j=1, 2,. . . ,n} với ai,j=0, nếu (i,j) E và ai,j=1, 
nếu (i,j)ЄE, i, j=1, 2,. . .,n gọi là ma trận kề của đồ thị G. 
Ví dụ:
H1. Đồ thị vô hướng G
28
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
1. Ma trận kề, ma trận trọng số
Xét đơn đồ thị có hướng G=(V,E)
Ma trận kề:
Ma trận A={ai,j : i,j=1, 2,. . . ,n} với ai,j=0, nếu (i,j) E và ai,j=1,
nếu (i,j)ЄE, i, j=1, 2,. . .,n gọi là ma trận kề của đồ thị G.
Ví dụ:
Đồ thị có hướng G1
29
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
* Tính chất của ma trận kề của đồ thị vô hướng:
- Tính đối xứng: a[i,j]=a[j,i], i,j=1,2,. . .,n.
- Tổng các phần từ trên dòng i (cột j) bằng bậc của đỉnh i 
(đỉnh j).
* Tính chất của ma trận kề của đồ thị có hướng:
- Không có tính đối xứng
- Tổng các phần từ trên dòng i bằng bán bậc ra của đỉnh i
(deg+(i)) và tổng các phần từ trên cột j bằng bán bậc vào
của đỉnh j (deg(-j)).
30
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
1. Ma trận kề, ma trận trọng số
Xét ví dụ 2:
31
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
Ma trận trọng số:
Đồ thị có trọng số là đồ thị mà mỗi cạnh (i,j) có một giá trị c(i,j)
gọi là trọng số của cạnh.
Để biểu diễn đồ thị ta sử dụng ma trận trọng số C= {c[i,j],
i,j=1, 2,. . .,n}
với c[i,j]= c(i,j) nếu (i,j) Є E và c[i,j]= nếu (i,j) E
trong đó số  có thể được đặt bằng một trong các giá trị sau: 
0, + , - .
32
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
Ma trận trọng số:
Ví du:
1
33
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
Ưu điểm lớn nhất của phương pháp biểu diễn đồ thị bằng
ma trận kề (hoặc ma trận trọng số) là để trả lời câu hỏi: Hai
đỉnh u,v có kề nhau trên đồ thị hay không, chúng ta chỉ
phải thực hiện một phép so sánh.
Nhược điểm lớn nhất của phương pháp này là: không phụ
thuộc vào số cạnh của đồ thị, ta luôn phải sử dụng n2 đơn
vị bộ nhớ để lưu trữ ma trận kề của nó.
34
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
2. Ma trận liên thuộc đỉnh-cạnh:
Xét G=(V, E) là đơn đồ thị có hướng. Ma trận liên thuộc đỉnh-
cạnh có dạng: 
35
3. Danh sách cạnh (cung)
+ Trong trường hợp đồ thị thưa (đồ thị có số cạnh m thoả
mãn bất đẳng thức: m<6n) biểu diễn đồ thị dưới dạng d/s
cạnh.
Lưu trữ danh sách tất cả các cạnh (cung) của đồ thị.
+ Một cạnh (cung) e=(x,y) của đồ thị tương ứng với hai biến
Dau[e], Cuoi[e].
+ Để lưu trữ đồ thị ta cần sử dụng 2m đơn vị bộ nhớ.
Nhược điểm: để tìm các đỉnh kề với một đỉnh cho trước
phải làm m phép so sánh (khi duyệt qua danh sách tất cả các
cạnh của đồ thị).
+ Trong trường hợp đồ thị có trọng số ta cần thêm m đơn vị
bộ nhớ để lưu trữ trọng số của các cạnh.
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
36
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
37
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
4. Danh sách kề
Với mỗi đỉnh v, ta lưu trữ danh sách các đỉnh kề với v:
Ke(v)={u Є V: (v,u) Є E}
38
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN 
BÀI 5 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
4. Danh sách kề
Đồ thị có hướng G1
39
1. Duyệt đồ thị theo chiều sâu (DFS-Depth
First Search)
* Ý tưởng:
- Từ đỉnh v1 nào đó chưa thăm, thăm v1, rồi
tìm đỉnh v2 (chưa thăm) kề với v1, thăm v2
Thuật toán lặp lại việc thăm cho tới khi tất cả
các đỉnh đều được thăm.
- Nếu tại một đỉnh vi nào đó, không còn đỉnh
nào kề với vi là chưa thăm thì quay trở lại tiếp
tục tìm đỉnh kề chưa thăm khác của vi-1.
CHƯƠNG II CÁC THUẬT TOÁN TÌM KIẾM TRÊN 
ĐỒ THỊ 
40
1.Duyệt đồ thị theo chiều sâu (DFS-Depth
First Search)
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 Є Ke(v) do
If Chuaxet[u] then DFS(u);
End; (*dinh v da duyet xong*)
Khi đó, tìm kiếm theo chiều sâu trên đồ thị được thực hiện
nhờ thuật toán sau:
Begin
(*Khoi tao tat ca cac dinh cua do thi*)
for v Є V do Chuaxet[v]:=true;
for v Є V do
If Chuaxet[v] then DFS(v);
End.
CHƯƠNG II CÁC THUẬT TOÁN TÌM KIẾM TRÊN 
ĐỒ THỊ 
41
1.Duyệt đồ thị theo chiều sâu (DFS-Depth
First Search)
Ví dụ 1. Xét đồ thị cho trong hình gồm 13 đỉnh, các đỉnh được đánh số từ 1 đến
13 như sau:
CHƯƠNG II CÁC THUẬT TOÁN TÌM KIẾM TRÊN 
ĐỒ THỊ 
42
2. Duyệt đồ thị theo chiều rộng (BFS-
Breadth First Search)
* Ý tưởng:
-Từ đỉnh v nào đó chưa thăm, thăm v, ... hất:
Bài toán đặt ra là trong số tất cả các cây khung
của đồ thị G, hãy tìm cây khung có độ dài nhỏ
nhất.
Cây khung như vậy được gọi là cây khung nhỏ
nhất của đồ thị.
Bài toán được gọi là “bài toán tìm cây khung
nhỏ nhất”.
• Hai mô hình thực tế tiêu biểu:
* Bài toán xây dựng hệ thống đường sắt.
* Bài toán nối mạng máy tính.
CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 
72
3. Thuật toán Kruskal: Thuật toán sẽ xây dựng
tập cạnh ET của cây khung nhỏ nhất T=(VT,ET)
theo từng bước:
1. Bắt đầu từ đồ thị rỗng T có n đỉnh.
2. Sắp xếp các cạnh của G theo thứ tự không giảm
của trọng số.
3. Bắt đầu từ cạnh đầu tiên của dãy này, thêm dần
các cạnh của dãy đã được xếp vào T theo nguyên
tắc cạnh thêm vào không được tạo thành chu
trình trong T.
4. Lặp lại Bước 3 cho đến khi nào số cạnh trong T
bằng n−1, ta thu được cây khung nhỏ nhất cần
tìm.
CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 
73
3. Thuật toán Kruskal:
Xét thí dụ: Tìm cây khung nhỏ nhất cho bởi đồ thị:
CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 
74
4. Thuật toán Prim: còn được gọi là phương
pháp lân cận gần nhất.
1. VT:={v*}, trong đó v* là đỉnh tuỳ ý của đồ thị G. ET:=∅.
2. Với mỗi đỉnh vj∉VT, tìm đỉnh wj VT sao cho
m(wj,vj) = min m(xi, vj)=:βj ; xi VT và gán cho đỉnh vj nhãn
[wj, βj]. Nếu không tìm đuợc wj (tức là khi vj không kề với
bất cứ đỉnh nào trong VT) thì gán cho vj nhãn [0, ∞].
3. Chọn đỉnh vj* sao cho βj* = min βj ; vj∉VT
VT := VT  {vj*}, ET := ET  {(wj*, vj*)}.
Nếu |VT| = n thì thuật toán dừng và (VT, ET) là cây khung
nhỏ nhất.
Nếu |VT| < n thì chuyển sang Bước 4.
4. Đối với tất cả các đỉnh vj∉VT mà kề với vj*, ta thay đổi
nhãn của chúng như sau:
Nếu βj > m(vj*, vj) thì đặt βj:=m(vj*, vj) và nhãn của vj là [vj*,
βj]. Ngược lại, ta giữ nguyên nhãn của vj. Sau đó quay
lại Bước 3.
75
4. Thuật toán Prim:
Xét thí dụ: Tìm cây khung nhỏ nhất cho bởi đồ thị:
CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 
76
4. Thuật toán Prim:
Bảng nhãn của các đỉnh:
CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 
Vậy độ dài cây khung nhỏ nhất là:
15 + 12 + 11 + 13 + 14 + 17 + 21 = 103.
77
5. Cây có gốc:
Định nghĩa: Cây có hướng là đồ thị có hướng mà đồ
thị vô hướng nền của nó là một cây.
Cây có gốc là một cây có hướng, trong đó có một
đỉnh đặc biệt, gọi là gốc, từ gốc có đường đi đến
mọi đỉnh khác của cây.
Trong cây có gốc thì gốc r có bán bậc vào bằng 0,
còn tất cả các đỉnh khác đều có bậc vào bằng 1.
Một cây có gốc thường được vẽ với gốc r ở trên
cùng và cây phát triển từ trên xuống, gốc r gọi là
đỉnh mức 0. Các đỉnh kề với r được xếp ở phía
dưới và gọi là đỉnh mức 1. Đỉnh ngay dưới đỉnh
mức 1 là đỉnh mức 2, ...
CHƯƠNG V CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 
78
5. Cây có gốc:
Tổng quát, trong một cây có gốc thì v là đỉnh mức k
khi và chỉ khi đường đi từ r đến v có độ dài bằng k.
Mức lớn nhất của một đỉnh bất kỳ trong cây gọi là
chiều cao của cây.
CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 
79
5. Cây có gốc:
Định nghĩa: Cho cây T có gốc r=v0. Giả sử v0, v1, ..., vn-1, vn
là một đường đi trong T. Ta gọi:
− vi+1 là con của vi và vi là cha của vi+1.
− v0, v1, ..., vn-1 là các tổ tiên của vn và vn là dòng dõi của v0,
v1, ..., vn-1.
− Đỉnh treo vn là đỉnh không có con; đỉnh treo cũng gọi là lá
hay đỉnh ngoài; một đỉnh không phải lá là một đỉnh trong.
Định nghĩa: Một cây có gốc T được gọi là cây m-phân nếu
mỗi đỉnh của T có nhiều nhất là m con. Với m=2, ta có
một cây nhị phân.
Trong một cây nhị phân, mỗi con được chỉ rõ là con bên trái
hay con bên phải;
Cây có gốc T được gọi là một cây m-phân đầy đủ nếu mỗi
đỉnh trong của T đều có m con.
CHƯƠNG IV CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 
CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT
• Trong phần này, giới thiệu về giải thuật
tìm đường đi ngắn nhất giữa 2 đỉnh trên
đồ thị có trọng số.
• Nội dung gồm:
– 5.1. Giới thiệu về bài toán
– 5.2. Thuật toán gán nhãn.
– 5.3. Thuật toán Dijkstra
80
CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT
• 5.1. Giới thiệu về bài toán
– Xét đồ thị G = với V = n, E = m.
– Với mỗi cạnh u, v ∈ E, có một giá trị trọng số
A u, v .
– Đặt A u, v = ∞ nếu u, v ∉ E.
– Nếu dãy v0, v1,..., vk là một đường đi trên G thì
– ∑ A vi−1, vi
k
i=1
– được gọi là độ dài của đường đi.
– Bài toán: Tìm đường đi ngắn nhất từ đỉnh s đến
đỉnh t của đồ thị G.
81
CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT
• 5.2. Thuật toán gán nhãn (1/4)
– Thuật toán được mô tả như sau:
– Từ ma trận trọng số A[u,v], u,v∈V, tìm cận trên
d[v] của khoảng cách từ s đến tất cả các đỉnh
v∈V.
– Nếu thấy d[u] + A[u,v] < d[v] thì d[v] = d[u] + A[u,
v] (làm tốt lên giá trị của d[v])
– Quá trình sẽ kết thúc khi không thể làm “tốt lên”
được nữa.
– Khi đó d[v] sẽ cho ta giá trị ngắn nhất từ đỉnh s
đến đỉnh v.
– Giá trị d[v] được gọi là nhãn của đỉnh v.
82
CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT
• 5.2. Thuật toán gán nhãn (2/4)
– Ví dụ về thuật toán:
– Tìm đường đi ngắn nhất từ A đến Z trong đồ thị G
sau.
83
CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT
• 5.2. Thuật toán gán nhãn (3/4)
– Các bước thực hiện của giải thuật:
– Bước 1: Gán cho nhãn đỉnh A là 0, d A = 0;
– Bước 2: Chọn cạnh có độ dài nhỏ nhất xuất phát
từ A (cạnh AC), gán nhãn của đỉnh kề C với:
d C = d A + A A, C = 0 + 5 = 5
84
CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT
• 5.2. Thuật toán gán nhãn (3/4)
– Bước 3: Tiếp đó, trong số các cạnh đi từ một đỉnh
có nhãn là A hoặc C tới một đỉnh chưa được gán
nhãn, chọn cạnh sao cho: nhãn của đỉnh + với
trọng số cạnh tương ứng = nhỏ nhất gán cho
nhãn của đỉnh cuối của cạnh
• Như vậy, ta lần lượt gán được các nhãn như sau: 
• d[B] = 6 vì d[B] <d[C] + A[C,B] = 5 + 4; 
• d[E] = 8; 
• Tiếp tục làm như vậy cho tới khi đỉnh Z. Nhãn của
Z là độ dài đường đi ngắn nhất từ A đến Z. 
85
CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT
• 5.2. Thuật toán gán nhãn (4/4)
– Các bước được mô tả như trong bảng sau:
– Như vậy, độ dài đường đi ngắn nhất từ A đến Z là 18.
– Đường đi ngắn nhất từ A đến Z qua các đỉnh: A → C
→ D → G → Z
86
CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT
• 5.3. Thuật toán Dijkstra (1/6)
– Thuật toán này do E.Dijkstra, nhà toán học người Hà
Lan, đề xuất năm 1959.
– Thuật toán tìm đường đi ngắn nhất từ đỉnh s đến các
đỉnh còn lại được Dijkstra đề nghị áp dụng cho
trường hợp đồ thị có hướng với trọng số không âm.
– Thuật toán được thực hiện trên cơ sở gán tạm thời
cho các đỉnh.
– Nhãn của mỗi đỉnh cho biết cận trên của độ dài
đường đi ngắn nhất tới đỉnh đó.
– Các nhãn này sẽ được biến đổi (tính lại) nhờ một thủ
tục lặp, mà ở mỗi bước lặp một số đỉnh sẽ có nhãn
không thay đổi, nhãn đó chính là độ dài đường đi
ngắn nhất từ s đến đỉnh đó.
87
CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT
• 5.3. Thuật toán Dijkstra (2/6)
– Giả mã của giải thuật Dijkstra:
88
void Dijkstra(void)
/*Đầu vào G=(V, E) với n đỉnh có
ma trận trọng số A[u,v]≥ 0; s∈V
*/
/*Đầu ra là khoảng cách nhỏ nhất
từ s đến các đỉnh còn lại d[v]:
v∈V*/
/*Truoc[v]: ghi lại đỉnh trước v
trong đường đi ngắn nhất từ s đến
v*/
{
/*Bước 1: Khởi tạo nhãn tạm thời
cho các đỉnh*/
for ( v∈ V ) {
d[v] = A[s,v];
truoc[v]=s;
}
d[s]=0;
T = V\{s};
/*T là tập đỉnh có nhãn tạm
thời*/
/* Bước lặp */
while (T != ∅ ) {
Tìm đỉnh u ∈ T sao cho
d[u] = min { d[z] | z∈T};
T= T\{u};
/*cố định nhãn đỉnh u*/
for ( v ∈ T ) {
/*Gán lại nhãn cho các đỉnh
trong T*/
if (d[v] > d[u] + A[u,v]) {
d[v] = d[u] + A[u,v];
truoc[v] =u;
}
}
}
}
CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT
• 5.3 Thuật toán Dijkstra (3/6)
– Ví dụ về giải thuật Dijkstra:
– Cho đồ thị G như trên, tìm đường từ 1->6
– Các bước thực hiện
89
Bước lặp Đỉnh 1 Đỉnh 2 Đỉnh 3 Đỉnh 4 Đỉnh 5 Đỉnh 6
Khởi tạo 0,1 4,1 2,1 (∗) ∞,1 ∞,1 ∞,1
1 - 3,3 (∗) - 10,3 12,3 ∞,1
2 - - - 8,2 (∗) 12,3 ∞,1
3 - - - - 10,4 (∗) 14,4
4 - - - - - 13,5 (∗)
5 - - - - - -
(∗)
CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT
• 5.3. Thuật toán Dijkstra (4/6)
– Chương trình minh họa giải thuật Dijkstra:
90
#include "conio.h"
#include "io.h"
#include "iostream"
using namespace std;
#define MAX 100
#define TRUE 1
#define FALSE 0
int n, s, z;
char chon;
int truoc[MAX],d[MAX],G[MAX][MAX];
int final[MAX];
void Init(void){
FILE * fp;
int i, j;
fp = fopen("dothi.in","r");
fscanf(fp,"%d", &n);
cout<<"\n So dinh:"<<n;
cout<<"\n Ma tran trong so:";
for(i=1;i<=n;i++){
cout<<"\n";
for(j=1;j<=n;j++){
fscanf(fp,"%d",&G[i][j]);
cout<<" "<<G[i][j];
if(G[i][j]==0)
G[i][j]=32000;
}
}
fclose(fp);
}
void Result(void){
int i,j;
cout<<"\n Duong di ngan nhat tu
"<<s<<" den "<<z<<" la\n";
cout<<" <="<<z;
i=truoc[z];
CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT
• 5.3. Thuật toán Dijkstra (5/6)
– Chương trình minh họa giải thuật Dijkstra:
91
while(i!=s){
cout<<" <="<<i;
i=truoc[i]; }
cout<<" <="<<s;
cout<<"\n Do dai duong di la: 
"<<d[z]; }
void Dijkstra(void){
int v, u, minp;
cout<<"\n Tim duong di tu s= ";
cin>>s;
cout<<" den z=";
cin>>z;
for(v=1;v<=n; v++){
d[v]=G[s][v];
truoc[v]=s;
final[v]=FALSE;
}
truoc[s]=0; 
d[s]=0;
final[s]=TRUE;
while(!final[z]) {
minp=32000;
for(v=1; v<=n; v++){
if((!final[v]) &&
(minp>d[v]) ){
u=v;
minp=d[v];}
}
final[u]=TRUE; 
if(!final[z]){
for(v=1; v<=n; v++){
if ((!final[v]) && 
(d[u]+ G[u][v]< d[v])){
d[v]=d[u]+G[u][v];
truoc[v]=u;}
}
}
}
}
CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT
• 5.3. Thuật toán Dijkstra (6/6)
– Chương trình minh họa giải thuật Dijkstra:
92
void main(void)
{
Init();
Dijkstra();
Result();
getch();
}
93
Luồng vận tải:
 Định nghĩa: Mạng vận tải là một đồ thị có hướng,
không có khuyên và có trọng số G=(V,E) với V={v0,
v1, ..., vn} thoả mãn:
1)Mỗi cung e E có trọng số m(e) là một số nguyên không
âm và được gọi là khả năng thông qua của cung e.
2) Có một và chỉ một đỉnh v0 không có cung đi vào, tức
là deg-(v0)=0. Đỉnh v0 được gọi là lối vào hay đỉnh
phát của mạng.
3) Có một và chỉ một đỉnh vn không có cung đi ra, tức là
deg+(vn)=0. Đỉnh vn được gọi là lối ra hay đỉnh thu của
mạng.
CHƯƠNG VI BÀI TOÁN LUỒNG CỰC ĐẠI
94
Luồng vận tải:
 Định nghĩa: Để xác định lượng vật chất chuyển qua
mạng vận tải G=(V,E), người ta đưa ra khái niệm
luồng vận tải và được định nghĩa như sau:
Hàm ϕ xác định trên tập cung E và nhận giá trị nguyên
được gọi là luồng vận tải của mạng vận tải G nếu ϕ
thoả mãn:
1)ϕ(e) ≥ 0, e E.
2)  v V; v ≠ v0; v ≠ vn
-(v) = {e E; e có đỉnh cuối là v}
+(v) = {e E; e có đỉnh đầu là v}
CHƯƠNG VI BÀI TOÁN LUỒNG CỰC ĐẠI

   
)()(
)()(
veve
ee 
95
Luồng vận tải:
3) ϕ(e) ≤ m(e), e E.
Ta xem ϕ(e) như là lượng hàng chuyển trên cung
e=(u,v) từ đỉnh u đến đỉnh v và không vượt quá khả
năng thông qua của cung này.
4)
Đại lượng ϕvn (ký hiệu là ϕn ) được gọi là luồng qua
mạng, hay cường độ luồng tại điểm vn hay giá trị của
luồng ϕ. Bài toán đặt ra ở đây là tìm ϕ để ϕvn đạt giá
trị lớn nhất, tức là tìm giá trị lớn nhất của luồng.
CHƯƠNG VI BÀI TOÁN LUỒNG CỰC ĐẠI
)(:)()(
)0 ()(
n
veve
vee
n
 
   
96
Luồng vận tải:
Định nghĩa: Cho mạng vận tải G=(V,E) và A  V.
Ký hiệu: Γ−(A)={(u,v) E | v A, u∉A},
Γ+(A)={(u,v) E | u A, v∉A}.
Đối với tập cung M tuỳ ý, đại lượng
được gọi là luồng của tập cung M.
Hệ quả: Cho ϕ là luồng của mạng vận tải G=(V,E) và
A  V \{v0,vn}. Khi đó: ϕ(Γ
−(A))=ϕ(Γ+(A)).
CHƯƠNG VI BÀI TOÁN LUỒNG CỰC ĐẠI

Me
eM )()( 
97
Cho mạng vận tải G=(V,E). Hãy tìm luồng ϕ để đạt
ϕvn max trên mạng G.
 Định nghĩa: Cho A  V là tập con tuỳ ý không
chứa lối vào v0 và chứa lối ra vn. Tập Γ
−(A) được
gọi là một thiết diện của mạng vận tải G.
Đại lượng
được gọi là khả năng thông qua của thiết diện Γ−(A)
CHƯƠNG VI BÀI TOÁN LUỒNG CỰC ĐẠI

  
 
)(
)())((
Ae
emAm
98
Định nghĩa: Cung e trong mạng vận tải G với luồng
vận tải ϕ được gọi là cung bão hoà nếu
ϕ(e)=m(e).
Luồng ϕ của mạng vận tải G được gọi là luồng đầy
nếu mỗi đường đi từ v0 đến vn đều chứa ít nhất
một cung bão hoà.
Ta thấy: nếu luồng ϕ trong mạng vận tải G chưa đầy
thì nhất định tìm được đường đi α từ lối vào v0
đến lối ra vn không chứa cung bão hoà. Khi đó ta
nâng luồng ϕ thành ϕ’ như sau:
CHƯƠNG VI BÀI TOÁN LUỒNG CỰC ĐẠI
99
Khi đó ϕ’ cũng là một luồng, mà giá trị của nó là:
ϕ’n = ϕn +1 > ϕn.
Như vậy, đối với mỗi luồng không đầy ta có thể
nâng giá trị của nó và nâng cho tới khi nhận được
một luồng đầy.
CHƯƠNG VI BÀI TOÁN LUỒNG CỰC ĐẠI
100
Thuật toán Ford-Fulkerson: Để tìm luồng cực đại
của mạng vận tải G, xuất phát từ luồng tuỳ ý ϕ
của G, rồi nâng luồng lên đầy, sau đó áp dụng
thuật toán Ford-Fulkerson theo 3 bước:
Bước 1 (đánh dấu ở đỉnh của mạng): Lối vào v0
được đánh dấu bằng 0.
1) Nếu đỉnh vi đã được đánh dấu thì ta dùng chỉ số
+i để đánh dấu cho mọi đỉnh y chưa được đánh
dấu mà (vi,y) E và cung này chưa bão hoà
(ϕ(vi,y)<m(vi,y)).
2) Nếu đỉnh vi đã được đánh dấu thì ta dùng chỉ số
−i để đánh dấu cho mọi đỉnh z chưa được đánh
dấu mà (z,vi) E và luồng của cung này dương
(ϕ(z,vi)>0).
101
Thuật toán Ford-Fulkerson:
Nếu ta đánh dấu được tới lối ra vn thì trong G  giữa v0
và vn một xích α, mọi đỉnh đều khác nhau và được
đánh dấu theo chỉ số của đỉnh liền trước nó (chỉ sai
khác nhau về dấu). Khi đó chắc chắn ta nâng được
giá trị của luồng.
Bước 2 (nâng giá trị của luồng): Ta đặt:
ϕ’(e) = ϕ(e), nếu e∉α,
ϕ’(e) = ϕ(e)+1, nếu e α được định hướng theo chiều
của xích α đi từ v0 đến vn,
ϕ’(e) = ϕ(e)−1, nếu e α được định hướng ngược với
chiều của xích α đi từ v0 đến vn.
Lặp lại một vòng mới. Vì khả năng thông qua của các
cung đều hữu hạn, nên quá trình phải dừng lại sau
một số hữu hạn bước.
102
Thuật toán Ford-Fulkerson:
Bước 3:
Nếu với luồng ϕ0 bằng phương pháp trên ta không
thể nâng giá trị của luồng lên nữa, nghĩa là ta
không thể đánh dấu được đỉnh vn, thì ta nói rằng
quá trình nâng luồng kết thúc và ϕ0 đã đạt giá trị
cực đại, đồng thời gọi ϕ0 là luồng kết thúc.
 Định lý (Ford-Fulkerson): Trong mạng vận tải
G=(V,E), giá trị lớn nhất của luồng bằng khả năng
thông qua nhỏ nhất của thiết diện, nghĩa là:
CHƯƠNG VI BÀI TOÁN LUỒNG CỰC ĐẠI
))((minmax
,, 0
Am
AvAvVA
v
n
n
 
 
103
Ví dụ: Cho mạng vận tải với khả năng thông qua
được đặt trong khuyên tròn, luồng được ghi trên
các cung. Tìm luồng cực đại của mạng này.
104
Luồng ϕ có đường đi (v0,v4), (v4,v6), (v6,v8) gồm các cung
chưa bão hoà nên nó chưa đầy. Do đó có thể nâng luồng
của các cung này lên một đơn vị, để được ϕ1.
Do mỗi đường xuất phát từ v0 đến v8 đều chứa ít nhất một
cung bão hoà, nên luồng ϕ1 là luồng đầy. Song nó chưa
phải là luồng cực đại.
Áp dụng TT Ford-Fulkerson để nâng luồng ϕ1.
105
Xét xích α=(v0, v4, v6, v3, v7, v8). Quá trình đánh dấu từ
v0 đến v8 để có thể nâng luồng ϕ
1 lên một đơn vị
bằng cách biến đổi luồng tại các cung thuộc xích α
được đánh dấu. Sau đó ta có luồng ϕ2.
106
Tương tự, xét xích β=(v0, v1, v5, v2, v6, v3, v7, v8). Nâng
luồng ϕ2 lên một đơn vị, sau đó ta có luồng ϕ3.
V0
107
Tiếp theo ta chỉ có thể đánh dấu được đỉnh v0 nên
quá trình nâng luồng kết thúc và ta được giá trị
của luồng cực đại là:
ϕ3v8 = 6+12+8 = 26.
Mặt khác, thiết diện nhỏ nhất Γ−(A)
với A={v1, v2, ..., v8}
là Γ− (A)={(v0,v1), (v0,v2), (v0,v3), (v0,v4)}.
CHƯƠNG VI BÀI TOÁN LUỒNG CỰC ĐẠI