Bài giảng Toán rời rạc - Phần 2: Lý thuyết đồ thị - Chương 1: Các khái niệm cơ bản - Nguyễn Đức Nghĩa

Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
1 
Phần 2 
LÝ THUYẾT ĐỒ THỊ 
Graph Theory 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
2 
Nội dung 
Chương 1. Các khái niệm cơ bản 
Đồ thị vô hướng và có hướng 
Các thuật ngữ cơ bản 
Một số dạng đồ thị vô hướng đặc biệt 
Chương 2. Biểu diễn đồ thị 
Ma trận kề, ma trận trọng số, Ma trận liên thuộc đỉnh cạnh 
Danh sách cạnh, Danh sách kề 
Chương 3. Duyệt đồ thị 
Tìm kiếm theo chiều sâu; Tìm kiếm theo chiều rộng 
Tìm đường đi và kiểm tra tính liên thông 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
3 
Nội dung 
Chương 4. Cây và cây khung của đồ thị 
Cây và các tính chất của cây 
Cây khung của đồ thị 
Bài toán cây khung nhỏ nhất 
Chương 5. Bài toán đường đi ngắn nhất 
Phát biểu bài toán 
Đường đi ngắn nhất xuất phát từ một đỉnh (Thuật toán Dijkstra, Ford-Bellman) 
Đường đi ngắn nhất trên đồ thị không có chu trình 
Đường đi ngắn nhất giữa mọi cặp đỉnh (Thuật toán Floyd) 
Chương 6. Bài toán luồng cực đại trong mạng 
Mạng, luồng và bài toán luồng cực đại 
Định lý Ford-Fulkerson 
Thuật toán Ford-Fulkerson 
Một số ứng dụng 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
4 
Chương 1 
CÁC KHÁI NIỆM CƠ BẢN 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
5 
Chương 1  CÁC KHÁI NIỆM CƠ BẢN 
1.1. Đồ thị trong thực tế 
1.2. Các loại đồ thị 
1.3. Bậc của đỉnh 
1.4. Đồ thị con 
1.5. Đồ thị đẳng cấu 
1.6. Đường đi và chu trình 
1.7. Tính liên thông 
1.8. Một số loại đồ thị đặc biệt 
1.9. Tô màu đồ thị 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
6 
Trong toán học đời thường hiểu là:  Bản vẽ hay Sơ đồ biểu diễn dữ liệu nhờ sử dụng hệ thống toạ độ. 
Trong toán rời rạc: Đây là cấu trúc rời rạc có tính trực quan cao, rất tiện ích để biểu diễn các quan hệ. 
Đồ thị là gì? 
Không phải 
cái ta muốn đề cập 
Không phải cái này 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
7 
Các ứng dụng thực tế của đồ thị 
Có tiềm năng ứng dụng trong nhiều lĩnh vực (Đồ thị có thể dùng để biểu diễn các quan hệ. Nghiên cứu quan hệ giữa các đối tượng là mục tiêu của nhiều lĩnh vực khác nhau). 
Ứng dụng trong mạng máy tính, mạng giao thông, mạng cung cấp nước, mạng điện,) lập lịch, tối ưu hoá luồng, thiết kế mạch, quy hoạch phát triển... 
Các ứng dụng khác: Phân tích gen, trò chơi máy tính, chương trình dịch, thiết kế hướng đối tượng,  
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
8 
Mối liên hệ giữa các môn học 
321 
143 
142 
322 
326 
341 
370 
378 
401 
421 
Đỉnh = môn học 
Cạnh có hướng = đk tiên quyết 
373 
410 
413 
415 
417 
461 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
9 
Biểu diễn mê cung 
S 
Đỉnh = phòng 
Cạnh = cửa thông phòng hoặc hành lang 
S 
E 
B 
E 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
10 
Biểu diễn mạch điện (Electrical Circuits) 
Đỉnh = nguồn, công tắc, điện trở,  
Cạnh = đoạn dây nối 
Nguồn 
Công tắc 
Điện trở 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
11 
Các câu lệnh của chương trìnhProgram statements 
x1=q+y*z 
x2=y*z-q 
Thoạt nghĩ: 
Loại 
Biểu thức con 
chung: 
y 
z 
* 
- 
q 
+ 
q 
* 
x1 
x2 
y 
z 
- 
q 
+ 
q 
* 
x1 
x2 
Đỉnh = ký hiệu/phép toán 
Cạnh = mối quan hệ 
y*z tính hai lần 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
12 
Yêu cầu trình tự (Precedence) 
S 1 	a=0; 
S 2 	b=1; 
S 3 	c=a+1 
S 4 	d=b+a; 
S 5 	e=d+1; 
S 6 	e=c+d; 
3 
1 
2 
6 
5 
4 
Các câu lệnh nào phải thực hiện trước S 6 ? 
S 1 , S 2 , S 3 , S 4 
Đỉnh = câu lệnh 
Cạnh = yêu cầu trình tự 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
13 
Truyền thông trong mạng máy tính (Information Transmission in a Computer Network) 
Hà nội 
New York 
Bắc kinh 
Tokyo 
Sydney 
Seoul 
Đỉnh = máy tính 
Cạnh = tốc độ truyền thông 
128 
140 
181 
30 
16 
56 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
14 
Luồng giao thông trên xa lộ (Traffic Flow on Highways) 
Đỉnh = thành phố 
Cạnh = lượng xe cộ trên 
tuyến đường cao tốc kết nối giữa các thành phố 
UW 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
15 
Mạng xe buýt 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
16 
Mạng tàu điện ngầm 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
17 
Sơ đồ đường phố 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
18 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
19 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
20 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
21 
Chương 1  CÁC KHÁI NIỆM CƠ BẢN 
1.1. Đồ thị trong thực tế 
1.2. Các loại đồ thị 
1.3. Bậc của đỉnh 
1.4. Đồ thị con 
1.5. Đồ thị đẳng cấu 
1.6. Đường đi và chu trình 
1.7. Tính liên thông 
1.8. Một số loại đồ thị đặc biệt 
1.9. Tô màu đồ thị 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
22 
Đồ thị vô hướng  (Undirected Graphs) 
 Định nghĩa. Đơn ( đa ) đồ thị vô hướng G = ( V,E ) là cặp gồm: 
