Toán rời rạc - Chương 5: Các khái niệm cơ bản của lý thuyết đồ thị

 CHƯƠNG 5: CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ 
PHẦN 1: 
 Các khái niệm cơ bản 
 Biểu diễn đồ thị 
 Một số đồ thị đặc biệt 
 Sự đẳng cấu của các đồ thị 
 Đồ thị có hướng 
 Đường đi và chu trình 
 Sự liên thông 
1 
Các khái niệm cơ bản 
Đồ thị (Graph) 
G = ( V , E ) với V ≠  
V : tập các đỉnh 
E : tập các cạnh 
Cạnh e E 
ứng với 2 đỉnh v , w V 
v , w là 2 đỉnh kề (hay liên kết) với nhau, e liên thuộc với v và w 
Ký hiệu: e = vw () 
v  w : e được gọi là vòng (khuyên) tại v 
2 
Các khái niệm cơ bản 
Đồ thị (Graph) 
Cạnh bội (song song) 
Hai cạnh phân biệt cùng tương ứng với một cặp đỉnh 
Đơn đồ thị 
Đồ thị không có vòng và cạnh song song 
Đa đồ thị 
Các đồ thị không phải là đơn đồ thị 
3 
Các khái niệm cơ bản 
Đồ thị (Graph) 
Đồ thị đầy đủ 
Đồ thị mà mọi cặp đỉnh đều kề nhau 
K n : đơn đồ thị đầy đủ 
Đồ thị con 
Đồ thị G ’ = ( V ’, E ’) 
V ’  V , E’  E 
Đồ thị hữu hạn 
E và V hữu hạn 
Đồ thị vô hạn 
4 
Biểu diễn đồ thị 
Biểu diễn hình học 
Mỗi đỉnh  một điểm 
Mỗi cạnh  một đường (cong hoặc thẳng) nối 2 đỉnh liên thuộc với nó 
Biểu diễn bằng ma trận 
Thường được dùng để biểu diễn trên máy tính 
2 cách biểu diễn thường dùng 
Ma trận kề 
Ma trận liên thuộc 
5 
Biểu diễn đồ thị 
Biểu diễn bằng ma trận 
Ma trận kề 
Ma trận vuông cấp n (số đỉnh của đồ thị) 
Các phần tử được xác định bởi 
 : Nếu là một cạnh của G 
 : Nếu không là một cạnh của G 
Tính chất 
Phụ thuộc vào thứ tự liệt kê của các đỉnh 
Ma trận là đối xứng 
Một vòng được tính là một cạnh ( a kk = 1) 
6 
Biểu diễn đồ thị 
Biểu diễn bằng ma trận 
Ma trận kề 
Ví dụ 1 
7 
Biểu diễn đồ thị 
Biểu diễn bằng ma trận 
Ma trận kề 
Ví dụ 2 
8 
Biểu diễn đồ thị 
Biểu diễn bằng ma trận 
Ma trận liên thuộc 
Ma trận M = ( ) nxm 
Các phần tử được xác định bởi 
 : Nếu cạnh liên thuộc với v i của G 
