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

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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 ? TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 1. Khái niệm cơ bản 1.1 Giới thiệu Nhà toán học Thụy Sĩ Leonhard Euler (April 1707 – September 1783) - 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. DA B C TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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: TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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; San Francisco Denver Los Angeles New York Chicago Washington Detroit TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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 San Francisco Denver Los Angeles New York Chicago Washington Detroit TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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) San Francisco Denver Los Angeles New York Chicago Washington Detroit TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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). TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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ó TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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. San Francisco Denver Los Angeles New York Chicago Washington Detroit TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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ụ: deg(a)=2; deg(b)=4; deg(f)= 3 deg(d)=0; deg(c)=1 Đỉnh d là đỉnh cô lập Đỉnh c là đỉnh treo a b d c e f TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ Bậc đỉnh a: deg(a) ? Bậc đỉnh b: deg(b) ? Bậc đỉnh c: deg(c) ? Bậc đỉnh d: deg(d) ? 1. Khái niệm cơ bản 1.4 Các thuật ngữ a b dc e f Bậc đỉnh e: deg(e) ? Bậc đỉnh f: deg(f) ? TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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. a b c d ef TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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: Thực hành: Tính toán bậc các đỉnh của đồ thị có hướng được cho trong hình bên a b c d ef TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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 v0e1v1e2vk-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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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). TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 2. Đồ thị Euler và đồ thị Hamilton 2.1 Đồ thị Euler Bài tập G1 G2 G3 H1 H2 H3 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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ẻ. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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 efgh TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 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? TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: LÝ THUYẾT ĐỒ THỊ 2. Đồ thị Euler và đồ thị Hamilton 2.2 Đồ thị Hamilton Bài tập Tìm đồ thị Hamilton, đồ thị nửa Hamilton