Tập đỉnh V là tập hữu hạn phần tử, các phần tử gọi là các đỉnh 
Tập cạnh E là tập ( họ ) các bộ không có thứ tự dạng 
 ( u, v ), u, v V, u ≠v 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
23 
Đơn đồ thị vô hướng  (Simple Graph) 
Ví dụ: Đơn đồ thị G 1 = ( V 1 , E 1 ), trong đó 
 V 1 ={ a, b, c, d, e, f, g, h }, 
 E 1 ={( a,b ), ( b,c ), ( c,d ), ( a,d ), ( d,e ), ( a,e ), ( d,b ), ( f,g )}. 
Đồ thị G 1 
a 
b 
e 
d 
c 
g 
f 
h 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
24 
Đa đồ thị vô hướng  (Multi Graphs) 
Ví dụ: Đa đồ thị G 2 = ( V 2 , E 2 ), trong đó 
 V 2 ={ a, b, c, d, e, f, g, h }, 
 E 2 ={( a,b ), ( b,c ), ( b,c ), ( c,d ), ( a,d ), ( d,e ), ( a,e ), ( a,e ), ( a, e ), ( d,b ), ( f,g )}. 
Đồ thị G 2 
d 
Cạnh lặp 
e 
a 
b 
c 
f 
g 
h 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
25 
Đồ thị có hướng  (Directed Graph) 
 Định nghĩa. Đơn ( đa ) đồ thị có hướng G = ( V,E ) là cặp gồm: 
Tập đỉnh V là tập hữu hạn phần tử, các phần tử gọi là các đỉnh 
Tập cung E là tập ( họ ) các bộ có thứ tự dạng 
 ( u, v ), u, v V, u ≠v 
Ví dụ: Đơn đồ thị có hướng G 3 = ( V 3 , E 3 ), trong đó 
 V 3 ={ a, b, c, d, e, f, g, h }, 
	E 3 ={( a,b ), ( b,c ), ( c,b ), ( d,c ), ( a,d ), ( b, d ), ( a,e ), ( d,e ), 
 ( e,a ), ( f,g ), ( g,f )} 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
26 
Đơn đồ thị có hướng  (Simple digraph) 
Đồ thị G 3 
a 
b 
e 
d 
c 
g 
f 
h 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
27 
Đa đồ thị có hướng  (Multi Graphs) 
Ví dụ: Đa đồ thị có hướng G 4 = ( V 4 , E 4 ), trong đó 
 V 4 ={ a, b, c, d, e, f, g, h }, 
	E 4 ={( a,b ), ( b,c ), ( c,b ), ( d,c ), ( a,d ), ( b, d ), ( a,e ), ( a,e ), 
 ( d,e ), ( e,a ), ( f,g ), ( g,f )} 
Đồ thị G 4 
e 
a 
d 
b 
c 
f 
g 
h 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
28 
Các loại đồ thị: Tóm tắt 
Chú ý: 
Một dạng đồ thị ít sử dụng hơn, đó là giả đồ thị. Giả đồ thị là đa đồ thị mà trong đó có các khuyên (cạnh nối 1 đỉnh với chính nó). 
Cách phân loại đồ thị dùng ở đây chưa chắc đã được chấp nhận trong các tài liệu khác... 
Loại 
Kiểu cạnh 
Có cạnh lặp? 
Đơn đồ thị vô hướng 
Vô hướng 
Không 
Đa đồ thị vô hướng 
Vô hướng 
Có 
Đơn đồ thị có hướng 
Có hướng 
Không 
Đa đồ thị có hướng 
Có hướng 
Có 
Khuyên (loop) 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
29 
Các thuật ngữ Graph Terminology 
 Chúng ta cần các thuật ngữ liên quan đến mối quan hệ giữa các đỉnh và các cạnh của đồ thị sau: 
