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

G với khả năng thông qua của các cung và các đỉnh. 
 93 
Hình 5. Hình 5a cho ví dụ mạng G với khả năng thông qua ở cung và đỉnh. 
Hình 5b là mạng G’ tƣơng ứng chỉ có khả năng thông qua trên các cung. 
6.4.3. M ng trong đó k ả năng t ông qua của mỗ cung bị c ặn a p ía. 
Xét mạng G mà trong đó mỗi cung (u, v) có khả năng thông qua (cận trên của luồng trên 
cung) c(u,v) và cận dƣới của luồng là d(u,v). Bài toán đặt ra là liệu có tồn tại luồng tƣơng 
hay không? 
Đƣa vào mạng G đỉnh phát sa và đỉnh thu ta và xây dựng mạng Ga theo qui tắc: 
qua là d(u,v). Giảm c(u,v) đi d(u,v) tức là thay khả năng thông qua của cung (u,v) bởi c(u,v) –
d(u,v) còn cận dƣới của nó đặ 
 94 
Hình 6. Mạng với khả năng thông qua bị chặn hai phía. 
Hình 6(a) cho ví dụ mạng G với khả năng thông qua của các cung bị chặn cả hai phía. Đồ thị 
Ga tƣơng ứng đƣợc cho trong hình 6(b). 
Ký hiệu d* d(u,v). 
Địn lý 4. 
1) Nếu luồng lớn nhất trong mạng Ga từ sa đến ta bằng d* thì tồn tại luồng tƣơng thích trong 
G. 
2) Nếu luồng lớn nhất trong mạng Ga từ sa đến ta là khác d* thì không tồn tại luồng tƣơng 
thích trong G. 
 95 
Bài tập 
 Bài 1 
Cho G=(V,E) đồ thị có hƣớng trong đó không có cung (s,t). Chứng minh rằng số đƣờng đi cơ 
bản nối hai đỉnh s và t là bằng số ít nhất các đỉnh của đồ thị cần loại bỏ để trong đồ thị không 
còn đƣờng đi nối s với t. 
Bài 2 
Xây dựng thuật toán tìm tập E1 tất cả các cung của đồ thị mà việc tăng khả năng thông qua 
của bất kỳ cung nào trong E đều dẫn đến tăng giá trị của luồng cực đại trong mạng. 
Bài 3 
Cho hai dãy số nguyên dƣơng {pi, i=1,2,…,m} và {qj, j=1,2,…,n}. Hãy xây dựng ma trận 
A={aij : i=1,2,…,m; j=1,2,…n} với các phần tử 
ai j i , tổng các phần tử trên cột j là qj. 
Bài 4 
Có m chàng trai, n cô gái và k bà mối, Mỗi bà mối p (p=1,2,…,k) có một danh sách Lp một số 
chàng trai và cô gái trong số các chàng trai và cô gái nói trên là khách hàng của bà ta. Bà mối 
p có thể se duyên cho bất cứ cặp trai gái nào là khách hàng của bà ta, nhƣng không đủ sức tổ 
chức quá dp đám cƣới. Hãy xây dựng thuật toán căn cứ vào danh sách Lp, dp, p=1,2,…,k; đƣa 
ra cách tổ chức nhiều nhất các đám cƣới giữa m chàng trai và n cô gái với sự giúp đỡ của các 
bà mối. 
Bài 5 : Chuyển bi 
Cậu bé vẽ N (N<=100) vòng tròn, đánh số từ 1 tới N và tô màu các vòng tròn đó (có thể có 
các vòng tròn có màu giống nhau), sau đó nối từng cặp các cung định hƣớng, mỗi cung có 
một màu nhất định. Các màu (của cung và vòng tròn) đƣợc đánh số từ 1 đến 100. 
Cậu bé chọn 3 số nguyên khác nhau L, K và Q nằm trong phạm vi từ 1 tới N, đặt vào trong 
các vòng tròn số L và K mỗi vòng một hòn bi, sau đó bắt đầu di chuyển bi theo nguyên tắc 
sau: 
Bi chỉ đƣợc chuyển theo cung có màu trùng với màu của vòng tròn chứa viên bi thứ 2. 
Bi chỉ đƣợc chuyển theo chiều cung 
Hai viên bi không đƣợc đồng thời ở cùng một vòng tròn; 
Không nhất thiết phải di chuyển lần lƣợt các viên bi, 
Quá trình di chuyển kết thúc, khi một trong hai viên bi tới vòng tròn Q. 
Hãy lập trình xác định cách di chuyển để chấm dứt quá trình sau một số ít nhất các bƣớc 
chuyển. 
 96 
