Bài giảng Lý thuyết đồ thị: Chương 1 - PGS.TS. Hoàng Chí Thành

Bài giảng Lý thuyết đồ thị: Chương 1 cung cấp cho người đọc những kiến thức như: Các khái niệm về đồ thị; Biểu diễn đồ thị trong máy tính; Một số tính chất về đường đi trên đồ thị; Bậc của đỉnh và tính liên thông. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết đồ thị: Chương 1 - PGS.TS. Hoàng Chí Thành LÝ THUYẾT ĐỒ THỊ Giảng viên: PGS.TS. Hoàng Chí Thành Trường Đại học Khoa học Tự nhiên, ĐHQG HN MỞ ĐẦU - Lý thuyết Đồ thị là một trong những ngành khoa học ra đời khá sớm. - Lý thuyết Đồ thị giúp mô tả hình học và giải quyết nhiều bài toán thực tế phức tạp liên quan đến các khái niệm như: đường đi, chu trình, tập ổn định, chu số, sắc số, duyệt đồ thị, đường đi ngắn nhất, tâm đồ thị, luồng vận tải, đồ thị phẳng, cây bao trùm, cây biểu thức, cây mã tối ưu …bằng các thuật toán ngắn gọn và lý thú. - Lý thuyết Đồ thị đã gắn kết nhiều ngành khoa học với nhau. 2/63 MỞ ĐẦU (tiếp) Bài giảng điện tử “Lý thuyết Đồ thị” này bao gồm: - 11 chương - phân thành 20 bài học trình bày những vấn đề cốt lõi nhất của lý thuyết đồ thị cùng các thuật toán tiêu biểu; giúp người học có thể cài đặt trên máy tính và ứng dụng trong thực tế. 3/63 CHƯƠNG 1 ĐẠI CƯƠNG VỀ ĐỒ THỊ 4/63 NỘI DUNG  Các khái niệm về đồ thị  Biểu diễn đồ thị trong máy tính  Một số tính chất về đường đi trên đồ thị  Bậc của đỉnh và tính liên thông 5/63 1.1. 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). 6/63 VÍ DỤ 1.1 Đồ 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 Hình 1.1: Đồ thị hữu hạn 7/63 TÍNH KỀ TRONG ĐỒ THỊ Đỉ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). Hai cạnh kề nhau: là hai cạnh có ít nhất một đỉnh chung. 8/63 ĐỊNH NGHĨA ĐỒ THỊ (tiếp)  Đị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). 9/63 VÍ DỤ 1.2 Á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 Hình 1.1: Đồ thị hữu hạn 10/63 ĐỒ THỊ VÔ HƯỚNG VÀ CÓ HƯỚNG  Cạnh vô hướng: cặp đỉnh (x, y)  E không sắp thứ tự.  Cạnh có hướng: cặp đỉnh (x, y)  E có sắp thứ tự. 11/63 ĐỒ THỊ VÔ HƯỚNG VÀ CÓ HƯỚNG (tiếp)  Định nghĩa 1.3 - Đồ thị chỉ chứa các cạnh vô hướng được gọi là đồ thị vô hướng - Đồ thị chỉ chứa các cạnh có hướng đượ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 vô hướng bằng hai cạnh có hướng tương ứng. 12/63 ĐỒ THỊ ĐỐI XỨNG Định nghĩa 1.4 Đồ thị G = (V, E) được gọi là đối xứng nếu:  x, y  V : (x, y)  E  (y, x)  E. - Các đồ thị vô hướng là đối xứng. 13/63 ĐƠN VÀ Đ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ắtlà đồ 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ị. 14/63 1.2. ĐƯỜNG ĐI VÀ CHU TRÌNH  Đị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. 15/63 ĐƯỜNG ĐI  Độ 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. 16/63 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ị. 17/63 CHU TRÌNH (tiếp)  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ó. 18/63 1.3. ĐỒ THỊ CON VÀ ĐỒ THỊ RIÊNG  Đị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ị riêng của đồ thị G. 19/63 1.3. ĐỒ THỊ CON VÀ ĐỒ THỊ RIÊNG (tiếp)  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. ...