Kề nhau, nối, đầu mút, bậc, bắt đầu, kết thúc, bán bậc vào, bán bậc ra, 
u 
v 
v 
u 
e 
e 
Cạnh vô hướng e =( u,v ) 
Cạnh có hướng (cung) e =( u,v ) 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
30 
Kề (Adjacency) 
Cho G là đồ thị vô hướng với tập cạnh E . Giả sử e E là cặp ( u , v ) . Khi đó ta nói: 
u , v là kề nhau/lân cận/nối với nhau ( adjacent / neighbors / connected) . 
Cạnh e là liên thuộc với hai đỉnh u và v . 
Cạnh e nối ( connect ) u và v . 
Các đỉnh u và v là các đầu mút ( endpoints ) của cạnh e . 
v 
u 
e 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
31 
Tính kề trong đồ thị có hướng 
Cho G là đồ thị có hướng (có thể là đơn hoặc đa) và giả sử e = ( u , v ) là cạnh của G . Ta nói: 
u và v là kề nhau, u là kề tới v , v là kề từ u 
e đi ra khỏi u, e đi vào v . 
e nối u với v , e đi từ u tới v 
Đỉnh đầu ( initial vertex) của e là u 
Đỉnh cuối ( terminal vertex ) của e là v 
u 
v 
e 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
32 
Chương 1  CÁC KHÁI NIỆM CƠ BẢN 
1.1. Đồ thị trong thực tế 
1.2. Các loại đồ thị 
1.3. Bậc của đỉnh 
1.4. Đồ thị con 
1.5. Đồ thị đẳng cấu 
1.6. Đường đi và chu trình 
1.7. Tính liên thông 
1.8. Một số loại đồ thị đặc biệt 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
33 
Bậc của đỉnh (Degree of a Vertex) 
Giả sử G là đồ thị vô hướng, v V là một đỉnh nào đó. 
Bậc của đỉnh v , deg( v ) , là số cạnh kề với nó. 
Đỉnh bậc 0 được gọi là đỉnh cô lập ( isolated ). 
Đỉnh bậc 1 được gọi là đỉnh treo ( pendant ). 
Các ký hiệu thường dùng: 
 ( G ) = min {deg( v ): v V }, 
 ( G ) = max {deg( v ): v V }. 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
34 
Ví dụ 
a 
b 
c 
e 
d 
f 
deg(d) = 3 
deg(f) = 0 
f là đỉnh cô lập 
b là kề với c và c là kề với b 
Cạnh (a,b) là liên thuộcvới hai đỉnh a và b 
g 
deg(g) = 1 
g là đỉnh treo 
( G ) = min {deg( v ): v V } = 0, 
 ( G ) = max {deg( v ): v V }= 3. 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
35 
Định lý về các cái bắt tay (Handshaking Theorem) 
Định lý. Giả sử G là đồ thị vô hướng (đơn hoặc đa) với tập đỉnh V và tập cạnh E . Khi đó 
 CM: Trong tổng ở vế trái mỗi cạnh e =( u,v ) E được tính hai lần: trong deg( u ) và deg( v ). 
Hệ quả: Trong một đồ thị vô hướng bất kỳ, số lượng đỉnh bậc lẻ (đỉnh có bậc là số lẻ) bao giờ cũng là số chẵn. 
32 
Ví dụ.  Biết rằng mỗi đỉnh của đồ thị vô hướng G =( V,E ) với 14 đỉnh và 25 cạnh đều có bậc là 3 hoặc 5. 
 Hỏi G có bao nhiêu đỉnh bậc 3? 
Giải. Giả sử G có x đỉnh bậc 3. 
 Khi đó có 14 - x đỉnh bậc 5. 
 Do | E | = 25, nên tổng tất cả các bậc là 50. 
 Từ đó, 3 x + 5(14 - x ) = 50 
 Suy ra x = 10. 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