Dữ liệu vào từ file BL.INP: 
Dòng đầu: 4 số nguyên N L K Q 
Dòng thứ 2: N số nguyên C1, C2,…,Cn; Ci là màu vòng tròn i 
M dòng sau: mỗi dòng 3 số nguyên Ai Bi Di; xác định cung màu Di từ vòng tròn Ai tới vòng 
tròn Bi. 
Các số trên một dòng cách nhau một dấu cách. 
Kết quả đƣa ra file BL.OUT: 
Dòng đầu: CO hoặc KHONG, cho biết quá trình có kết thúc đƣợc hay không, 
Nếu dòng đầu là CO thì dòng 2 chứa số nguyên xác định số bƣớc chuyển tối thiểu . 
BL.INP BL.OUT 
5 3 4 1 
2 3 2 1 4 
8 
2 1 2 
4 1 5 
4 5 2 
4 5 2 
5 1 3 
3 2 2 
2 3 4 
5 3 1 
3 5 1 
CO 
3 
Bài 6 : Bảng điện 
Một lƣới ô vuông đƣợc phủ trên một bảng điện hình vuông. Vị trí nằm trên giao của 2 đƣờng 
kề của lƣới sẽ đƣợc gọi là nút. Tất cả có nxn nút trên lƣới. 
 97 
Có một số nút chứa tiếp điểm. Nhiệm vụ của bạn là cần nối các tiếp điểm với các nút ở trên 
biên của bảng bởi các đoạn dây dẫn (gọi là các mạch). Các mạch chỉ đƣợc chạy dọc theo các 
đƣờng kẻ của lƣới (nghĩa là không đƣợc chạy theo đƣờng chéo). Hai mạch không đƣợc phép 
có điểm chung, vì vậy hai mạch bất kỳ không đƣợc phép cùng chạy qua cùng một đoạn đƣờng 
kẻ của lƣới cũng nhƣ không đƣợc chạy qua cùng một nút của lƣới. Các mạch cũng không 
đƣợc chạy dọc theo các đoạn kẻ của lƣới ở trên biên (mạch phải kết thúc khi nó gặp biên) và 
cũng không đƣợc chạy qua nút chứa tiếp điểm khác. 
Ví dụ: Bảng điện và các tiếp điểm đƣợc cho trong hình 2a. Nút tô đậm trong hình vẽ thể hiện 
vị trí các tiếp điểm. 
Yêu cầu: Viết chƣơng trình cho phép nối đƣợc một số nhiều nhất các tiếp điểm với bbiên. Các 
tiếp điểm ở trên biên đã thỏa mãn đòi hỏi đặt ra, vì thế không nhất thiết phải thực hiện mạch 
nối chúng. Nếu nhƣ có nhiều lời giải thì chi cần đƣa ra một trong số chúng. 
Dữ liệu vào: file văn bản ELE.INP: 
Dòng đầu tiên chứa số nguyên n (3 <= n <= 15). 
Mỗi dòng trong số n dòng tiếp theo chứa n ký tự phân cách nhau bởi một dấu cách. Mỗi ký 
tự chỉ là 0 hoặc 1. Ký tự 1 thể hiện tiếp điểm, ký tự 0 thể hiện nút không có tiếp điểm trên vị 
trí tƣơng ứng của lƣới. Các nút đƣợc đánh số từ 1 đến n*n theo thứ tự từ trái sang phải, từ trên 
xuống dƣới. Chỉ số của nút chứa tiếp điểm sẽ là chỉ số của tiếp điểm. 
Kết quả: ghi ra file ELE.OUT: 
Dòng đầu tiên chứa k là số tiếp điểm lớn nhất có thể nối với biên bởi các mạch. 
Mỗi dòng trong số k dòng tiếp theo mô tả một mạch nối một trong số k tiếp điểm với biên 
theo qui cách sau: đầu tiên là chỉ số của tiếp điểm đƣợc nối, tiếp đến là dãy các ký tự mô tả 
hƣớng của mạch nối: E: đông, W: tây, N: bắc, S: nam. Giữa chỉ số và dãy ký tự phải có đúng 
một dấu cách, còn giữa các ký tự trong dãy ký tự không đƣợc có dấu cách. 
Kết quả phải đƣợc đƣa ra theo thứ tự tăng dần của chỉ số tiếp điểm. 
Ví dụ: 
 98 
