Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 6: Cây và cây khung của đồ thị

Chương 6 cung cấp cho người học những kiến thức về cây và cây khung của đồ thị. Chương này giúp người học có những hiểu biết về cây và các tính chất cơ bản của cây, cây khung của đồ thị, bài toán tìm cây khung nhỏ nhất. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 6: Cây và cây khung của đồ thị Chương 6. Cây và cây khung của đồ thị1. CÂY VÀ CÁC TÍNH CHẤT CƠ BẢN CỦA CÂY Định nghĩa1.Ta gọi cây là đồ thị vô hướng liên thông không có chu trình. Đồ thị không cóchu trình được gọi là rừng.Như vậy, rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây.Thí dụ 1. Trong hình 1 là một rừng gồm 3 cây T1, T2, T3. Hình 1. Rừng gồm 3 cây T1, T2, T3.Có thể nói cây là đồ thị vô hướng đơn giản nhất. Định lý sau đây cho ta mộtsố tính chất của cây. Định lý 1. Giả sử G=(V,E) là đồ thị vô hướng n đỉnh. Khi đó các mệnh đềsau đây là tương đương: (1) T là cây; (2) T không chứa chu trình và có n-1 cạnh; (3) T liên thông và có n-1 cạnh; (4) T liên thông và mỗi cạnh của nó đều là cầu; (5) Hai đỉnh bất kỳ của T được nối với nhau bởi đúng một đường đi đơn; (6) T không chứa chu trình nhưng hễ cứ thêm vào một cạnh ta thu được đúng một chu trình.2. CÂY KHUNG CỦA ĐỒ THỊ Định nghĩa 2. Cho đồ thị vô hướng liên thông G=(V,E) cây khungT=(VT,ET) của nó được xác định như sau:  Tập đỉnh của cây T cũng là tập đỉnh của đồ thị G. tức là: VT = V.  Tập cạnh của cây T là tập con của tập cạnh của đồ thị G. tức là: ET V.Nói cách khác, từ đồ thị G ta bỏ bớt các cạnh đi cho thành 1 cây, thì đó là mộtcây khung của đồ thị. Như vậy 1 đồ thị có thể có nhiều cây khung.Ví dụ: Hình 2. Đồ thị và 2 các cây khung của nó (nó còn có các cây khung khác)3. BÀI TOÁN TÌM CÂY KHUNG NHỎ NHẤT.Bài toán cây khung nhỏ nhất của đồ thị là một trong số những bài toán tối ưutrên đồ thị tìm được ứng dụng trong nhiều lĩnh vực khác nhau của đời sống.Trong mục này chúng ta trình bày những thuật toán cơ bản để giải bài toánnày. Trước hết chúng ta phát biểu nội dung bài toán.Cho G=(V,E) là đồ thị vô hướng liên thông. Mỗi cạnh e của đồ thị G được gánvới một trọng số không âm c(e), gọi là độ dài của nó. Giả sử T=(VT,ET) là câykhung của đồ thị G. Ta gọi độ dài c(T) của cây khung T là tổng độ dài cáccạnh của nó: c(T) =  c(e). e ETBài toán đặt ra là trong tất cả cây khung của đồ thị G hãy tìm cây khung vớiđộ dài nhỏ nhất. Cây khung như vậy như vậy được gọi là cây khung nhỏ nhấtcủa đồ thị và bài toán đặt ra được gọi là bài toán cây khung nhỏ nhất.Để minh hoạ cho những ứng dụng bài toán cây khung nhỏ nhất, dưới đây, taphát biểu hai mô hình thực tế tiêu biểu của nó. Bài toán xây dựng hệ thống đường sắt. Giả sử ta muốn xây dựng một hệthống đường sắt nối n thành phố sao cho hành khách có thể đi từ bất kỳ mộtthành phố nào đến bất kỳ một trong các thành phố còn lại. Mặt khác trên quanđiểm kinh tế đòi hỏi là chi phí xây dựng hệ thống đường phải nhỏ nhất. Rõràng đồ thị mà đỉnh là các thành phố còn các cạnh là các tuyến đường sắt nốicác thành phố tương ứng với phương án xây dựng tối ưu phải là cây. Vì vây,bài toán đặt ra dẫn về bài toán tìm cây khung nhỏ nhất trên đồ thị đầy đủ nđỉnh, mỗi đỉnh tương ứng với một thành phố, với độ dài trên các các cạnhchính là chi phí xây dựng đường ray nối hai thành phố tương ứng (chú ý làtrong bài toán này ta giả thiết là không xây dựng tuyến đường sắt có các nhàga phân tuyến nằm ngoài các thành phố). Bài toán nối mạng máy tính. Cần nối mạng một hệ thống gồm n máy tínhđánh số từ 1 đến n. Biết chi phí nối máy i với máy j là c[i,j], i,j = 1, 2, . . . ,n (thông thường chi phí này phụ thuộc vào độ dài cáp nối cần sử dụng). Hãy tìmcách nối mạng sao cho tổng chi phí nối mạng là nhỏ nhất. 3.1. Thuật toán KruskalCho đồ thị vô hướng liên thông có trọng số G=(V,E). Thuật tóan tìm ra câykhung nhỏ nhất Tmin=(Vmin,Emin). Các bước làm như sau:Bước khởi đầu: Tập đỉnh của cây Tmin là tập đỉnh của đồ thị G, tức là: Vmin = V. Tập cạnh của cây Tmin là rỗng: Emin = ước lặp: Mỗi lần lặp chọn 1 cạnh cho cây (Lặp lại cho đến khi chọn đủ sốcạnh bằng số đỉnh trừ 1) Xét cạnh có trọng số nhỏ nhất trong các cạnh chưa xét. Nếu cạnh này không tạo thành chu trình với các cạnh đã chọn trước đó, thì chọn nó vào cây. Ngược lại thì bỏ qua không chọn.Thí dụ 3.Tìm cây khung nhỏ nhất của đồ thị cho trong hình 3 dưới. Hình 3. Đồ thị để tìm cây khung nhỏ nhấtBước khởi tạo. Đặt Tmin= .Bước lặp:  Xét cạnh (3,5) chọn vào cây.  Xét cạnh (4,6) chọn vào cây.  Xét cạnh (4,5) chọn vào cây.  Xét cạnh (5,6) không chọn vào cây.  Xét cạnh (3,4) không chọn vào cây.  Xét cạnh (1,3) chọn vào cây.  Xét cạnh (2,3) chọn vào cây.Đã chọn đủ 5 cạnh, được Tmin =  (3,5) , (4,6) , (4,5) , (1,3) , (2,3)  Chính làtập cạnh của cây khung nhỏ nhất cần tìm. 3.2. Thuật toán PrimThuật toán Prim còn được gọi là phương pháp lân cận gần nhất. Trongphương pháp này bắt đầu từ một đỉnh tuỳ ý của đồ thị, đầu tiên ta nối s vớiđỉnh lân cận gần nó nhất, chẳng hạn là đỉnh y. Nghĩa là trong số các cạnh kềcủa đỉnh s, cạnh (s,y) có độ dài nhỏ nhất. Tiếp theo trong số các cạnh kề vớihai đỉnh s hoặc y ta tìm cạnh có độ dài nhỏ nhất, cạnh này dẫn đến đỉnh thứ baz, và ta thu được cây bộ phận gồm 3 đỉnh và 2 cạnh. Quá trình này sẽ tiếp tụccho đến khi ta thu được cây gồm tất cả các đỉnh của đồ thị, đó chính là câykhung nhỏ nhất cần tìm.Cho đồ thị vô hướng liên thông có trọng số G=(V,E). Thuật tóan tìm ra câykhung nhỏ nhất Tmin=(Vmin,Emin). Các bước làm như sau:Bước khởi đầu: Tập đỉnh của cây Tmin là 1 đỉnh tùy í s: Vmin = {s}. Tập cạnh của cây Tmin là rỗng: Emin = ước lặp: Mỗi lần lặp chọn 1 đỉnh và 1 cạnh cho cây (Lặp lại cho đến khichọn hết đỉnh của đồ thị) Tìm ra đỉnh gần cây Tmin hiện tại nhất. Thêm vào cây Tmin đỉnh này, và cạnh ngắn nhất nối đỉnh này với cây. Thí dụ 4.Tìm cây khung nhỏ nhất của đồ thị cho trong hình 3 dưới. Hình 3. Đồ thị để tìm cây khung nhỏ nhấtBước khởi tạo. Đặt Vmin= , Emin = Bước lặp:  Vmin= , Emin =   Vm ...