›
›

Bài giảng Lý thuyết đồ thị - Chương 1: Các khái niệm cơ bản

pdf 59 trang phuongnguyen 5931
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lý thuyết đồ thị - Chương 1: Các khái niệm cơ bản", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_ly_thuyet_do_thi_chuong_1_cac_khai_niem_co_ban.pdf

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 1: Các khái niệm cơ bản

  1. Môn học: Lý thuyết đồ thị Chương 1: Các khái niệm cơ bản Trường ĐHSPKT TP. HCM Khoa Công nghệ Thông tin Email: levinhcntt@yahoo.com
  2. Nội dung I. Định nghĩa đồ thị II. Các loại đồ thị III. Các thuật ngữ cơ bản trong đồ thị IV. Đường đi, chu trình V. Đồ thị liên thông VI. Một số dạng đồ thị đặc biệt Chương 1 – Các khái niệm cơ bản 2 Lý thuyết đồ thị
  3. I. Định nghĩa đồ thị ™Bài toán Euler Konigsber (1736) Có thể chỉ một lần đi qua tất cả 7 chiếc cầu này hay không? Chương 1 – Các khái niệm cơ bản 3 Lý thuyết đồ thị
  4. I. Định nghĩa đồ thị ™Chuyển bài toán về dạng đồ thị ƒ Mỗi vùng là 1 đỉnh ƒ Mỗi chiếc cầu là 1 cạnh Chương 1 – Các khái niệm cơ bản 4 Lý thuyết đồ thị
  5. I. Định nghĩa đồ thị ™Đồ thị được xây dựng từ bài toán Euler ƒ Có thể đi qua tất cả các cạnh của đồ thị, sao cho mỗi cạnh chỉ đi qua đúng một lần được không? Chương 1 – Các khái niệm cơ bản 5 Lý thuyết đồ thị
  6. I. Định nghĩa đồ thị ™Định nghĩa ƒ Đồ thị G là một tập hợp gồm các đỉnh và các cạnh. Ta thường ký hiệu: G = (V, E), trong đó: + V: Là tập các đỉnh + E: Là tập các cạnh V={1, 2, 3, 4} E={a, b, c, d, e} Chương 1 – Các khái niệm cơ bản 6 Lý thuyết đồ thị
  7. Nội dung I. Định nghĩa đồ thị II. Các loại đồ thị III. Các thuật ngữ cơ bản trong đồ thị IV. Đường đi, chu trình V. Đồ thị liên thông VI. Một số dạng đồ thị đặc biệt Chương 1 – Các khái niệm cơ bản 7 Lý thuyết đồ thị
  8. II. Các loại đồ thị Đồ thị Đồ thị vô hướng Đơn đồ thị Đa đồ thị Giảđồthị Đồ thị có hướng Đơn đồ thị Đa đồ thị Chương 1 – Các khái niệm cơ bản 8 Lý thuyết đồ thị
  9. II. Các loại đồ thị ™Đơn đồ thị vô huớng Đồ thị G=(V, E) được gọi là đơn đồ thị vô hướng: ƒ V: Là tập các đỉnh ƒ 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. V={1, 2, 3, 4, 5} E={(1, 2), (1, 3), (1, 5), (2, 5), (3, 4), (3, 5), (4, 5)} Chương 1 – Các khái niệm cơ bản 9 Lý thuyết đồ thị
  10. II. Các loại đồ thị ™Đa đồ thị vô huớng Đồ thị G=(V, E) được gọi là đa đồ thị vô hướng: ƒ V: Là tập các đỉnh ƒ E: Là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V. Hai cạnh e1, e2 gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh V={1, 2, 3, 4, 5} E={(1, 2), (1, 3), (1, 5), (2, 5), (3, 4), (3, 5), (4, 5), (1, 2), (2, 1), (5, 2), (3, 5) } Chương 1 – Các khái niệm cơ bản 10 Lý thuyết đồ thị
  11. II. Các loại đồ thị ™Giả đồ thị vô huớng Đồ thị G=(V, E) được gọi là giả đồ thị vô hướng: ƒ V: Là tập các đỉnh ƒ E: Là họ các cặp không có thứ tự gồm hai phần tử không nhất thiết khác nhau của V. Cạnh e được gọi là khuyên nếu nó có dạng: e=(u, u) V={1, 2, 3, 4, 5} E={(1, 2), (1, 3), (1, 5), (2, 5), (3, 4), (3, 5), (4, 5), (1, 2), (2, 1), (5, 2), (3, 5), (2, 2), (3, 3) } Chương 1 – Các khái niệm cơ bản 11 Lý thuyết đồ thị
  12. II. Các loại đồ thị ™Đơn đồ thị có hướng Đồ thị G=(V, E) được gọi là đơn đồ thị có hướng: ƒ V: Là tập các đỉnh ƒ E: Là tập các cặp có thứ tự gồm hai phần tử khác nhau của V. (tập các cung) V={1, 2, 3, 4, 5} E={(2, 1), (1, 3), (5, 1), (4, 2), (3, 4), (3, 5), (5, 4)} Chương 1 – Các khái niệm cơ bản 12 Lý thuyết đồ thị
  13. II. Các loại đồ thị ™Đa đồ thị có hướng Đồ thị G=(V, E) được gọi là đơn đồ thị có hướng: ƒ V: Là tập các đỉnh ƒ E: Là họ các cặp có thứ tự gồm hai phần tử khác nhau của V. (tập các cung) Hai cung e1, e2 được gọi là cung lặp nếu chúng cùng tương ứng với một cặp đỉnh. V={1, 2, 3, 4, 5} E={(2, 1), (1, 3), (6, 2), (3, 4), (6, 3), (4, 6), (5, 4), (5, 6), (3,1), (6,2)} Chương 1 – Các khái niệm cơ bản 13 Lý thuyết đồ thị
  14. II. Các loại đồ thị Đồ thị Không có thứ tự Đồ thị vô hướng Không cạnh lặp, không khuyên Đơn đồ thị Có cạnh lặp, không khuyên Đa đồ thị Có cạnh lặp, Có khuyên Giảđồthị Có thứ tự Đồ thị có hướng Không cung lặp, không khuyên Đơn đồ thị Có cung lặp, không khuyên Đa đồ thị Chương 1 – Các khái niệm cơ bản 14 Lý thuyết đồ thị
  15. Nội dung I. Định nghĩa đồ thị II. Các loại đồ thị III. Các thuật ngữ cơ bản trong đồ thị IV. Đường đi, chu trình V. Đồ thị liên thông VI. Một số dạng đồ thị đặc biệt Chương 1 – Các khái niệm cơ bản 15 Lý thuyết đồ thị
  16. III. Các thuật ngữ cơ bản ™Kề và liên thuộc ƒ Giả sử u và v là hai đỉnh của đồ thị vô hướng G và e=(u, v) là cạnh của đồ thị, khi đóta nói: + u và v kề nhau và e liên thuộc với u và v. + u và v là các đỉnh đầu của cạnh e v e u Chương 1 – Các khái niệm cơ bản 16 Lý thuyết đồ thị
  17. III. Các thuật ngữ cơ bản ™Bậc của đỉnh ƒ Bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó. ƒ Ký hiệu: deg(v) deg(1)= 2, deg(2)= 2, deg(3)= 3, deg(4)= 3, deg(5)= 3, deg(6)= 1, deg(7)= 0. ƒ Đỉnh treo là đỉnh chỉ có duy nhất một cạnh liên thuộc với nó. Æ Đỉnh 6 ƒ Đỉnh cô lập là đỉnh không có cạnh nào liên thuộc với nó.Æ Đỉnh 7 Chương 1 – Các khái niệm cơ bản 17 Lý thuyết đồ thị
  18. III. Các thuật ngữ cơ bản ™Định lý bắt tay Giả sử G=(V,E) là đồ thị vô hướng với m cạnh. Khi đótổng tất cả các bậc của đỉnh trong V bằng 2m. ∑ deg( v) = 2m v∈V m = 7 ∑ deg(v) = 2m = 14 v∈V Chương 1 – Các khái niệm cơ bản 18 Lý thuyết đồ thị
  19. III. Các thuật ngữ cơ bản ™Định lý bắt tay Chứng minh? ™ Mỗi một cạnh nối với đúng hai đỉnh, vì thế một cạnh đóng góp 2 đơn vị vào tổng các bậc của tất cả các đỉnh. Î tổng các bậc của tất cả các đỉnh gấp đôi số cạnh của đồ thị Chương 1 – Các khái niệm cơ bản 19 Lý thuyết đồ thị
  20. III. Các thuật ngữ cơ bản ™Hệ quả của định lý bắt tay Trong đồ thị vô hướng, số đỉnh bậc lẻ là một số chẵn. Các đỉnh bậc lẻ: 3, 5, 4, 6 Æ 4 đỉnh Chương 1 – Các khái niệm cơ bản 20 Lý thuyết đồ thị
  21. III. Các thuật ngữ cơ bản ™Hệ quả của định lý bắt tay Trong đồ thị vô hướng, số đỉnh bậc lẻ là một số chẵn. Chứng minh:? ™ Gọi L và C lần lượt là tập các đỉnh bậc lẻ và bậc chẵn của đồ thị vô hướng G= (V, E). Ta có: 2m = ∑deg(v) = ∑deg(v) + ∑deg(v) v∈V v∈L v∈C + Tổng 2m chẵn + Tổng ∑ deg( v ) chẵn v∈C Î Tổng ∑ deg( v ) chẵn v∈L Chương 1 – Các khái niệm cơ bản 21 Lý thuyết đồ thị
  22. III. Các thuật ngữ cơ bản ™Kề trong đồ thị có hướng ƒ Giả sử u và v là hai đỉnh của đồ thị có hướng G và e=(u, v) là một cung của đồ thị, khi đóta nói: + u và v kề nhau, cung e đi ra khỏi u và đi vào v. + u là đỉnh đầu, v là đỉnh cuối của cạnh e. v e u Chương 1 – Các khái niệm cơ bản 22 Lý thuyết đồ thị
  23. III. Các thuật ngữ cơ bản ™Bán bậc vào và bán bậc ra của đỉnh ƒ Bán bậc ra (bán bậc vào) của đỉnh v trong đồ thị có hướng là số cung ra khỏi nó (đi vào nó). ƒ Ký hiệu: deg + ( v ) ( deg − ( v ) ) deg + (2) = 1,deg − (2) = 2 deg + (6) = 2,deg − (6) = 1 Chương 1 – Các khái niệm cơ bản 23 Lý thuyết đồ thị
  24. III. Các thuật ngữ cơ bản ™Định lý Giả sử G=(V,E) là đồ thị có hướng với m cung, khi đó tổng tất cả các bán bậc ra bằng tổng tất cả các bán bậc vào và bằng m. ∑ deg + (v) = ∑ deg − (v) = m v∈V v∈V ∑deg+ (v) = ∑deg− (v) = 7 v∈V v∈V Chương 1 – Các khái niệm cơ bản 24 Lý thuyết đồ thị
  25. III. Các thuật ngữ cơ bản ™ Bài tập 1.Có bao nhiêu cạnh trong đồ thị có 10 đỉnh, mỗi đỉnh có bậc bằng 6 a) 20 b) 30 c) 40 d)50 2.Cho biết các đỉnh của đồ thị có bậc lần lượt là: 4, 3, 3, 2, 2. Số cạnh của đồ thị này là: a) 5 b) 6 c) 7 d) 8 3.Cho danh sách bậc các đỉnh của các đồ thị sau, đồ thị nào không tồn tại? a) 3, 3, 3, 3, 2 b) 1, 2, 3, 4, 5 c) 0, 1, 2, 2, 3 d) 1, 1, 1, 1 Chương 1 – Các khái niệm cơ bản 25 Lý thuyết đồ thị
  26. III. Các thuật ngữ cơ bản ™ Bài tập 4. Có thể tồn tại đồ thị đơn 15 đỉnh, mỗi đỉnh có bậc bằng 5 hay không? 5. Trong một giải thi đấu có n đội tham dự và đã có n+1 trận đấu được tiến hành. CMR có 1 đội đã thi đấu ít nhất 3 trận. Chương 1 – Các khái niệm cơ bản 26 Lý thuyết đồ thị
  27. Nội dung I. Định nghĩa đồ thị II. Các loại đồ thị III. Các thuật ngữ cơ bản trong đồ thị IV. Đường đi, chu trình V. Đồ thị liên thông VI. Một số dạng đồ thị đặc biệt Chương 1 – Các khái niệm cơ bản 27 Lý thuyết đồ thị
  28. IV. Đường đi, chu trình ™ Đường đi độ dài n từ đỉnh u đến đỉnh v trên đồ thị vô hướng G=(V,E) là dãy(theo đỉnh): x0, x1, , xn-1, xn. Trong đó: + u= x0 + v= xn + (xi, xi+1) ∈ E ™ Hay theo cạnh: (x0, x1), (x1, x2), , (xn-1, xn). ™ Khi đó: u gọi là đỉnh đầu, v gọi là đỉnh cuối của đường đi. Theo đỉnh: (1, 3, 4, 5, 6) Theo cạnh: (b, c, h, g) Chương 1 – Các khái niệm cơ bản 28 Lý thuyết đồ thị
  29. IV. Đường đi, chu trình ™ Đường đi có đỉnh đầu và đỉnh cuối trùng nhau gọi là chu trình. ƒ Đường đi (hay chu trình) được gọi là đơn nếu nó không đi qua một cạnh nào quá một lần. Chu trình đơn: (1, 2, 6, 3, 1) Chu trình không phải chu trình đơn: (2, 6, 4, 3, 6, 2) Chương 1 – Các khái niệm cơ bản 29 Lý thuyết đồ thị
  30. IV. Đường đi, chu trình ™ Đường đi và chu trình trong đồ thị có hướng Đường đi độ dài n (n∈N+) từ đỉnh u đến đỉnh v trên đồ thị có hướng G=(V,E) là dãy: x0 , x1, , xn-1, xn . Trong đóu= x0 , v= xn , (xi , xi+1) ∈ E Hay theo các cung: (x0 , x1 ), (x1, x2 ), , (xn-1, xn ). a 2 4 1 c g (1, 2, 6, 4, 3) b f (a, c, f, d) d 5 (1, 3, 4, 5, 6) 3 h e 30 6 Chương 1 – Các khái niệm cơ bản 30 Lý thuyết đồ thị
  31. Nội dung I. Định nghĩa đồ thị II. Các loại đồ thị III. Các thuật ngữ cơ bản trong đồ thị IV. Đường đi, chu trình V. Đồ thị liên thông VI. Một số dạng đồ thị đặc biệt Chương 1 – Các khái niệm cơ bản 31 Lý thuyết đồ thị
  32. V.Đồ thị 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 2 đỉnh bất kỳ của nó. Đường đi: 1, 3, 2, 4, 5 Chương 1 – Các khái niệm cơ bản 32
  33. V.Đồ thị liên thông ™ Đồ thị H=(W,F) được gọi là đồ thị con của đồ thị G=(V,E) nếu : W ⊆ V và F ⊆ E V={1, 2, 3, 4, 5} W={1, 2, 4, 5} E={a, b, c, d, e} F={a, d, e} Chương 1 – Các khái niệm cơ bản 33
  34. VI. Một số dạng đồ thị đặc biệt ™ Bài tập 1. Đồ thị K3 có bao nhiêu đồ thị con có ít nhất một đỉnh ? Chương 1 – Các khái niệm cơ bản 34 Lý thuyết đồ thị
  35. V.Đồ thị liên thông ™Một đồ thị không liên thông sẽ được phân rã thành các thành phần liên thông, và mỗi thành phần liên thông này là một đồ thị con của đồ thị ban đầu. Chương 1 – Các khái niệm cơ bản 35
  36. V.Đồ thị liên thông • Đỉnh v được gọi là đỉnh rẽ nhánh nếu việc loại bỏ v cùng các cạnh liên thuộc với nó sẽ 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ó sẽ làm tăng số thành phần liên thông của đồ thị 2 Các đỉnh rẽ nhánh? 1 Các cạnh là cầu ? G 5 3 4 Chương 1 – Các khái niệm cơ bản 36
  37. V.Đồ thị liên thông • Đồ thị có hướng G=(V,E) được gọi là liên thông mạnh nếu luôn tìm được đường đi từ 1 đỉnh bất kỳ đến một đỉnh bất kỳ khác của nó. • Đồ thị có hướng G=(V,E) được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là đồ thị vô hướng liên thông. 1 1 2 2 G 5 H 5 3 3 4 4 Chương 1 – Các khái niệm cơ bản 37
  38. V.Đồ thị liên thông ™ Bài tập 1. Trong 1 đồ thị G có chứa đúng 2 đỉnh bậc lẻ (các đỉnh còn lại nếu có đều bậc chẵn). CM có 1 đường đi nối 2 đỉnh bậc lẻ đóvới nhau. Chương 1 – Các khái niệm cơ bản 38
  39. Nội dung I. Định nghĩa đồ thị II. Các loại đồ thị III. Các thuật ngữ cơ bản trong đồ thị IV. Đường đi, chu trình V. Đồ thị liên thông VI. Một số dạng đồ thị đặc biệt Chương 1 – Các khái niệm cơ bản 39 Lý thuyết đồ thị
  40. VI. Một số dạng đồ thị đặc biệt ™ Đồ thị đầy đủ: Một đồ thị đơn vô hướng n đỉnh được gọi là đồ thị đầy đủ nếu hai đỉnh bất kỳ đều được nối với nhau bằng 1 cạnh. ™ Ký hiệu: Kn Số cạnh của Đồ thị đầy đủ ? Chương 1 – Các khái niệm cơ bản 40 Lý thuyết đồ thị
  41. VI. Một số dạng đồ thị đặc biệt ™ Đồ thị vòng: Một đồ thị đơn vô hướng n đỉnh được gọi là đồ thị vòng nếu nó có duy nhất một chu trình đơn đi qua tất cả các đỉnh. ™ Ký hiệu: Cn Số cạnh, số đỉnh của Đồ thị vòng ? Chương 1 – Các khái niệm cơ bản 41 Lý thuyết đồ thị
  42. VI. Một số dạng đồ thị đặc biệt ™ Đồ thị bánh xe với n ≥ 3 đỉnh là đồ thị thu được từ đồ thị Cn bằng cách bổ xung thêm một đỉnh mới nối với tất cả các đỉnh của Cn. ™ Ký hiệu: Wn Số cạnh, số đỉnh của Đồ thị bánh xe ? Chương 1 – Các khái niệm cơ bản 42 Lý thuyết đồ thị
  43. VI. Một số dạng đồ thị đặc biệt ™ Đồ thị siêu khối Đồ thị siêu khối k=2n đỉnh là đồ thị có các đỉnh được đánh số bằng các chuỗi nhị phân độ dài n. ™ Ký hiệu: Qn ™ Hai đỉnh kề nhau nếu 2 chuỗi nhị phân tương ứng chỉ khác nhau 1 bit. Số cạnh của đồ thị siêu khối là: n.2n - 1 Chương 1 – Các khái niệm cơ bản 43 Lý thuyết đồ thị
  44. VI. Một số dạng đồ thị đặc biệt ™ Đồ thị hai phía Đơn đồ thị G=(V, E) gọi là đồ thị hai phía nếu: -V = X ∪ Y, X ≠ ∅, Y ≠ ∅, X ∩ Y = ∅ -Mỗi cạnh của G sẽ có một đỉnh thuộc X và một đỉnh thuộc Y. Chương 1 – Các khái niệm cơ bản 44 Lý thuyết đồ thị
  45. VI. Một số dạng đồ thị đặc biệt ™ Đồ thị hai phía đầy đủ Đơn đồ thị G = (X ∪ Y, E ) được gọi là đồ thị hai phía đầy đủ nếu: Mỗi đỉnh thuộc X sẽ được nối với mỗi đỉnh thuộc Y. Nếu |X| = m và |Y| = n thì ta sẽ ký hiệu là: Km, n Số cạnh của Đồ thị hai phía đầy đủ ? Chương 1 – Các khái niệm cơ bản 45 Lý thuyết đồ thị
  46. VI. Một số dạng đồ thị đặc biệt ™Định lý: Đơn đồ thị G = (V, E) là đồ thị hai phía khi và chỉ khi nó không chứa chu trình độ dài lẻ. ™Chứng minh: ∀ Đồ thị hai phía ⇒ Không chứa chu trình độ dài lẻ ∀ Đồ thị, không chứa chu trình độ dài lẻ ⇒ hai phía Chương 1 – Các khái niệm cơ bản 46 Lý thuyết đồ thị
  47. VI. Một số dạng đồ thị đặc biệt ™Thuật toán kiểm tra đồ thị hai phía 1. Chọn v là đỉnh bất kỳ. Đặt X = {v} 2. Y = { u | u kề với v, ∀ v ∈ X} 3. Nếu X ∩ Y ≠∅ ⇒G không là đồ thị hai phía 4. Ngược lại, đặt X := Y Quay trở lại 2. 5. Nếu tất cả các đỉnh được xét hết mà không xảy ra 3. thì G là đồ thị hai phía. Ngược lại G không là đồ thị hai phía. Chương 1 – Các khái niệm cơ bản 47 Lý thuyết đồ thị
  48. VI. Một số dạng đồ thị đặc biệt ™ Ví dụ: X= {1} Y= {5}, X ∩ Y = ∅, ⇒ X:=Y Y= {1, 2}, X ∩ Y = ∅, ⇒ X:=Y Y= {5, 6, 7}, X ∩ Y = ∅, ⇒ X:=Y Y = {1, 2, 3, 4} DỪNG Khi đó đồ thị là hai phía: X={1, 2, 3, 4} Y={5, 6, 7} Chương 1 – Các khái niệm cơ bản 48 Lý thuyết đồ thị
  49. VI. Một số dạng đồ thị đặc biệt ™ Bài tập: Kiểm tra đồ thị sau có phải là đồ thị hai phía hay không? Chương 1 – Các khái niệm cơ bản 49 Lý thuyết đồ thị
  50. VI. Một số dạng đồ thị đặc biệt ™ Bài tập: Không phải là đồ thị hai phía Chu trình độ dài lẻ Chương 1 – Các khái niệm cơ bản 50 Lý thuyết đồ thị
  51. VI. Một số dạng đồ thị đặc biệt ™ Đồ thị phẳng Đồ thị được gọi là đồ thị phẳng nếu ta có thể vẽ nó trên một mặt phẳng mà các cạnh không giao nhau. Chương 1 – Các khái niệm cơ bản 51 Lý thuyết đồ thị
  52. VI. Một số dạng đồ thị đặc biệt ™ Định lý Euler Giả sử G = (V, E) là đồ thị phẳng, liên thông với e cạnh và v đỉnh. Gọi f là số mặt của đồ thị. Khi đó: f = e – v + 2. Số cạnh: e = 4 Số đỉnh: v = 4 Số mặt: f = 4 – 4 + 2 = 2 Chương 1 – Các khái niệm cơ bản 52 Lý thuyết đồ thị
  53. VI. Một số dạng đồ thị đặc biệt ™ Định lý Euler Chứng minh: Bằng PP Quy nạp ™ Gọi fn, en, vn lần lượt là số mặt, số cạnh, số đỉnh của đồ thị phẳng Gn do biểu diễn phẳng của đồ thị G với n cạnh sinh ra + Trường hợp: e1=1, v1=2 thì f1 = 1 – 2 + 2 = 1 + Giả sử đồ thị Gn (n cạnh) thỏa đẳng thức: fn = en –vn + 2. Thêm vào đồ thị Gn một cạnh (an+1, bn+1) để được đồ thị Gn+1. Ta phải chứng minh: fn+1=en+1 –vn+1 + 2 Xảy ra hai trường hợp Chương 1 – Các khái niệm cơ bản 53 Lý thuyết đồ thị
  54. VI. Một số dạng đồ thị đặc biệt ™ Định lý Euler (Chứng minh) + Cả 2 đỉnh an+1, bn+1 thuộc Gn: fn+1= fn +1 en+1=en+ 1 vn+1=vn ==> fn+1 = en+1 –vn+1 + 2 fn + 1 = en + 1 – vn + 2 fn = en –vn + 2 Chương 1 – Các khái niệm cơ bản 54 Lý thuyết đồ thị
  55. VI. Một số dạng đồ thị đặc biệt ™ Định lý Euler (Chứng minh) + Cả 2 đỉnh an+1, bn+1 thuộc Gn: fn+1= fn en+1=en+ 1 vn+1=vn + 1 Î fn+1 = en+1 –vn+1 + 2 fn = en + 1 – vn + 1 + 2 fn = en –vn + 2 Î ĐPCM Chương 1 – Các khái niệm cơ bản 55 Lý thuyết đồ thị
  56. VI. Một số dạng đồ thị đặc biệt ™ Định lý Kuratowski Phép chia cạnh (u, v) là việc ta bỏ đi cạnh (u, v) và thêm vào một đỉnh mới w cùng với hai cạnh (u, w), (w, v). ™ Định nghĩa đồng cấu Hai đồ thị được gọi là đồng cấu nếu chúng có thể thu được từ cùng một đồ thị nào đónhờ các phép chia cạnh. Chương 1 – Các khái niệm cơ bản 56 Lý thuyết đồ thị
  57. VI. Một số dạng đồ thị đặc biệt ™ Định lý Kuratovski Điều kiện cần và đủ để một đồ thị là phẳng là đồ thị này không chứa bất kỳ một đồ thị con nào đồng cấu với K3,3 và K5 Chương 1 – Các khái niệm cơ bản 57 Lý thuyết đồ thị
  58. VI. Một số dạng đồ thị đặc biệt Các dạng đồ thị đặc biệt Đồ thị đầy đủ (Kn) Đồ thị vòng (Cn) Đồ thị bánh xe (Wn) Đồ thị siêu khối (Qn) Đồ thị hai phía Đồ thị hai phía đầy đủ (Km,n) Đồ thị phẳng Chương 1 – Các khái niệm cơ bản 58 Lý thuyết đồ thị
  59. VI. Một số dạng đồ thị đặc biệt ™ Bài tập 1. Số cạnh của đồ thị K8 ? 2. Số cạnh của đồ thị C2007 ? 3. Số cạnh của đồ thị W100 ? 4. Cho đồ thị G phẳng, liên thông có 20 đỉnh, bậc của mỗi đỉnh bằng 3. Đồ thị biểu diễn phẳng của G có bao nhiêu mặt? 5. Cho đồ thị phân đôi p đỉnh và q cạnh. CM: q ≤ p2/4. Dấu = xảy ra khi nào? 6. Cho đồ thị G có n đỉnh, m cạnh với m ≥ n. Chứng minh G có một chu trình. 7. Có bao nhiêu đồ thị đơn gồm 5 đỉnh và có 4 hoặc 6 cạnh ? Chương 1 – Các khái niệm cơ bản 59 Lý thuyết đồ thị