ELE.IN ELE.OUT 
6 
0 0 0 1 1 1 
0 0 0 0 1 0 
0 0 0 1 1 1 
0 0 0 0 0 0 
0 0 1 1 1 1 
0 0 0 1 0 1 
11 E 
16 NWN 
17 SE 
27 S 
28 NWWSS 
29 S 
 99 
TÀI LIỆU THAM KHẢO 
[1] Nguyễn Thanh Hùng. Nguyễn Đức Nghĩa, Giáo Trình Lý Thuyết Đồ Thị, NXB Đại học 
Quốc Gia TPHCM, 2007. 
[2] Doãn Châu Long. Lý thuyết quy hoạch tuyến tính và lý thuyết đồ thị. NXB Giáo dục. 
1982. 
[3] Kenneth Rosen. Toán học rời rạc và ứng dụng trong tin học. NXB KHKT Hà nội. 1998. 
[4] Giáo trình Lý thuyết đồ thị, Đại học Quốc gia TP Hồ Chí Minh 
THI KẾT TH C HỌC PHẦN 
 ưu Không viết, vẽ, sửa đề thi, nộp lại đề sau khi thi 
Bộ môn: K oa ọc máy tín - Học p ần: Lý t uyết đồ t ị 
Đề t số 1 T ờ g an 75 p út Đề t mẫu 
Câu 1: (4 điểm) 
Cho đồ thị: 
 Yêu cầu 
- Biểu diễn đồ thị theo phƣơng pháp danh sách cạnh. 
- Áp dụng thuật toán DFS kiểm tra xem đồ thị có liên thông không? 
Câu 2: (6 điểm) 
 Cho đồ thị: 
 Yêu cầu 
- Đồ thị trên có là đồ thị Ole không? Vì sao? 
- Xác định các cầu của đồ thị trên? 
- Áp dụng thuật toán Kruskal tìm cây khung nhỏ nhất của đồ thị. 
------------------------------ * Hết * ------------------------------ 
4 
1 
5 
6 
3 
2 
7 
12 
3 
7 
10 
6 
4 
5 
8 
9 
THI KẾT TH C HỌC PHẦN 
 ưu Không viết, vẽ, sửa đề thi, nộp lại đề sau khi thi 
Bộ môn: K oa ọc máy tín - Học p ần: Lý t uyết đồ t ị 
Đề t số 2 T ờ g an 75 p út Đề t mẫu 
Câu 1: (4 điểm) 
Cho đồ thị: 
 Yêu cầu 
- Biểu diễn đồ thị theo phƣơng pháp danh sách kề. 
- Áp dụng thuật toán BFS kiểm tra xem đồ thị có liên thông không? 
Câu 2: (6 điểm) 
 Cho đồ thị: 