37 
Bậc của đỉnh của đồ thị có hướng 
Cho G là đồ thị có hướng, v là đỉnh của G . 
Bán bậc vào ( in-degree ) của v , deg ( v ) , là số cạnh đi vào v . 
Bán bậc ra ( out-degree ) của v , deg ( v ) , là số cạnh đi ra khỏi v . 
Bậc của v , deg( v ): deg ( v )+ deg ( v ) , là tổng của bán bậc vào và bán bậc ra của v . 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
38 
Ví dụ 
f 
a 
b 
c 
e 
d 
deg - (d) = 2 
deg + (d)= 1 
deg-(f) = 0 
deg+(f)= 0 
b kề tới c và c kề từ b 
deg-(a) = 0 
deg+(a)= 2 
a- đỉnh nguồn 
deg-(e) = 2 
deg+(e)= 0 
e – đỉnh đích (target) 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
39 
Định lý về các cái bắt tay có hướng  Directed Handshaking Theorem 
Định lý. Giả sử G là đồ thị có hướng (có thể là đơn hoặc đa) với tập đỉnh V và tập cạnh E . Khi đó: 
Chú ý là khái niệm bậc của đỉnh là không thay đổi cho dù ta xét đồ thị vô hướng hay có hướng. 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
40 
Chương 1  CÁC KHÁI NIỆM CƠ BẢN 
1.1. Đồ thị trong thực tế 
1.2. Các loại đồ thị 
1.3. Bậc của đỉnh 
1.4. Đồ thị con 
1.5. Đồ thị đẳng cấu 
1.6. Đường đi và chu trình 
1.7. Tính liên thông 
1.8. Một số loại đồ thị đặc biệt 
1.9. Tô màu đồ thị 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
41 
Đồ thị con (Subgraphs) 
Định nghĩa. Đồ thị H =( W , F ) được gọi là đồ thị con của đồ thị G =( V , E ) nếu W  V và F  E . 
Ký hiệu: H  G. 
G 
H 
Ví dụ 
Definition. A graph H is a subgraph of a graph G if  V ( H )  V ( G ) and E ( H )  E ( G ) (denote H  G ). 
G 
u 
v 
w 
x 
y 
H 
v 
w 
x 
y 
 G 
 G 
v 
w 
x 
y 
F 
Ví dụ 
Định nghĩa. Cho G = ( V, E ) là đồ thị vô hướng. 
 Giả sử S  V , S . Đồ thị con cảm sinh bởi S là đồ thị con cực đại của G với tập đỉnh là S . (thường ký hiệu là ) 
 Đồ thị con H của đồ thị G được gọi là đồ thị con cảm sinh đỉnh ( vertex-induced subgraph) của G nếu tìm được S  V sao cho H = . 
Ví dụ: 
Đồ thị con cảm sinh Induced Subgraph 
G 
u 
v 
w 
x 
y 
H không là đồ thị con cảm sinh của G . 
v 
w 
x 
y 
H 
H ∪ {( x,w )} đúng 
Loại bỏ đỉnh The deletion of vertices 
Định nghĩa. Cho G = ( V, E ) là đồ thị vô hướng. Giả sử S  V . Ta gọi việc loại bỏ tập đỉnh S khỏi đồ thị là việc loại bỏ tất cả các đỉnh trong S cùng các cạnh kề với chúng. 
Như vậy nếu ký hiệu đồ thị thu được là G - S, ta có G - S = . 
 Nếu S ={ v }, thì để đơn giản ta viết G - v . 
G 
u 
v 
w 
x 
y 
Giả sử S= { x,u } 
G - S 
u 
v 
w 
x 
y 
Định nghĩa. Cho G = ( V, E ) là đồ thị vô hướng. 
 Giả sử X  E, X . Đồ thị con cảm sinh bởi X là đồ thị con nhỏ nhất của G với tập cạnh là X . (ký hiệu bởi ) 
 Đồ thị con H của G được gọi là đồ thị con cảm sinh cạnh ( edge-induced subgraph) nếu H = đối với một tập con nào đó X  E . 
Ví dụ: 
Đồ thị con cảm sinh cạnh Edge Induced Subgraph 
G 
u 
v 
w 
x 
y 
Cho X = {( u,v ),( v,w )} 
u 
v 
w 
Ví dụ. Cho G =( V,E ) là đồ thị vô hướng. 
 Nếu H =, thì có thể suy ra H = được không? 
No 
G 
u 
v 
w 
H 
v 
w 
Đồ thị con cảm sinh cạnh và cảm sinh đỉnh 
Dễ thấy, G = . 
Ví dụ trên cho thấy không nhất thiết trùng với G 
Định nghĩa.  Đồ thị con H  G được gọi là đồ thị con bao trùm của G nếu tập đỉnh của H là tập đỉnh của G : V ( H ) = V ( G ). 
Định nghĩa.  Ta viết H = G + {( u,v ), ( u,w )} hiểu là  E ( H ) = E ( G ) ∪ {( u,v ), ( u,w )}, trong đó ( u,v ), ( u,w ) E ( G ). 
Đồ thị con bao trùm Spanning Subgraph 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
48 
Hợp của hai đồ thị 
Hợp G 1  G 2 của hai đơn đồ thị G 1 =( V 1 , E 1 ) và G 2 =( V 2 , E 2 ) là đơn đồ thị ( V 1  V 2 , E 1  E 2 ) . 
a 
b 
c 
d 
e 
a 
b 
c 
d 
f 
 
49 
Hợp của các đồ thị 
 Nếu S 1 , S 2 , S 3 , S 4 , S 5 , S 6 là các hình vuông, khi đó Q 3 là hợp của các diện của nó: Q 3 = S 1  S 2  S 3  S 4  S 5  S 6 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