: : Nếu cạnh không liên thuộc với v i của G 
Tính chất 
Các cột tương ứng với các cạnh bội là giống nhau trong ma trân liên thuộc 
Các vòng ứng với một cột có đúng một phần tử bằng 1 ứng với đỉnh nối với vòng đó. 
9 
Biểu diễn đồ thị 
Biểu diễn bằng ma trận 
Ma liên thuộc 
Ví dụ 
10 
Biểu diễn đồ thị 
Biểu diễn bằng bảng (danh sách liền kề) 
Lưu trữ các đỉnh liền kề với một đỉnh 
Ví dụ 
Đỉnh 
Đỉnh liền kề 
a 
b, c, e 
b 
a 
c 
a, c, d, e 
d 
c, e 
e 
a, c, d 
11 
Các khái niệm cơ bản 
Bậc của đỉnh 
Đỉnh của đồ thị G có bậc là n nếu nó kề với n đỉnh khác. 
Ký hiệu: deg ( v ) hay d ( v ) 
Mỗi vòng được kể là 2 cạnh tới một đỉnh 
Đỉnh cô lập  deg ( v )=0 
Đỉnh treo  deg ( v )=1 
Cạnh treo có đầu mút là một đỉnh treo 
Đồ thị rỗng: deg ( v )=0  v 
12 
Các khái niệm cơ bản 
Bậc của đỉnh 
Định lý 1.1 
Trong mọi đồ thị G = (V, E), tổng số bậc của các đỉnh của G bằng 2 lần số cạnh của nó 
Hệ quả 
Trong mọi đồ thị G = (V, E) ta có 
Số đỉnh bậc lẻ là một số chẵn 
Tổng bậc của đỉnh bậc lẻ là một số chẵn 
13 
Các khái niệm cơ bản 
Bậc của đỉnh 
Định lý 1.2 
Trong mọi đơn đồ thị G = (V, E), nếu số đỉnh nhiều hơn 1 thì tồn tại ít nhất hai đỉnh cùng bậc. 
Định lý 1.3 
Trong mọi đơn đồ thị G = (V, E), nếu số đỉnh nhiều hơn 2 và có đúng hai đỉnh cùng bậc thì hai đỉnh này không đồng thời có bậc bằng 0 hoặc n-1. 
14 
Các khái niệm cơ bản 
Chứng minh và giải toán bằng phương pháp đồ thị 
Xây dựng đồ thị mô tả đầy đủ thông tin của bài toán 
Mỗi đỉnh v V  một đối tượng trong bài toán 
Mỗi cạnh e E  mối quan hệ giữa hai đối tượng 
Vẽ đồ thị mô tả bài toán 
Sử dụng các định nghĩa, tính chất, định lý,  suy ra điều cần phải chứng minh 
15 
Các khái niệm cơ bản 
Một số bài toán ví dụ 
Chứng minh rằng trong một cuộc họp tùy ý có ít 
nhất 2 đại biểu tham gia trở lên, luôn có ít nhất hai 
đại biểu mà họ có số người quen bằng nhau trong 
các đại biểu đến dự họp. 
16 
Các khái niệm cơ bản 
Một số bài toán ví dụ 
Chứng minh rằng số người mà mỗi người đã có một 
số lẻ lần bắt tay nhau trên trái đất là một con số 
chẵn. 
17 
Một số đồ thị đặc biệt 
Đồ thị đầy đủ K n 
Đơn đồ thị 
Số đỉnh: 	| V | = n 
Bậc: deg ( v ) = n – 1,  v V 
Số cạnh:	 | E | = n(n - 1) / 2 
18 
Một số đồ thị đặc biệt 
Đồ thị vòng C n 
Đơn đồ thị 
Số đỉnh: 	| V | = n  3 
Bậc: deg ( v ) = 2,  v V 
Số cạnh:	 | E | = n 
19 
Một số đồ thị đặc biệt 
Đồ thị hình bánh xe W n 
Nối các đỉnh của C n với một đỉnh mới u ta được W n 
Số đỉnh: 	| V | = n + 1, n  3 
Bậc: deg ( v ) = 3,  v V \ {u};	 
 deg(u) = n 