Yêu cầu 
- Xác định 1 đƣờng đi Hamilton trong đồ thị trên? 
- Xác định bậc của các đỉnh trong đồ thị trên? 
- Áp dụng thuật toán Kruskal tìm cây khung nhỏ nhất của đồ thị. 
------------------------------ * Hết * ------------------------------ 
5 1 
4 
3 
6 
2 
2 
1 
4 5 
6 
3 
1 
2 
6 
2 
1 
6 
2 
6 
THI KẾT TH C HỌC PHẦN 
 ưu Không viết, vẽ, sửa đề thi, nộp lại đề sau khi thi 
Bộ môn: K oa ọc máy tín - Học p ần: Lý t uyết đồ t ị 
Đề t số 3 T ờ g an 75 p út Đề t mẫu 
Câu 1: (4 điểm) 
Cho đồ thị: 
 Yêu cầu 
- Biểu diễn đồ thị theo phƣơng pháp ma trận kề. 
- Áp dụng thuật toán DFS kiểm tra xem đồ thị có liên thông không? 
Câu 2: (6 điểm) 
 Cho đồ thị: 
 Yêu cầu 
- Xác định xem đồ thị trên có là đồ thị Ole không? Vì sao? 
- Xác định các cầu của đồ thị trên? 
- Áp dụng thuật toán Dijkstra tìm đƣờng đi ngắn nhất của đồ thị từ đỉnh 1 
tới đỉnh 6. 
------------------------------ * Hết * ------------------------------ 
1 
2 
3 
4 
5 
6 
8 
7 
1 
2 3 
6 
5 4 
4 
6 
7 
1 
8 
5 
2 
10 
2 
THI KẾT TH C HỌC PHẦN 
 ưu Không viết, vẽ, sửa đề thi, nộp lại đề sau khi thi 
Bộ môn: K oa ọc máy tín - Học p ần: Lý t uyết đồ t ị 
Đề t số 4 T ờ g an 75 p út Đề t mẫu 
Câu 1: (4 điểm) 
Cho 1 đồ thị gồm có sáu đỉnh đánh số từ 1,2,…6 theo thứ tự các dòng từ trên xuống, cột từ 
trái sang phải dƣới dạng một ma trận kề nhƣ sau: 
 Yêu cầu 
- Hãy vẽ đồ thị tƣơng ứng với danh sách đƣợc cho ở trên. 
- Áp dụng thuật toán DFS kiểm tra xem đồ thị có liên thông không? 
Câu 2: (6 điểm) 
Cho 1 đồ thị có trọng số nhƣ hình vẽ: 
 Yêu cầu: 
- Xác định xem đồ thị trên có là đồ thị Ole không? Vì sao? 
- Áp dụng thuật toán Kruskal vào đồ thị trên để tìm cây khung nhỏ nhất 
của đồ thị. 
------------------------------ * Hết * ------------------------------ 
Bộ môn: K oa ọc máy tín - Học p ần: Lý thuyết đồ thị 
0 1 1 1 1 1 
1 0 1 1 0 0 
1 1 0 0 1 1 
1 1 0 0 1 1 
1 0 1 1 0 1 
1 0 1 1 1 0 
THI KẾT TH C HỌC PHẦN 
 ưu Không viết, vẽ, sửa đề thi, nộp lại đề sau khi thi 
Đề t số 5 T ờ g an 75 p út Đề t mẫu 
Câu 1: (4 điểm) 
Cho đồ thị: 
 Yêu cầu 
- Biểu diễn đồ thị theo phƣơng pháp danh sách kề. 
- Áp dụng thuật toán BFS kiểm tra xem đồ thị có liên thông không? 
Câu 2: (6 điểm) 
 Cho đồ thị: 
 Yêu cầu 
- Đồ thị trên có là đồ thị Ole không? Vì sao? 
- Trình bày thuật toán Prim, áp dụng thuật toán vào đồ thị trên bắt đầu từ 
đỉnh 4? 
------------------------------ * Hết * ------------------------------ 
4 
1 
5 
6 
3 
2 
7 
12 
3 
7 
10 
6 
4 
5 
8 
9