50 
Chương 1  CÁC KHÁI NIỆM CƠ BẢN 
1.1. Đồ thị trong thực tế 
1.2. Các loại đồ thị 
1.3. Bậc của đỉnh 
1.4. Đồ thị con 
1.5. Đồ thị đẳng cấu 
1.6.  ... time = time+1; 
 f[u] = time; 
end; 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
230 
Phân tích thuật toán DFS 
Mỗi đỉnh được thăm đúng 1 lần, việc thăm mỗi đỉnh đòi hỏi chi phí thời gian O (1), suy ra thao tác thăm đỉnh đòi hỏi thời gian O (| V |). 
Vòng lặp trong DFS(u) thực hiện việc duyệt cạnh của đồ thị 
Mỗi cạnh được duyệt qua đúng một lần nếu đồ thị là có hướng và 2 lần nếu đồ thị là vô hướng 
Như vậy tổng số lần lặp là O (| E| ). 
Vậy, thuật toán có thời gian O (| V|+|E| ) 
Đối với đồ thị, thuật toán có đánh giá như vậy gọi là thuật toán thời gian tuyến tính 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
231 
Ví dụ: DFS 
Đỉnh xuất phát tìm kiếm (Source vertex) 
a 
d 
e 
h 
g 
f 
c 
b 
Để hoạt động của thuật toán là xác định, giả thiết rằng ta duyệt các đỉnh trong danh sách kề của một đỉnh theo thứ tự từ điển 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
232 
Ví dụ: DFS 
1 | 
 | 
 | 
 | 
 | 
 | 
 | 
 | 
sourcevertex 
d [ v ] f [ v ] 
a 
b 
f 
e 
h 
g 
d 
c 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
233 
Ví dụ: DFS 
1 | 
 | 
 | 
 | 
 | 
 | 
2 | 
 | 
sourcevertex 
a 
g 
f 
e 
h 
d 
c 
b 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
234 
Ví dụ: DFS 
1 | 
 | 
 | 
 | 
 | 
3 | 
2 | 
 | 
sourcevertex 
a 
g 
h 
f 
d 
e 
c 
b 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
235 
Ví dụ: DFS 
1 | 
 | 
 | 
 | 
 | 
3 | 4 
2 | 
 | 
sourcevertex 
a 
h 
g 
f 
e 
d 
c 
b 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
236 
Ví dụ: DFS 
1 | 
 | 
 | 
 | 
5 | 
3 | 4 
2 | 
 | 
sourcevertex 
a 
h 
g 
f 
e 
d 
c 
b 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
237 
Ví dụ: DFS 
1 | 
 | 
 | 
 | 
5 | 6 
3 | 4 
2 | 
 | 
sourcevertex 
a 
g 
f 
e 
h 
d 
c 
b 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
238 
Ví dụ: DFS 
1 | 
8 | 
 | 
 | 
5 | 6 
3 | 4 
2 | 7 
 | 
sourcevertex 
a 
h 
f 
g 
e 
d 
b 
c 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
239 
Ví dụ: DFS 
1 | 
8 | 
 | 
 | 
5 | 6 
3 | 4 
2 | 7 
 | 
sourcevertex 
a 
g 
f 
e 
h 
d 
c 
b 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
240 
Ví dụ: DFS 
1 | 
8 | 
 | 
 | 
5 | 6 
3 | 4 
2 | 7 
9 | 
sourcevertex 
c 
a 
b 
g 
h 
f 
d 
e 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
241 
Ví dụ: DFS 
1 | 
8 | 
 | 
 | 
5 | 6 
3 | 4 
2 | 7 
9 |10 
sourcevertex 
a 
f 
b 
c 
d 
e 
g 
h 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
242 
Ví dụ: DFS 
1 | 
8 |11 
 | 
 | 
5 | 6 
3 | 4 
2 | 7 
9 |10 
sourcevertex 
a 
b 
e 
c 
f 
d 
h 
g 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
243 
Ví dụ: DFS 
1 |12 
8 |11 
 | 
 | 
5 | 6 
3 | 4 
2 | 7 
9 |10 
sourcevertex 
a 
c 
b 
d 
e 
g 
f 
h 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
244 
Ví dụ: DFS 
1 |12 
8 |11 
13| 
 | 