Số cạnh:	 | E | = 2 n 
20 
Một số đồ thị đặc biệt 
Đồ thị đều bậc k (Đồ thị k-đều) 
Mọi đỉnh đều có cùng bậc k 
Số đỉnh: 	| V | = n 
Bậc: deg ( v ) = k,  v V 
Số cạnh:	 | E | = n.k/2 
21 
Ví dụ: 
C n là đồ thị đều bậc 2 
K n là đồ thị đều bậc (n-1) 
Một số đồ thị đặc biệt 
22 
Các khối n -lập phương Q n 
Có đỉnh, mỗi đỉnh được biểu diễn bằng một dãy số nhị phân với độ dài n. 
Hai đỉnh là liền kề nếu và chỉ nếu các dãy nhị phân biểu diễn chúng chỉ khác nhau đúng 1 bit. 
Số đỉnh: 	| V | = 
Bậc: deg ( v ) = n,  v V 
Số cạnh:	 | E | = n. 
Một số đồ thị đặc biệt 
23 
Đồ thị bù 
Hai đơn đồ thị G và G’ được gọi là bù nhau 
chúng có chung các đỉnh 
Cạnh nào thuộc G thì không thuộc G’ và ngược lại 
Ký hiệu: G’ = 
Một số đồ thị đặc biệt 
Đồ thị lưỡng phân 
Một đồ thị G được gọi là đồ thị lưỡng phân nếu tập các đỉnh của G có thể phân thành 2 tập hợp không rỗng, rời nhau sao cho mỗi cạnh của G nối một đỉnh thuộc tập này đến một đỉnh thuộc tập kia. 
Ký hiệu: K m,n 
24 
Sự đẳng cấu giữa các đồ thị 
Định nghĩa 
G ( V , E ) đẳng cầu với G’(V’, E’) , ( G  G’ ) nếu 
Tồn tại song ánh f: V V’ 
Bảo toàn quan hệ liền kề: 
u, v V, uv E  f( u)f(v ) E’ 
G đẳng cấu với G’ thì 
|V| = |V’| 
|E| = |E’| 
deg( v ) = deg( f ( v )),  v V 
25 
Sự đẳng cấu giữa các đồ thị 
Định nghĩa 
Chứng minh 2 đồ thị đẳng cấu 
Điều kiện cần 
Xét số cạnh, số đỉnh, bậc của đỉnh 
Điều kiện đủ 
Xây dựng song ánh bảo toàn quan hệ liền kề 
Ví dụ 1: 
26 
Sự đẳng cấu giữa các đồ thị 
Định nghĩa 
Chứng minh 2 đồ thị đẳng cấu 
Ví dụ 2 
27 
Sự đẳng cấu giữa các đồ thị 
Đồ thị tự bù 
Định nghĩa 
Đồ thị G tự bù nếu G đẳng cấu với phần bù của nó 
Ví dụ 
Định lý 1.4 
Hai đồ thị có ma trận liền kề (theo một thứ tự nào đó của các đỉnh) bằng nhau thì đẳng cấu với nhau 
28 
Đồ thị có hướng 
29 
Định nghĩa 
G = (V, E) 
Tập đỉnh V 
Tập cạnh (cung) E = { (a, b) | a,b V } 
e = (a, b) E 
Ký hiệu: e = 
e có hướng từ a đến b 
a: đỉnh đầu;	b: đỉnh cuối 
e là khuyên (vòng) ab 
G được gọi là đầy đủ nếu đồ thị vô hướng của nó là đầy đủ 
Đồ thị có hướng 
Bậc của đỉnh 
Bậc vào 
deg - (v) = | { u | (u, v) E } | = số cạnh có đỉnh cuối là v 
Bậc ra 
deg + (v) = | { u | (v, u) E } | = số cạnh có đỉnh đầu là v 
30 
Chú ý: Một khuyên (vòng) tại một đỉnh sẽ góp thêm một đơn vị vào bậc vào và bậc ra của đỉnh này. 
Đồ thị có hướng 
Bậc của đỉnh 
Định lý 1.5 
Tổng bậc vào của các đỉnh bằng tổng bậc ra và bằng số cạnh của đồ thị 
Đồ thị cân bằng 
31 
Đồ thị có hướng 
Bậc của đỉnh 
Ví dụ 
Có một nhóm gồm 9 đội bóng bàn thi đấu vòng tròn một lượt. 
Hỏi sau khi có kết quả thi đấu của tất cả các đội có thể có trường hợp bất kỳ đội nào trong 09 đội này cũng đều thắng đúng 05 đội khác trong nhóm được không? 
 (Lưu ý trong thi bóng bàn không có trận hòa) 
32 
33 
Đường đi và chu trình 
Đường đi 
Định nghĩa 
Đường đi có độ dài n từ v 0 đến v n với n là một số nguyên dương là một dãy các cạnh liên tiếp v 0 v 1 , v 1 v 2 , , v n-1 v n 
v 0 : đỉnh đầu; v n : đỉnh cuối 
Ký hiệu: v 0 v 1 v 2  v n-1 v n 
 đường đi v 0 - v n 
