Bài giảng Toán ứng dụng - Bài 3: Lý thuyết đồ thị

Nội dung text: Bài giảng Toán ứng dụng - Bài 3: Lý thuyết đồ thị

1. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: MÔN HỌC: TOÁN ỨNG DỤNG Bài 1: CƠ SỞ LOGIC Bài 2: BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI Bài 3: LÝ THUYẾT ĐỒ THỊ Bài 4: BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM Bài 5: CÂY VÀ CÁC ỨNG DỤNG LÝ THUYẾT ĐỒ THỊ
2. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: Bài 3: LÝ THUYẾT ĐỒ THỊ 1. KHÁI NIỆM CƠ BẢN 1.1 Giới thiệu 1.2 Định nghĩa đồ thị 1.3 Phân loại đồ thị 1.4 Các thuật ngữ 1.5 Định lý về bậc của đỉnh 1.6 Đường đi, chu trình, đồ thị liên thông 2. ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON 2.1 Đồ thị Euler 2.2 Đồ thị Hamilton LÝ THUYẾT ĐỒ THỊ
3. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.1 Giới thiệu - Bài toán về các cây cầu ở Konigsberg: Có cách nào để đi dạo qua tất cả bảy cây cầu, mà mỗi cây cầu chỉ đi qua một lần ? LÝ THUYẾT ĐỒ THỊ
4. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.1 Giới thiệu - Năm 1736, là năm khai sinh lý thuyết đồ thị, qua việc công bố lời giải bài toán về các cây cầu ở Konigsberg của nhà toán học Euler. C A D Nhà toán học Thụy Sĩ Leonhard Euler B (April 1707 – September 1783) LÝ THUYẾT ĐỒ THỊ
5. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.2 Định nghĩa đồ thị Định nghĩa: Đồ thị G được xác định bởi (V, E) gồm: - V là tập hợp hữu hạn khác rỗng các phần tử gọi là đỉnh (hay nút) của đồ thị; - E là tập hợp các cặp đỉnh. Mỗi phần tử của E được gọi là một cạnh. LÝ THUYẾT ĐỒ THỊ
6. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.2 Định nghĩa đồ thị Định nghĩa: Cho hai đồ thị G = (V,E) và G’ = (V’,E’) . G’ được gọi là đồ thị con của G, ký hiệu G’ G nếu V’ V và E’  E . Nếu V’= V và E’  E thì G’ được gọi là đồ thị con khung của G. G H LÝ THUYẾT ĐỒ THỊ
7. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.3 Phân loại đồ thị Đồ thị G được phân loại theo đặc tính và số lượng của tập các cạnh E: LÝ THUYẾT ĐỒ THỊ
8. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.3 Phân loại đồ thị Đồ thị G được phân loại theo đặc tính và số lượng của tập các cạnh E: - G được gọi là đơn đồ thị nếu giữa hai đỉnh u, v thuộc V chỉ có nhiều nhất là 1 cạnh; Detroit New York San Francisco Chicago Denver Washington Los Angeles LÝ THUYẾT ĐỒ THỊ
9. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.3 Phân loại đồ thị Đồ thị G được phân loại theo đặc tính và số lượng của tập các cạnh E: - G được gọi là đa đồ thị nếu giữa hai đỉnh u, v thuộc V có nhiều hơn 1 cạnh Detroit New York San Francisco Chicago Denver Washington Los Angeles LÝ THUYẾT ĐỒ THỊ
10. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.3 Phân loại đồ thị Đồ thị G được phân loại theo đặc tính và số lượng của tập các cạnh E: - Đa đồ thị G được gọi là giả đồ thị nếu có khuyên. Khuyên là cạnh có hai đầu mút trùng nhau, dạng (u,u) Detroit New York San Francisco Chicago Denver Washington Los Angeles LÝ THUYẾT ĐỒ THỊ
11. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.3 Phân loại đồ thị Đồ thị G được phân loại theo đặc tính và số lượng của tập các cạnh E: - G là đồ thị vô hướng nếu các cạnh trong E là không định hướng. Tập E gồm các cặp (u,v) không sắp thứ tự (u,v)≡ (v,u) - G là đồ thị có hướng nếu các cạnh trong E là có định hướng. Trong đồ thị có hướng, hai điểm u và v, có thể được nối bởi hai cung (u,v) và (v,u). LÝ THUYẾT ĐỒ THỊ
12. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.3 Phân loại đồ thị Đồ thị G được phân loại theo đặc tính và số lượng của tập các cạnh E: Loại đồ thị Cạnh Có cạnh bội Có khuyên Đơn đồ thị vô hướng Vô hướng Không Không Đa đồ thị vô hướng Vô hướng Có Không Giả đồ thị vô hướng Vô hướng Có Có Đồ thị có hướng Có hướng Không Có Đa đồ thị có hướng Có hướng Có Có LÝ THUYẾT ĐỒ THỊ
13. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.4 Các thuật ngữ - Cạnh uv nối u với v, cạnh uv được gọi là cạnh liên thuộc với u,v; đỉnh u được gọi là kề với đỉnh v. - Hai cạnh nối cùng một cặp đỉnh gọi là cạnh song song. - Cạnh uv nối u với v, cạnh uv được gọi là cạnh liên thuộc với u,v; đỉnh u được gọi là kề với đỉnh v. Detroit New York San Francisco Chicago Denver Washington Los Angeles LÝ THUYẾT ĐỒ THỊ
14. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.4 Các thuật ngữ - Cho đồ thị vô hướng G = (V,E). Bậc của đỉnh v, ký hiệu deg(v), là số cạnh liên thuộc 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. - Đỉnh có bậc bằng 0 gọi là đỉnh cô lập - Đỉnh có bậc bằng 1 gọi là đỉnh treo Ví dụ: a b deg(a)=2; deg(b)=4; deg(f)= 3 f deg(d)=0; deg(c)=1 c Đỉnh d là đỉnh cô lập Đỉnh c là đỉnh treo d e LÝ THUYẾT ĐỒ THỊ
15. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.4 Các thuật ngữ Bậc đỉnh a: deg(a) ? a b Bậc đỉnh b: deg(b) ? f Bậc đỉnh c: deg(c) ? c d Bậc đỉnh d: deg(d) ? e Bậc đỉnh e: deg(e) ? Bậc đỉnh f: deg(f) ? LÝ THUYẾT ĐỒ THỊ
16. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.4 Các thuật ngữ Cho đồ thị có hướng G* = (V,E). - bậc ra của đỉnh v, ký hiệu deg+(v), là số cung đi ra khỏi đỉnh, - bậc vào của đỉnh v, ký hiệu deg-(v), là số cung đi vào đỉnh. f e a d b c LÝ THUYẾT ĐỒ THỊ
17. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.5 Định lý về bậc của đỉnh Định lý: Với G là đồ thị vô hướng, với m cạnh, khi đó tổng số bậc của đỉnh là 2m. Hệ quả: Trong đồ thị vô hướng, tổng số đỉnh bậc lẻ là một số chẵn. LÝ THUYẾT ĐỒ THỊ
18. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.5 Định lý về bậc của đỉnh Định lý: Với G* là đồ thị có hướng, với m cung, khi đó chúng ta có công thức: e Thực hành: f Tính toán bậc các đỉnh của a đồ thị có hướng được cho d trong hình bên b c LÝ THUYẾT ĐỒ THỊ
19. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.5 Định lý về bậc của đỉnh Bài tập 1: Vẽ đơn đồ thị vô hướng gồm 6 đỉnh với bậc là: 2,2,3,3,3,5 Bài tập 2: Vẽ đơn đồ thị vô hướng gồm 6 đỉnh với bậc là: 2,2,3,3,3,3 LÝ THUYẾT ĐỒ THỊ
20. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.6 Đường đi, chu trình, đồ thị liên thông Định nghĩa: Cho G = (V,E) là đồ thị vô hướng u,v V a) Đường đi (dây chuyền) độ 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: v0=u ,vk= v, ei=vi-1vi , i=1,2, ,k b) Đường đi không có cạnh nào xuất hiện quá một lần gọi là đường đi đơn c) Đườ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 LÝ THUYẾT ĐỒ THỊ
21. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.6 Đường đi, chu trình, đồ thị liên thông Định nghĩa: Đường đi được gọi là chu trình nếu bắt đầu và kết thúc tại cùng một đỉnh Đường đi đơn có đỉnh bắt đầu và đỉnh kết thúc trùng nhau tạo ra chu trình đơn. Bài toán: Hãy xác định theo đồ thị: 1- đường đi đơn 2- đường đi sơ cấp 3- chu trình và chu trình đơn LÝ THUYẾT ĐỒ THỊ
22. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.6 Đường đi, chu trình, đồ thị liên thông Định nghĩa: Đồ 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 hai đỉnh bất kỳ của đồ thị. Với đồ thị G không liên thông, G được phân rã thành một số đồ thị con liên thông. Mỗi đồ thị con này được gọi là thành phần liên thông. LÝ THUYẾT ĐỒ THỊ
23. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.6 Đường đi, chu trình, đồ thị liên thông Định nghĩa: Đồ thị có hướng G* = (V,E) tính liên thông được xác định theo hướng của cung. Đồ thị G* là liên thông mạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của đồ thị. Đồ thị G* là liên thông yếu nếu chỉ tồn tại đồ thị vô hướng nền của nó là liên thông. LÝ THUYẾT ĐỒ THỊ
24. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Khái niệm cơ bản 1.6 Đườ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 xoá 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 xoá cạnh e). LÝ THUYẾT ĐỒ THỊ
25. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Đồ thị Euler và đồ thị Hamilton 2.1 Đồ thị Euler Định nghĩa Chu trình đơn trong G = (V,E) đi qua mỗi cạnh của đồ thị một lần gọi là chu trình Euler. Đường đi đơn trong G đi qua mỗi cạnh của đồ thị một lần được gọi là đường đi Euler. Đồ thị được gọi là đồ thị Euler nếu có chu trình Euler Đồ thị được gọi là đồ thị nửa Euler nếu có có đường đi Euler LÝ THUYẾT ĐỒ THỊ
26. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Đồ thị Euler và đồ thị Hamilton 2.1 Đồ thị Euler Bài tập G1 G2 G3 H1 H2 H3 LÝ THUYẾT ĐỒ THỊ
27. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Đồ thị Euler và đồ thị Hamilton 2.1 Đồ thị Euler Định lý Đồ thị vô hướng liên thông G = (V,E) là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn. Hệ quả Đồ thị vô hướng liên thông G = (V,E) là đồ thị nửa Euler khi và chỉ khi G có không quá 2 đỉnh bậc lẻ. LÝ THUYẾT ĐỒ THỊ
28. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Đồ thị Euler và đồ thị Hamilton 2.1 Đồ thị Euler Thuật toán 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- Xóa bỏ cạnh đã đi qua và đồng thời xóa đỉnh cô lập tạo thành. 2- Ở mỗi bước ta chỉ qua cầu khi không còn cách lựa chọn nào khác. LÝ THUYẾT ĐỒ THỊ
29. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Đồ thị Euler và đồ thị Hamilton 2.1 Đồ thị Euler Thuật toán tìm chu trình Euler Ví dụ: Tìm chu trình Euler cho đồ thị G dưới đây a b c d e h g f LÝ THUYẾT ĐỒ THỊ
30. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Đồ thị Euler và đồ thị Hamilton 2.2 Đồ thị Hamilton Định nghĩa Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần. Chu trình bắt đầu từ 1 đỉnh v nào đó qua tất cả các đỉnh còn lại đúng một lần, rồi quay trở về lại đỉnh v. Đồ thị gọi là đồ thị Hamilton nếu có chu trình Hamilton Đồ thị gọi là đồ thị nửa Hamilton nếu có đường đi Hamilton LÝ THUYẾT ĐỒ THỊ
31. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Đồ thị Euler và đồ thị Hamilton 2.2 Đồ thị Hamilton Định nghĩa Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần. Ví dụ Đồ thị hình bên có phải là đồ thị Hamilton? LÝ THUYẾT ĐỒ THỊ
32. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Đồ thị Euler và đồ thị Hamilton 2.2 Đồ thị Hamilton Bài tập Tìm đồ thị Hamilton, đồ thị nửa Hamilton LÝ THUYẾT ĐỒ THỊ