5 | 6 
3 | 4 
2 | 7 
9 |10 
sourcevertex 
a 
e 
b 
c 
g 
d 
h 
f 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
245 
Ví dụ: DFS 
1 |12 
8 |11 
13| 
14| 
5 | 6 
3 | 4 
2 | 7 
9 |10 
sourcevertex 
a 
e 
b 
g 
d 
c 
h 
f 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
246 
Ví dụ: DFS 
1 |12 
8 |11 
13| 
14|15 
5 | 6 
3 | 4 
2 | 7 
9 |10 
sourcevertex 
a 
e 
b 
d 
c 
g 
f 
h 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
247 
Ví dụ: DFS 
1 |12 
8 |11 
13|16 
14|15 
5 | 6 
3 | 4 
2 | 7 
9 |10 
sourcevertex 
a 
e 
b 
d 
c 
g 
f 
h 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
248 
DFS: Các loại cạnh 
DFS(G) sinh ra một cách phân loại các cạnh của đồ thị đã cho: 
Cạnh của cây ( Tree edge ) : là cạnh mà theo đó từ một đỉnh ta đến thăm một đỉnh mới (cạnh đi vào đỉnh trắng) 
Các cạnh này tạo thành một rừng gọi là rừng tìm kiếm DFS . 
Các đỉnh được thăm khi thực hiện DFS(v) và các cạnh của cây tạo thành cây được gọi là cây DFS ( v ) 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
249 
Ví dụ: Rừng DFS 
1 |12 
8 |11 
13|16 
14|15 
5 | 6 
3 | 4 
2 | 7 
9 |10 
sourcevertex a 
Tree edges 
Cây DFS ( a ) 
sourcevertex g 
Cây DFS ( g ) 
a 
e 
d 
c 
g 
f 
h 
b 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
250 
DFS: Cạnh ngược 
DFS tạo ra một cách phân loại các cạnh của đồ thị đã cho: 
Cạnh của cây ( Tree edge ) : là cạnh mà theo đó từ một đỉnh ta đến thăm một đỉnh mới (cạnh đi vào đỉnh trắng) 
Cạnh ngược ( Back edge ) : đi từ con cháu (descendent) đến tổ tiên (ancestor) 
Đi vào đỉnh xám (đi từ đỉnh xám đến đỉnh xám) 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
251 
Ví dụ: DFS Cạnh ngược 
1 |12 
8 |11 
13|16 
14|15 
5 | 6 
3 | 4 
2 | 7 
9 |10 
sourcevertex 
Tree edges 
Back edges 
a 
d 
e 
c 
g 
f 
h 
b 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
252 
DFS: Cạnh tới 
DFS tạo ra một cách phân loại các cạnh của đồ thị đã cho: 
Cạnh của cây ( Tree edge ) : là cạnh mà theo đó từ một đỉnh ta đến thăm một đỉnh mới (cạnh đi vào đỉnh trắng) 
Cạnh ngược ( Back edge ) : đi từ con cháu (descendent) đến tổ tiên (ancestor) 
Cạnh tới ( Forward edge ) : đi từ tổ tiên đến con cháu 
Không là cạnh của cây 
Đi từ đỉnh xám đến đỉnh đen 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
253 
Ví dụ: DFS Cạnh tới 
1 |12 
8 |11 
13|16 
14|15 
5 | 6 
3 | 4 
2 | 7 
9 |10 
sourcevertex 
Tree edges 
Back edges 
Forward edges 
a 
d 
c 
g 
f 
h 
e 
b 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
254 
DFS: Cạnh vòng 
DFS tạo ra một cách phân loại các cạnh của đồ thị đã cho: 
Cạnh của cây ( Tree edge ) : là cạnh mà theo đó từ một đỉnh ta đến thăm một đỉnh mới (cạnh đi vào đỉnh trắng) 
Cạnh ngược ( Back edge ) : đi từ con cháu (descendent) đến tổ tiên (ancestor) 
Cạnh tới ( Forward edge ) : đi từ tổ tiên đến con cháu 
Cạnh vòng ( Cross edge ) : cạnh nối hai đỉnh không có quan hệ họ hàng 
Không là cạnh của cây, và giống như cạnh vòng cũng 
Đi từ đỉnh xám đến đỉnh đen 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
255 
Ví dụ: DFS Cạnh vòng 
1 |12 
8 |11 
13|16 
14|15 
5 | 6 
3 | 4 
2 | 7 
9 |10 
sourcevertex 
Tree edges 
Back edges 
Forward edges 
Cross edges 
a 
f 
d 
h 
g 
c 
e 
b 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
256 
DFS: Các loại cạnh 
DFS tạo ra một cách phân loại các cạnh của đồ thị đã cho: 
Tree edge : cạnh theo đó từ một đỉnh đến thăm đỉnh mới (trắng) 
Back edge : đi từ con cháu đến tổ tiên 
Forward edge : đi từ tổ tiên đến con cháu 
Cross edge : giữa hai đỉnh không có họ hàng 
Chú ý: Cạnh của cây & cạnh ngược là quan trọng; nhiều thuật toán không đòi hỏi phân biệt cạnh tới và cạnh vòng 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
257 
DFS: Các loại cạnh 
Định lý: Nếu G là đồ thị vô hướng, thì DFS chỉ sản sinh ra cạnh của cây và cạnh ngược. 
Chứng minh bằng phản chứng: 
Giả sử có cạnh tới (forward edge) 
Nhưng khi đó F phải là cạnh ngược (back edge)?! 
sourc e 
F? 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
258 
DFS: Các loại cạnh 
Giả sử có cạnh vòng (cross edge) 
Khi đó C không thể là cạnh vòng bởi vì: 
Nó phải được khảo sát từ một trong hai đỉnh đầu mút và trở thành cạnh của cây trước khi đỉnh kia được khảo sát 
Do đó bức tranh bên là không đúngcả hai cạnh bên không thể là cạnh của cây 
source 
C? 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
259 
DFS: Phân biệt các loại cạnh 
Dễ dàng phân biệt các loại cạnh nhê ph©n tÝch mµu cña c¸c ®Ønh vµ/hoÆc xÐt c¸c gi¸ trÞ cña c¸c mèc thêi gian d vµ f . 
Khi ta duyệt cạnh e =( u, v ) từ đỉnh u , căn cứ vào màu của v ta có thể biết cạnh này thuộc loại cạnh nào: 
1. WHITE cho biết e là cạnh của cây 
2. GRAY cho biết e là cạnh ngược 
BLACK cho biết e là cạnh tới hoặc vòng 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
260 
Phân tích DFS 
(* Main Program*) 
1. for u V do 
2. color [ u ]  white 
3. [ u ]  NIL 
4. time  0 
5. for u V do 
6. if color [ u ] = white 
7. then DFS-Visit( u ) 
Các biến time, color , là toàn cục . 
DFS-Visit( u ) 
color [ u ]  GRAY (* Thăm đỉnh u *) 
time  time + 1 
 d [ u ]  time 
 for each v Adj [ u ] do 
 if color [ v ] = WHITE 
 then [ v ]  u 
 DFS-Visit( v ) 
 color [ u ]  BLACK (* Đỉnh u đã duyệt xong *) 
 f [ u ]  time  time + 1 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
