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

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. Chương 2 Các khái niệm cơ bản
2. Các khái niệm về đồ thị ⚫ Định nghĩa 1.1 Đồ thị là một cặp G = (V, E), trong đó: - V là tập hợp các đỉnh (vertex), - E  V V là tập hợp các cạnh (edge).
3. Các khái niệm về đồ thị (tt) Đồ thị G cho như hình vẽ. - Tập đỉnh V = {a, b , c, d, e}, - Tập các cạnh E = {(a, b), (a, c), (b, c), (d, b), (d, c), (e, a), (e, b), (e, d)}. b c a e d
4. Đỉnh / Cạnh kề Đỉnh kề: Nếu (a,b) là một cạnh của đồ thị G thì: - Đỉnh b kề với đỉnh a - Hai đỉnh a và b cùng kề với cạnh (a,b). Cạnh kề: - là hai cạnh có ít nhất một đỉnh chung.
5. Ánh xạ kề ⚫ Định nghĩa 1.2 Đồ thị là một cặp G = (V, F), trong đó: - V là tập hợp các đỉnh, - F : V → 2V , được gọi là ánh xạ kề. ⚫ Sự tương đương của hai định nghĩa:  x, y V : (x, y) E y F(x).
6. Ví dụ (ánh xạ kề) Ánh xạ kề của đồ thị trên hình vẽ: F(a) = {b, c} , F(b) = {c} , F(c) =  , F(d) = {b, c} và F(e) = {a, b, d} . b c a e d
7. Cạnh / Cung ⚫ Cạnh: cặp đỉnh (x, y) E không sắp thứ tự. ⚫ Cung : cặp đỉnh (x, y) E có sắp thứ tự.
8. Đồ thị có hướng / vô hướng ⚫ Định nghĩa 1.3 - Đồ thị chỉ chứa các cạnh được gọi là đồ thị vô hướng - Đồ thị chỉ chứa các cung được gọi là đồ thị có hướng. Mỗi đồ thị vô hướng có thể biểu diễn bằng một đồ thị có hướng bằng cách thay mỗi cạnh bằng hai cung tương ứng.
9. Đơn / đa đồ thị ⚫ Định nghĩa 1.5 - Đồ thị G = (V, E) mà mỗi cặp đỉnh được nối với nhau không quá một cạnh được gọi là đơn đồ thị (gọi tắt là đồ thị). - Đồ thị có những cặp đỉnh được nối với nhau nhiều hơn một cạnh thì được gọi là đa đồ thị.
10. Đường đi ⚫ Định nghĩa 1.6: Cho G = (V, E) là một đồ thị. – Đường đi trong đồ thị là một dãy các đỉnh: – – sao cho mỗi đỉnh trong dãy (không kể đỉnh đầu tiên) kề với đỉnh trước nó bằng một cạnh nào đó, nghĩa là: ⚫  i = 2, 3, , k-1, k : (xi-1, xi) E. – Ta nói rằng đường đi này đi từ đỉnh đầu x1 đến đỉnh cuối xk.
11. Đường đi (tt) ⚫ Độ dài của đường đi: là số cạnh của đường đi đó. ⚫ Đường đi đơn: Các đỉnh trên nó khác nhau từng đôi một.
12. Chu trình ⚫ Định nghĩa 1.7 Chu trình là một đường đi khép kín (đỉnh cuối trùng với đỉnh đầu của đường). [x1, x2, , xi, xi+1, , xk-1, xk] trong đó x1 = xk. - Để cho gọn, trong ký hiệu của chu trình thường không viết đỉnh cuối: [x1, x2, , xi, xi+1, , xk-1] Ký hiệu: n là số đỉnh, m là số cạnh của một đồ thị. ⚫ Chu trình đơn: là chu trình mà các đỉnh trên nó khác nhau từng đôi. ⚫ Đỉnh nút: là đỉnh kề với chính nó.
13. Bậc và bán bậc ⚫ Bậc (Degree) của đỉnh: – Giả sử G(V,E) là đồ thị vô hướng. Khi đó: – Bậc của đỉnh v (kí hiệu là Deg(v)) là số cạnh kề với đỉnh đó. ⚫ Bán bậc: – Giả sử G(V,E) là đồ thị có hướng. Khi đó: – Bán bậc vào Deg-(v) là số cung đi vào đỉnh v. – Bán bậc ra Deg+(v) là số cung đi ra từ đỉnh v.
14. Định lý bắt tay ⚫ Đối với đồ thị vô hướng: – “Tổng bậc của tất cả các đỉnh bằng 2 lần số cạnh” ⚫ Đối với đồ thị có hướng: – “Tổng bán bậc vào của mọi đỉnh bằng tổng bậc ra của chúng”.
15. Tính liên thông ⚫ Vô hướng: – Hai đỉnh u, v được gọi là liên thông nếu tồn tại đường đi giữa u và v. – Đồ thị là liên thông nếu mọi cặp đỉnh đều liên thông với nhau. ⚫ Có hướng: – Đồ thị là liên thông mạnh nếu giữa mọi cặp đỉnh đều tồn tại đường đi. – Nếu đồ thị có hướng G(V,E) không liên thông mạnh nhưng đồ thị vô hướng “tương ứng” là liên thông thì ta nói G liên thông yếu. ⚫ Nếu G(V,E) không liên thông khi đó G được tách thành k thành phần liên thông (k>1).
16. Tính liên thông (tt) Đồ thị vô hướng liên thông Đồ thị gồm 2 thành phần liên thông
17. Đồ thị con, đồ thị bộ phận ⚫ Định nghĩa 1.8 Giả sử G = (V, E) là một đồ thị. - Đồ thị G’ = (V’, E’) được gọi là đồ thị con của đồ thị G nếu: V’  V và E’ = E  (V’ V’). - Đồ thị G” = (V, E”) với E”  E, được gọi là đồ thị bộ phận (riêng) của đồ thị G.
18. Đồ thị con, đồ thị bộ phận (tt) ⚫ Một số kết quả - Mỗi tập con các đỉnh V’ của đồ thị tương ứng duy nhất với một đồ thị con. - Để xác định một đồ thị con ta chỉ cần nêu tập đỉnh của nó. - Đồ thị riêng là đồ thị giữ nguyên tập đỉnh và bỏ bớt một số cạnh.
19. Đẳng cấu đồ thị ⚫ Sự đẳng cấu của hai đồ thị dựa trên sự đẳng cấu của hai tập đỉnh sao cho sự đẳng cấu ấy bảo toàn được các cạnh của đồ thị. ⚫ Định nghĩa 1.9 Hai đồ thị G1 = (V1, E1) và G2 = (V2, E2 ) được gọi là đẳng cấu với nhau nếu tồn tại một song ánh S trên các tập đỉnh bảo toàn các cạnh:  x, y V1 : (x, y) E1 (S(x), S(y)) E2.
20. Đẳng cấu đồ thị (tt) ⚫ Hai đồ thị sau là đẳng cấu với song ánh: ⚫ S(ai) = xi , i = 1, 2, 3, 4. a a 1 2 x1 x2 x3 a3 a4 x4
21. Một số dạng đồ thị đặc biệt (SV tự đọc tài liệu) ⚫ Đồ thị đầy đủ. ⚫ Đồ thị vòng. ⚫ Đồ thị bánh xe. ⚫ Đồ thị 2 phía. ⚫