Bài giảng Toán rời rạc - Chương 6: Đồ thị - Phần 1

Giảng viên: ThS. Trần Quang Khải TOÁN RỜI RẠC Chương 06: Đồ thị Toán rời rạc: 2011-2012 Nội dung 1. Giới thiệu về lý thuyết đồ thị. 2. Đồ thị vô hướng – Đồ thị có hướng. 3. Bậc của đỉnh. 4. Một số dạng đồ thị đặc biệt. 5. Biểu diễn đồ thị trên máy tính. Chương 6: Đồ thị 2 Toán rời rạc: 2011-2012 Giới thiệu Những câu hỏi cũ: Đường nào nhanh nhất tới nhà người yêu? Đường nào gần nhất tới café Gió và Nước? Chương 6: Đồ thị 3 Toán rời rạc: 2011-2012 Giới thiệu Câu hỏi khác:  Thế kế mạng LAN cho tòa nhà 20 tầng thế nào đây?  Sắp đặt các links trong website sao cho hợp lý?  Sắp xếp cả núi công việc để hoàn thành sớm nhất? Chương 6: Đồ thị 4 Toán rời rạc: 2011-2012 Giới thiệu Định nghĩa đồ thị (graph): cấu trúc rời rạc gồm  Các đỉnh (vertices or nodes).  Các cạnh (edges) nối các đỉnh. Biểu diễn: Đỉnh: các điểm.  Cạnh: đường thẳng/cong. Hai loại: Đồ thị vô hướng (undirected graph). Đồ thị có hướng (directed graph). Chương 6: Đồ thị 5 Toán rời rạc: 2011-2012 Giới thiệu Lý thuyết đồ thị:  Là một lý thuyết kinh điển. Ứng dụng rộng rãi ngày nay, trong nhiều lĩnh vực: • Nghiên cứu Khoa học. • Công nghiệp.  Khởi xướng: Leonard Euler (thế kỷ 18). Chương 6: Đồ thị 6 Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Đồ thị vô hướng Đồ thị có hướng Chương 06 Toán rời rạc: 2011-2012 Đồ thị đơn cạnh Simple graph (đơn đồ thị): G = (V, E) V: một tập hợp không rỗng của các đỉnh. E: tập các cặp đỉnh (tức các cạnh) không-thứ-tự.  Các cạnh nối (connect) các đỉnh lại với nhau.  Giữa 2 đỉnh chỉ có đúng 1 cạnh. Chương 6: Đồ thị 8 Toán rời rạc: 2011-2012 Đồ thị đa cạnh Multi-graph (đa đồ thị): G = (V, E) E: cho phép nhiều cạnh nối một cặp đỉnh. Chương 6: Đồ thị 9 Toán rời rạc: 2011-2012 Đồ thị “giả” Pseudo-graph (giả đồ thị): G = (V, E) E: cho phép lặp (loop) tại các đỉnh. (Còn gọi là chứa các khuyên) Chương 6: Đồ thị 10 Toán rời rạc: 2011-2012 Đồ thị có hướng Directed graph: G = (V, E) V: một tập hợp không rỗng của các đỉnh. E: tập các cặp đỉnh có-thứ-tự.  Cạnh nối 2 đỉnh gọi là cung (arc). Chương 6: Đồ thị 11 Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Bậc của đỉnh Chương 06 Toán rời rạc: 2011-2012 Một số thuật ngữ cơ bản Đồ thị vô hướng: Cho G = (V, E) là đồ thị vô hướng và u và v gọi là 2 đỉnh liền kề (adjacent). e gọi là cạnh nối (cạnh kề: incident) của u và v. u và v gọi là điểm cuối của e.  Bậc (degree) của đỉnh là số các cạnh nối với nó.  Kí hiệu: deg(e) = Chương 6: Đồ thị 13 Evue  ),( Toán rời rạc: 2011-2012 Bậc của đỉnh – Ví dụ Chương 6: Đồ thị 14 Điểm “bị treo” Điểm “cô lập” ( ) ( ) Toán rời rạc: 2011-2012 Một số thuật ngữ cơ bản Đồ thị có hướng: Cho G = (V, E) là đồ thị có hướng và u gọi là nối tới v, v gọi là được nối từ u. u gọi là đỉnh đầu, v gọi là đỉnh cuối. Khi đó:  deg−(u): bậc “vào” (in-degree) của u.  deg+(u): bậc “ra” (out-degree) của u. Chương 6: Đồ thị 15 Evue  ),( Toán rời rạc: 2011-2012 Bậc của đỉnh – Ví dụ Chương 6: Đồ thị 16 Toán rời rạc: 2011-2012 Bậc của đỉnh – Định lý Định lý 1: Cho G = (V, E) là đồ thị vô hướng: (Handshaking theorem) Một đồ thị luôn có 1 số chẵn các đỉnh bậc lẻ. Lưu ý: định lý 1 đúng ngay cả khi đồ thị là đa cạnh hoặc có chứa khuyên. Chương 6: Đồ thị 17    Vv vdegE )(2 Toán rời rạc: 2011-2012 Bậc của đỉnh – Định lý Định lý 2: Cho G = (V, E) là đồ thị có hướng: Chương 6: Đồ thị 18       VvVv vdegvdegE )()( Toán rời rạc: 2011-2012 Một số dạng đồ thị đặc biệt 1. Đồ thị đầy đủ (complete): n đỉnh Mỗi cặp đỉnh đều có đúng 1 cạnh nối. Kí hiệu: Kn. Chương 6: Đồ thị 19 Toán rời rạc: 2011-2012 Một số dạng đồ thị đặc biệt 2. Đồ thị chu trình (cycle - vòng): n ≥ 3 đỉnh  Kí hiệu: Cn. Chương 6: Đồ thị 20 Toán rời rạc: 2011-2012 Một số dạng đồ thị đặc biệt 3. Đồ thị bánh xe (wheel): n ≥ 3 đỉnh và 1 đỉnh ở giữa nối với các đỉnh kia. Kí hiệu: Wn. Chương 6: Đồ thị 21 Toán rời rạc: 2011-2012 Một số dạng đồ thị đặc biệt 4. Đồ thị hình sao(star): n ≥ 3 đỉnh và 1 đỉnh ở giữa nối với các đỉnh kia. Kí hiệu: Sn. Chương 6: Đồ thị 22 Toán rời rạc: 2011-2012 Một số dạng đồ thị đặc biệt 5. Đồ thị dạng khối n chiều : n-cube.  Kí hiệu: Qn. Chương 6: Đồ thị 23 Q3 Q2 Toán rời rạc: 2011-2012 Một số ứng dụng Mạng cục bộ (LAN):  hình sao,  vòng,  bus,  lai (có dư thừa nhưng tăng độ tin cậy). Cấu trúc kết nối của máy tính song song: một chiều,  lưới,  siêu khối (n-cube). Chương 6: Đồ thị 24 Toán rời rạc: 2011-2012 Đồ thị phân đôi Bipartite graph:  Các đỉnh của 1 đồ thị chia làm 2 tập con. Mỗi cạnh nối 1 đỉnh từ tập này đến 1 đỉnh ở tập kia. Ví dụ: Quan hệ hôn nhân trong một làng, gồm 2 tập con là phái nam và phái nữ. Quan hệ “gán” giữa danh sách các công việc và danh sách các nhân viên. Chương 6: Đồ thị 25 Toán rời rạc: 2011-2012 Đồ thị phân đôi Định nghĩa: G = (V, E)  và  Chương 6: Đồ thị 26  212121 ,, VVVVVVV 21,,),( VvVuEvu  Toán rời rạc: 2011-2012 Đồ thị phân đôi Đồ thị phân đôi đầy đủ (complete bipartite): G = (V, E) là phân đôi đầy đủ nếu G là đồ thị phân đôi.   Kí hiệu: Km,n với |V1| = m, |V2| = n Chương 6: Đồ thị 27 EvuVvVu  ),(,, 21 K3,3 K3,4 Toán rời rạc: 2011-2012 Đồ thị phân đôi Chương 6: Đồ thị 28 K12,12 Toán rời rạc: 2011-2012 Đồ thị đều Regular graph: đồ thị đơn được gọi là đều nếu Ví dụ: Chương 6: Đồ thị 29 Vvuvdegudeg  ,),()( Toán rời rạc: 2011-2012 Đồ thị bù Complementary graph: Cho đồ thị đơn G = (V, E). Đồ thị bù G = (V, E) của G được định nghĩa như sau: Ví dụ: Chương 6: Đồ thị 30 ), FW }),(|),{( EvuVvVuvuF VW   GG Toán rời rạc: 2011-2012 Tạo đồ thị mới từ đồ thị cũ Đồ thị con (subgraph) của G = (V, E) là đồ thị H = (W, F), trong đó W⊆V, F⊆E. Cho 2 đồ thị và Định nghĩa Chương 6: Đồ thị 31 ),( ),( ),( 212121 222111 EEVVGG EVGEVG   Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Biểu diễn đồ thị trong máy tính Toán rời rạc: 2011-2012 Các cách biểu diễn 1. Danh sách cạnh kề (adjacency list). 2. Ma trận đỉnh kề (adjacency matrix). 3. Ma trận cạnh kề (incidence matrix). Chương 6: Đồ thị 33 Toán rời rạc: 2011-2012 Danh sách cạnh kề (adjacency list) Chương 6: Đồ thị 34 Toán rời rạc: 2011-2012 Ma trận đỉnh kề (adjacency matrix) Cho đồ thị G = (V, E). Ma trận đỉnh kề AG  Kích thước: |V|* |V| Giá trị các phần tử: Chương 6: Đồ thị 35      otherwise if 0 ),( 1 Evv a ji ij Toán rời rạc: 2011-2012 Ma trận cạnh kề (incidence matrix) Cho đồ thị G = (V, E). Ma trận cạnh kề MG  Kích thước: |V|* |E| Giá trị các phần tử: Chương 6: Đồ thị 36     otherwise with incident if 0 1 ii ij ve m