261 
Phân tích DFS 
Vòng lặp trên các dòng 1-2 và 5-7 đòi hỏi thời gian  (| V| ) , chưa tính thời gian thực hiện lệnh DFS(v). 
DFS(v) thực hiện đối với mỗi đỉnh trắng v V và ngay sau khi được thăm nó được tô màu xám. Các dòng 3-6 của DFS(v) sẽ thực hiện |Adj[ v ]| lần. Vậy thời gian tổng cộng của DFS(v) là  v V |Adj[ v ]| =  (| E| ) 
Do đó thời gian của DFS là  (| V|+|E| ) . 
Thuật toán trên đồ thị có đánh giá thời gian như trên gọi là thuật toán thời gian tuyến tính 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
262 
CÁC ỨNG DỤNG CỦA DFS 
Tính liên thông của đồ thị 
Tìm đường đi từ s đến t 
 Phát hiện chu trình 
 Kiểm tra tính liên thông mạnh 
 Định hướng đồ thị 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
263 
Bài toán về tính liên thông 
Bài toán: Cho đồ thị vô hướng G = ( V,E ). Hỏi đồ thị gồm bao nhiêu thành phần liên thông, và từng thành phần liên thông gồm các đỉnh nào? 
Giải: Sử dụng DFS (BFS) : 
Mỗi lần gọi đến DFS (BFS) ở trong chương trình chính sẽ sinh ra một thành phần liên thông 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
264 
DFS giải bài toán liên thông 
(* Main Program*) 
1. for u V do 
2. id [ u ]  0 
3. cnt  0 (* cnt – số lượng tplt *) 
4. for u V do 
5. if id [ u ] = 0 
 then cnt  cnt +1 
 DFS-Visit( u ) 
DFS-Visit( u ) 
id [ u ]  cnt 
 for each v Adj [ u ] do 
 if id [ v ] = 0 
 then DFS-Visit( v ) 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
265 
Tìm đường đi 
Bài toán tìm đường đi 
Input: Đồ thị G = ( V,E ) xác định bởi danh sách kề và hai đỉnh s, t . 
Đầu ra: Đường đi từ đỉnh s đến đỉnh t , hoặc khẳng định không tồn tại đường đi từ s đến t . 
Thuật toán: Thực hiện DFS(s) (hoặc BFS(s)). 
Nếu [t] = NIL thì không có đường đi, trái lại ta có đường đi 
 t [t] [ [ t]] . . . s 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
266 
DFS giải bài toán đường đi 
(* Main Program*) 
1. for u V do 
2. color [ u ]  white 
3. [ u ]  NIL 
4. DFS-Visit( s ) 
DFS-Visit( u ) 
color [ u ]  GRAY (* Thăm đỉnh u *) 
for each v Adj [ u ] do 
 if color [ v ] = WHITE 
 then [ v ]  u 
 DFS-Visit( v ) 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
