Bài giảng Toán rời rạc - Chương V: Đồ thị - Lê Văn Luyện

Nội dung text: Bài giảng Toán rời rạc - Chương V: Đồ thị - Lê Văn Luyện

1. LOGOChương V Lê Văn Luyện email: lvluyen@yahoo.com TỐN RỜI RẠC www.math.hcmus.edu.vn/~lvluyen/trr
2. Đồ thị Đồ thị b c a d e h k g
3. 1. Những khái niệm và tính chất cơ bản Định nghĩa đồ thị Định nghĩa 1. Đồ thị vơ hướng G = (V, E) gồm: i) V là tập hợp khác rỗng mà các phần tử của nĩ gọi là đỉnh (vertex) của G. ii) E là tập hợp gồm các cặp khơng sắp thứ tự của hai đỉnh. Mỗi phần tử của E được gọi là một cạnh (edge) của G. Ký hiệu uv. 3
4. 1. Những khái niệm và tính chất cơ bản b c a d e h k g 4
5. 1. Những khái niệm và tính chất cơ bản Chú ý  Ta nĩi cạnh uv nối u với v, cạnh uv kề với u,v.  Nếu uv E thì ta nĩi đỉnh u kề đỉnh v.  Hai cạnh nối cùng một cặp đỉnh gọi là hai cạnh song song.  Cạnh uu cĩ hai đầu mút trùng nhau gọi là một khuyên.  Định nghĩa 2. Đồ thị vơ hướng khơng cĩ cạnh song song và khơng cĩ khuyên gọi là đồ thị đơn vơ hướng. 5
6. b c a d e h k b g a b c d a d c 6
7. 7 1. Những khái niệm và tính chất cơ bản Detroit New York San Francisco Chicago Denver Washington Los Angeles
8. 8 1. Những khái niệm và tính chất cơ bản Detroit New York San Francisco Chicago Denver Washington Los Angeles
9. 9 1. Những khái niệm và tính chất cơ bản Detroit New York San Francisco Chicago Denver Washington Los Angeles
10. 1. Những khái niệm và tính chất cơ bản Định nghĩa 3 Đa đồ thị cĩ hướng G =(V,E) gồm: i) V là tập hợp khác rỗng mà các phần tử của nĩ gọi là đỉnh của G. ii) E là tập hợp gồm các cặp cĩ sắp thứ tự của hai đỉnh. Mỗi phần tử của E được gọi là một cung (cạnh) của G. Ký hiệu uv. Ta nĩi cung uv đi từ u đến v, cung uv kề với u,v 10
11. b b a a d c d c 11
12. 1. Những khái niệm và tính chất cơ bản Chú ý  Nếu uv là một cung thì ta nĩi: . Đỉnh u và v kề nhau. . Đỉnh u gọi là đỉnh đầu (gốc), đỉnh v là đỉnh cuối (ngọn) của cung uv. Đỉnh v là đỉnh sau của đỉnh u.  Hai cung cĩ cùng gốc và ngọn gọi là cung song song.  Cung cĩ điểm gốc và ngọn trùng nhau gọi là khuyên. 12
13. Detroit New York Chicago San Francisco Denver Washington Los Angeles
14. Detroit New York Chicago San Francisco Denver Washington Los Angeles
15. Những khái niệm và tính chất cơ bản Bậc của đỉnh Cho đồ thị vơ hướng G = (V,E). Bậc của đỉnh v, ký hiệu deg(v), là số cạnh kề với v, trong đĩ một khuyên tại một đỉnh được đếm hai lần cho bậc của đỉnh ấy. 16
16. Bậc đỉnh a: deg(a) = 2 a Bậc đỉnh b: deg(b) = 5 b c d Bậc đỉnh c: deg(c) = 3 Bậc đỉnh d: deg(d) = 2 17
17. a b c d e f Bậc của các đỉnh? 18
18. 1. Những khái niệm và tính chất cơ bản Cho đồ thị cĩ hướng G = (V, E), v V 1) deg-(v):= số cung cĩ đỉnh cuối là v, gọi là bậc vào của v. 2) deg +(v):= số cung cĩ đỉnh đầu là v,gọi là bậc ra của v 3) deg(v):= deg- (v) + deg+(v)  Đỉnh bậc 0 gọi là đỉnh cơ lập. Đỉnh bậc 1 gọi là đỉnh treo 19
19. a b Bậc đỉnh a: deg-(a)= 1 ; deg+(a)=1 Bậc đỉnh b: deg-(b)= 1 ; deg+(b)=3 c d e Bậc đỉnh c: deg-(c)= 1 ; deg+(c)=2 f Bậc đỉnh d: deg-(d)= 0 ; deg+(d)=0 Bậc đỉnh e: deg-(e)= 1 ; deg+(e)=0 Bậc đỉnh f: deg-(f)= 2 ; deg+(f)=0 21
20. 1. Những khái niệm và tính chất cơ bản Định lí Cho đồ thị G = (V,E), m là số cạnh (cung) 1) 2mv  deg( ) vV 2) Nếu G cĩ hướng thì: m deg ( v ) deg ( v ) v V v V 3) Số đỉnh bậc lẻ của đồ thị là số chẵn 22
21. Ví dụ Cho đồ thị G cĩ 14 cạnh, trong đĩ cĩ 3 đỉnh bậc 1, 2 đỉnh bậc 3, 2 đỉnh bậc 4, 1 đỉnh bậc 5, các đỉnh cịn lại cĩ bậc là 2. Hỏi G cĩ bao nhiêu đỉnh? Giải. Gọi x là số đỉnh bậc 2. Theo định lý giữa số cạnh và bậc, ta cĩ 3.1+2.3+2.4+1.5+2x=2.14 Suy ra x= 3. Vậy số đỉnh của G là 3+2+2+1+3=11 (đỉnh)
22. Ví dụ. Cho đồ thị G cĩ 13 cạnh, trong đĩ cĩ 3 đỉnh bậc 1, 4 đỉnh bậc 2, 1 đỉnh bậc 5, các đỉnh cịn lại cĩ bậc là 3 hoặc 4. Hỏi G cĩ bao nhiêu đỉnh bậc 3 và đỉnh bậc 4?
23. 2. Biểu diễn đồ thị bằng ma trận Ta sử dụng ma trận kề. Cho G = (V,E) với V={1,2, ,n}. Ma trận kề của G là ma trận A = (aij)n xác định như sau: aij = số cạnh (số cung) đi từ đỉnh i đến đỉnh j 25
24. 2. Biểu diễn đồ thị bằng ma trận Tìm ma trận kề a b c d a a 0 1 1 0 b b 1 0 1 1 c c 1 1 0 1 d d 0 1 1 0 26
25. 2. Biểu diễn đồ thị bằng ma trận Tìm ma trận kề a b c d e f b a 0 2 1 0 0 0 a b 2 0 1 0 1 1 c 1 1 0 0 0 1 c d e d 000000 e 0 1 0 0 2 0 f f 0 1 1 0 0 0 27
26. 3. Đẳng cấu Định nghĩa Cho hai đơn đồ thị G = (V,E) và G’= (V’,E’). Ta nĩi rằng G đẳng cấu G’, ký hiệu G  G’, nếu tồn tại song ánh f :V→ V’sao cho: uv là cạnh của G f(u)f(v) là cạnh của G’ 28
27. 3. Đẳng cấu Chú ý  Nếu G và G’ là các đơn đồ thị vơ hướng đẳng cấu qua ánh xạ f thì chúng cĩ:  Cùng số đỉnh  Cùng số cạnh  Cùng số đỉnh với bậc cho sẵn (vd: số đỉnh bậc 2 của G và G’ bằng nhau)  deg v = deg f(v) 29
28. 3. Đẳng cấu 30
29. Ví dụ Khơng cĩ đỉnh bậc 1 b deg(e) = 1 b a c a c d e e d Khơng đẳng cấu 31
30. b 2 a 1 3 d c 6 e 4 5 f Đẳng cấu 32
31. a 2 b 1 4 5 d e 3 c Khơng đẳng cấu 33
32. Đẳng cấu khơng? a b d c e 34
33. 4. Đường đi, chu trình, đồ thị liên thơng: Định nghĩa. Cho đồ thị vơ hướng G = (V,E). Trên V ta định nghĩa quan hệ tương đương như sau: u~v u ≡ v hay cĩ một đường đi từ u đến v a) Nếu u~v thì ta nĩi hai đỉnh u và v liên thơng với nhau b) Mỗi lớp tương đương được gọi là một thành phần liên thơng của G c) Nếu G chỉ cĩ một thành phần liên thơng thì G gọi là liên thơng 35
34. 4. Đường đi, chu trình, đồ thị liên thơng: Định nghĩa. Cho G = (V,E) là đồ thị vơ hướng liên thơng a) Đỉnh v được gọi là đỉnh khớp nếu G – v khơng liên thơng (G – v là đồ thị con của G cĩ được bằng cách xố v và các cạnh kề với v) b) Cạnh e được gọi là cầu nếu G- e khơng liên thơng (G-e là đồ thị con của G cĩ được bằng cách xố cạnh e). 37
35. 4. Đường đi, chu trình, đồ thị liên thơng: Cho G = (V,E) là đồ thị vơ hướng u,v V a) Đường đi (dây chuyền) cĩ chiều dài k nối hai đỉnh u,v là dãy đỉnh và cạnh liên tiếp nhau v0e1v1e2 vk-1ekvk sao cho: v 0=u ,v k = v, e i=v i-1v i , i=1,2, ,k 39
36. 4. Đường đi, chu trình, đồ thị liên thơng: a) Đường đi khơng cĩ cạnh nào xuất hiện quá một lần gọi là đường đi đơn b) Đường đi khơng cĩ đỉnh nào xuất hiện quá một lần gọi là đường đi sơ cấp c) Đường đi được gọi là chu trình nếu nĩ bắt đầu và kết thúc tại cùng một đỉnh d) Đường đi được gọi là chu trình sơ cấp nếu nĩ bắt đầu và kết thúc tại cùng một đỉnh và khơng cĩ đỉnh nào xuất hiện quá một lần 40
37. Chu trình sơ cấp nào khơng? (a,e1,b,e2,c,e3,d,e4,b ) là đường đi từ đỉnh a tới đỉnh b cĩ chiều dài là 4. Tuy nhiên, trong trường hợp này, đồ thị của chúng ta là đơn đồ thị, do vậy cĩ thể gọi đường đi này bằng 1 cách ngắn gọn như sau: (a,b,c,d,b) Chu trình sơ cấp: (b,c,d,b) (b,f,e,b) 41
38. Đường đi Euler Euler 42
39. Đường đi Euler Bài tốn. Thị trấn Kưnigsberg chia thành 4 phần bởi các nhánh của dịng sơng Pregel Bốn phần này được nối kết bởi 7 cây cầu 43
40. Đường đi Euler 44
41. Đường đi Euler Câu hỏi. Cĩ thể đi qua bảy cây cầu mà khơng cĩ cây cầu nào đi quá 1 lần 45
42. C A D B C A D B 46
43. Đường đi Euler Đường đi Euler Định nghĩa. 1. Đường đi Euler là đường đi qua tất cả các cạnh mỗi cạnh (cung) đúng một lần. Chu trình Euler là chu trình đi qua tất cả các cạnh của đồ thị mỗi cạnh đúng một lần. 2. Đồ thị được gọi là đồ thị Euler nếu nĩ cĩ chu trình Euler 47
44. Đường đi Euler Điều kiện cần và đủ. Cho G = (V,E) là đồ thị vơ hướng liên thơng. G là đồ thị Euler Mọi đỉnh của G đều cĩ bậc chẵn. Nếu G cĩ hai đỉnh bậc lẻ cịn mọi đỉnh khác đều cĩ bậc chẵn thì G cĩ đường đi Euler Nhận xét. - Nếu đồ thị G chỉ cĩ 2 đỉnh bậc lẻ thì ta cĩ thể vẽ đồ thị bằng 1 nét. - Nếu đồ thị G chỉ cĩ 2k đỉnh bậc lẻ thì ta cĩ thể vẽ đồ thị bằng k nét 48
45. Đường đi Euler Thuật tốn Fleury để tìm chu trình Euler. Bắt đầu từ một đỉnh bất kỳ của G và tuân theo qui tắc sau: 1. Mỗi khi đi qua một cạnh nào đĩ thì xố nĩ đi, sau đĩ xố đỉnh cơ lập nếu cĩ. 2. Khơng bao giờ đi qua một cầu trừ phi khơng cịn cách đi nào khác. 49
46. Đường đi Euler a b c d e h g f abcfdcefghbga 50