34 
Đường đi và chu trình 
Đường đi 
Định nghĩa 
Đường đi đơn giản (đường đi đơn) 
Đường đi không qua cạnh nào quá một lần 
Đường đi sơ cấp 
Đường đi không qua đỉnh nào quá một lần 
Đường đi sơ cấp Đường đi đơn giản 
35 
Đường đi và chu trình 
Chu trình 
Định nghĩa 
Chu trình 
đường đi khép kín ( v 0 v 1 v 2  v n-1 v n v 0 ) 
độ dài ít nhất là 3 
Chu trình đơn giản 
Chu trình không đi qua cạnh nào quá 1 lần 
Chu trình sơ cấp 
Chu trình không đi qua đỉnh nào quá 1 lần (trừ đỉnh đầu, đỉnh cuối) 
36 
Đường đi và chu trình 
Chu trình 
Định lý 1.6 
G = (V, E) là một đồ thị vô hướng 
Số đỉnh lớn hơn hoặc bằng 3 
Bậc của mọi đỉnh đều lớn hơn hoặc bằng 2 
thì trong G luôn tồn tại một chu trình sơ cấp 
Định lý 1.7 
G = (V, E) là một đồ thị vô hướng 
Số đỉnh lớn hơn hoặc bằng 4 
Bậc của mọi đỉnh đều lớn hơn hoặc bằng 3 
thì trong G luôn tồn tại một chu trình sơ cấp có độ dài chẵn 
37 
Tính liên thông 
Tính liên thông trong đồ thị vô hướng 
Định nghĩa 
Hai đỉnh v, u trong đồ thị G được gọi là liên thông nếu tồn tại một đường đi nối chúng với nhau. 
Đồ thị G gọi là liên thông nếu hai đỉnh phân biệt bất kỳ trong đồ thị đều liên thông. Ngược lại thì ta gọi là đồ thị không liên thông. 
38 
Tính liên thông 
Tính liên thông trong đồ thị vô hướng 
Định nghĩa 
Cho G = (V,E), v V . 
V’ là tập con của V gồm đỉnh v và tất cả các đỉnh liên thông với v trong G. 
E’ là tập con của E gồm tất cả các cạnh nối các đỉnh thuộc V’. 
Khi đó G’ = (V’, E’) gọi là thành phần liên thông của G chứa v. 
Chú ý : Nếu v và u liên thông trong G thì thành phần liên thông 	 của G chứa v cũng là thành phần liên thông của G chứa u. 
39 
Tính liên thông 
Tính liên thông trong đồ thị vô hướng 
Định lý 1.8 
Đồ thị G=(V, E) là liên thông khi và chỉ khi G có duy nhất một thành phần liên thông. 
 (Sv tự chứng minh) 
40 
Tính liên thông 
Tính liên thông trong đồ thị vô hướng 
Đỉnh cắt và cầu 
u là đỉnh cắt (điểm khớp) số thành phần liên thông tăng lên nếu bỏ u và các cạnh liên thuộc với nó. 
e là cầu số thành phần liên thông tăng lên nếu bỏ cạnh e. 
41 
Tính liên thông 
Tính liên thông trong đồ thị vô hướng 
Định lý 1.9: 
Đơn đồ thị G = ( V , E ) có 
| V | = n 2 
deg( u ) + deg( v ) n,  u,v V 
thì G là đồ thị liên thông 
Hệ quả: 
Đơn đồ thị G = ( V , E ), | V | = n có 
 deg( v ) n/2,  v V 
thì G là đồ thị liên thông 
42 
Tính liên thông 
Tính liên thông trong đồ thị có hướng 
Liên thông mạnh 
Đồ thị có hướng G được gọi là liên thông mạnh nếu giữa 2 đỉnh u,v bất kỳ trong G luôn có đường đi từ v đến u và từ u đến v. 
Liên thông yếu 
Đồ thị có hướng G được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng của nó là liên thông 
43 
Tính liên thông 
Tính liên thông trong đồ thị có hướng 
Định lý 1.10 
Nếu đồ thị G có đúng 2 đỉnh bậc lẻ thì 2 đỉnh này phải liên thông với nhau 
Định lý 1.11 
Đồ thị G là một đồ thị lưỡng phân khi và chỉ khi mọi chu trình của nó đều có độ dài chẵn 
44 
Một số phép biến đổi đồ thị 
Hợp của 2 đồ thị 
G = (V, E) 
G’ = (V’, E’) 
G’’ = G  G’ = (V’’, E’’) 
V’’ = V  V’ 
E’’ = E  E’ 
45 
Một số phép biến đổi đồ thị 
Phép phân chia sơ cấp 
Phép thay thế cạnh e = uv của G bởi một đỉnh mới w cùng với 2 cạnh uw và vw 
Đồng phôi 
G và G’ gọi là đồng phôi nếu chúng có thể nhận được từ cùng một đồ thị bằng một dãy các phép phân chia sơ cấp 
Hai đồ thị đồng phôi chưa chắc đẳng cấu với nhau