267 
DFS và Chu trình 
Bài toán: Cho đồ thị G =( V,E ). Hỏi G có chứa chu trình hay không? 
Định lý: Đồ thị G là không chứa chu trình khi và chỉ khi trong quá trình thực hiện DFS ta không phát hiện ra cạnh ngược . 
Chứng minh: 
Nếu G không chứa chu trình thì rõ ràng không có cạnh ngược (bởi vì sự tồn tại cạnh ngược dẫn đến phát hiện chu trình) 
Nếu không có cạnh ngược thì G là không chứa chu trình (acyclic). Thực vậy 
Không có cạnh ngược tức là chỉ có cạnh của cây 
Nếu chỉ có cạnh của cây thì G chỉ là cây hoặc rừng 
Vậy G không chứa chu trinh 
Như vậy DFS có thể áp dụng để giải bài toán đặt ra. 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
268 
DFS và chu trình 
(* Main Program*) 
1. for u V do 
2. color [ u ]  white 
3. [ u ]  NIL 
4. time  0 
5. for u V do 
6. if color [ u ] = white 
7. then DFS-Visit( u ) 
DFS( u ) 
color [ u ]  GRAY (* Thăm đỉnh u *) 
time  time + 1 
 d [ u ]  time 
 for each v Adj [ u ] do 
 if color [ v ] = WHITE 
 then [ v ]  u 
 DFS-Visit( v ) 
 color [ u ]  BLACK (* Đỉnh u đã duyệt xong *) 
 f [ u ]  time  time + 1 
Cần phải điều chỉnh như thế nào để phát hiện chu trình? 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
269 
DFS và chu trình 
Câu hỏi: Thời gian tính là bao nhiêu? 
Trả lời: Chính là thời gian thực hiện DFS : O (| V|+|E |). 
Câu hỏi: Nếu G là đồ thị vô hướng thì có thể đánh giá thời gian tính sát hơn nữa được không? 
Trả lời: Thuật toán có thời gian tính O (| V| ), bởi vì: 
Trong một rừng (đồ thị không chứa chu trình) | E | | V | - 1 
Vì vậy nếu đồ thị có | V | cạnh thì chắc chắn nó chứa chu trình, và thuật toán kết thúc. 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
270 
Kiểm tra tính liên thông mạnh 
Bài toán: Hỏi đồ thị có hướng G có là liên thông mạnh? 
Mệnh đề: Đồ thị có hướng G= ( V,E ) là liên thông mạnh khi và chỉ khi luôn tìm được đường đi từ một đỉnh v đến tất cả các đỉnh còn lại và luôn tìm được đường đi từ tất cả các đỉnh thuộc V \ { v } đến v. 
Chứng minh: Hiển nhiên 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
271 
Thuật toán kiểm tra tính liên thông mạnh 
Thuật toán. 
Chän v V lµ mét ®Ønh tuú ý 
Thùc hiÖn DFS( v ) trªn G . NÕu tån t¹i ®Ønh u kh«ng ®­îc th¨m th× G kh«ng liªn th«ng m¹nh vµ thuËt to¸n kÕt thóc. Tr¸i l¹i thùc hiÖn tiÕp 
Thùc hiÖn DFS( v ) trªn G T = ( V, E T ), víi E T thu ®­îc tõ E bëi viÖc ®¶o ng­îc h­íng c¸c cung. NÕu tån t¹i ®Ønh u kh«ng ®­îc th¨m th× G kh«ng liªn th«ng m¹nh, nÕu tr¸i l¹i G lµ liªn th«ng m¹nh. 
Thời gian tính: O (| V |+| E |) 
c 
a 
d 
e 
b 
f 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
272 
Thuật toán kiểm tra tính liên thông mạnh 
 Đồ thị G Đồ thị G T 
c 
a 
d 
e 
b 
f 
c 
a 
d 
e 
b 
f 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
273 
Định hướng đồ thị 
Bµi to¸n: Cho ®å thÞ v« h­íng liªn th«ng G = ( V, E ). H·y t×m c¸ch ®Þnh h­íng c¸c c¹nh cña nã ®Ó thu ®­îc ®å thÞ cã h­íng liªn th«ng m¹nh hoÆc tr¶ lêi G lµ kh«ng ®Þnh h­íng ®­îc. 
ThuËt to¸n ®Þnh h­íng  : Trong qu¸ tr×nh thùc hiÖn DFS(G) ®Þnh h­íng c¸c c¹nh cña c©y DFS theo chiÒu tõ tæ tiªn ®Õn con ch¸u, c¸c c¹nh ng­îc theo h­íng tõ con ch¸u ®Õn tæ tiªn. Ký hiÖu ®å thÞ thu ®­îc lµ G ( ) 
Bæ ®Ò. G lµ ®Þnh h­íng ®­îc khi vµ chØ khi G ( ) lµ liªn th«ng m¹nh. 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
274 
Ví dụ: Định hướng đồ thị 
 Đồ thị G Đồ thị G (  ) 
c 
a 
d 
e 
b 
f 
c 
a 
d 
e 
b 
f 
a 
Phần 2. LÝ THUYẾT ĐỒ THỊ 
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 
275 
Questions?