Đồ thị con T của đồ thị liên thông G được gọi là spanning tree của G nếu T là cây và T bao gồm tất cả các đỉnh của G.
Spanning Tree là gì?
Spanning Tree (cây khung) là một khái niệm trong lý thuyết đồ thị, đặc biệt được áp dụng trong mạng máy tính. Nó là một cây con của một đồ thị liên thông, bao gồm tất cả các đỉnh của đồ thị gốc, nhưng không có chu kỳ. Một cây khung được tạo thành bằng cách loại bỏ các cạnh từ đồ thị gốc để tạo ra một cấu trúc cây.
Cây khung có nhiều ứng dụng quan trọng trong mạng máy tính và viễn thông. Nó được sử dụng để tối ưu hóa đường truyền dữ liệu, đảm bảo tính linh hoạt và ổn định của mạng, giảm thiểu tắc nghẽn và tiết kiệm băng thông. Thuật toán tìm cây khung nhỏ nhất (Minimum Spanning Tree) như Prim và Kruskal được sử dụng để xây dựng cây khung tối ưu dựa trên trọng số của các cạnh trong đồ thị.
Cây khung đảm bảo rằng mỗi đỉnh trong đồ thị được kết nối với nhau theo một cách duy nhất, đồng thời loại bỏ các chu kỳ và tạo ra một mạng phân cấp với cấu trúc hợp lý.
Cây Khung trong đồ thị
Cây khung (Spanning Tree) trong đồ thị là một cây con của đồ thị gốc mà bao gồm tất cả các đỉnh của đồ thị và là một cấu trúc không có chu kỳ. Cây khung được tạo ra bằng cách loại bỏ các cạnh từ đồ thị gốc để tạo ra một cấu trúc cây.
Cây khung có một số tính chất quan trọng:
- Cây khung bao gồm tất cả các đỉnh của đồ thị gốc: Mỗi đỉnh trong đồ thị được kết nối với ít nhất một đỉnh khác trong cây khung.
- Cây khung không có chu kỳ: Không có đường đi nào trong cây khung có thể tạo thành chu kỳ. Điều này đảm bảo tính cây và tính chất phân cấp của cây khung.
- Cây khung là một cây con của đồ thị gốc: Tất cả các đỉnh trong cây khung được kết nối với nhau bởi các cạnh không tạo thành chu kỳ.
Cây khung có nhiều ứng dụng trong lý thuyết đồ thị và các lĩnh vực liên quan. Trong mạng máy tính, cây khung được sử dụng để tối ưu hóa đường truyền dữ liệu, giảm thiểu tắc nghẽn và tăng tính linh hoạt của mạng. Các thuật toán tìm cây khung nhỏ nhất (Minimum Spanning Tree) như Prim và Kruskal được sử dụng để xây dựng cây khung tối ưu dựa trên trọng số của các cạnh trong đồ thị.
Thuật toán Prim cho việc tạo Cây Khung
Thuật toán Prim là một thuật toán được sử dụng để tạo cây khung nhỏ nhất (Minimum Spanning Tree) trong một đồ thị có trọng số. Thuật toán bắt đầu từ một đỉnh bất kỳ và mở rộng cây khung bằng cách thêm cạnh có trọng số nhỏ nhất kết nối từ cây khung hiện tại đến một đỉnh chưa được thăm. Quá trình này được lặp lại cho đến khi tất cả các đỉnh trong đồ thị được bao gồm trong cây khung.
Dưới đây là thuật toán Prim cho việc tạo cây khung:
- Khởi tạo cây khung ban đầu với một đỉnh bất kỳ.
- Tạo một hàng đợi ưu tiên để lưu trữ các cạnh kết nối từ cây khung hiện tại đến các đỉnh chưa được thăm, sắp xếp theo trọng số tăng dần.
- Lặp cho đến khi hàng đợi ưu tiên trống: a. Lấy cạnh có trọng số nhỏ nhất từ hàng đợi ưu tiên. b. Kiểm tra xem đỉnh đích của cạnh đã được thăm hay chưa. Nếu chưa, thêm cạnh vào cây khung và đánh dấu đỉnh đích đã được thăm. c. Thêm tất cả các cạnh kết nối từ đỉnh đích vào hàng đợi ưu tiên.
- Trả về cây khung đã tạo.
Thuật toán Prim đảm bảo rằng cây khung tạo ra là cây khung nhỏ nhất với tổng trọng số các cạnh là nhỏ nhất. Nó hoạt động tốt trên đồ thị dạng đầy đủ và đồ thị liên thông. Độ phức tạp của thuật toán Prim là O(E log V), trong đó E là số cạnh của đồ thị và V là số đỉnh của đồ thị.
Thuật toán Kruskal cho việc tạo Cây Khung
Thuật toán Kruskal là một thuật toán được sử dụng để tạo cây khung nhỏ nhất (Minimum Spanning Tree) trong một đồ thị có trọng số. Đặc điểm nổi bật của thuật toán Kruskal là nó hoạt động dựa trên việc xét các cạnh của đồ thị theo thứ tự không giảm của trọng số và kết hợp các cạnh này vào cây khung nếu không tạo thành chu trình.
Dưới đây là thuật toán Kruskal cho việc tạo cây khung:
- Sắp xếp tất cả các cạnh của đồ thị theo thứ tự không giảm của trọng số.
- Khởi tạo một cây khung rỗng.
- Lặp qua từng cạnh theo thứ tự đã sắp xếp: a. Kiểm tra xem việc thêm cạnh vào cây khung có tạo thành chu trình hay không. Nếu không tạo thành chu trình, thêm cạnh vào cây khung. b. Nếu cây khung đã chứa đủ (số đỉnh – 1) cạnh, thoát khỏi vòng lặp.
- Trả về cây khung đã tạo.
Thuật toán Kruskal tạo ra cây khung nhỏ nhất bằng cách kết hợp các cạnh có trọng số nhỏ nhất mà không tạo thành chu trình. Độ phức tạp của thuật toán Kruskal là O(E log V), trong đó E là số cạnh của đồ thị và V là số đỉnh của đồ thị. Thuật toán Kruskal hoạt động tốt trên đồ thị có trọng số không âm và không yêu cầu đồ thị liên thông.
Minimum Spanning Tree
Giả sử G là một đồ thị trọng số liên thông, tức là mỗi cạnh của G được gán một số không âm được gọi là trọng số của cạnh, khi đó bất kỳ cây khung T nào của G cũng được gán tổng trọng số thu được bằng cách cộng trọng số của cạnh trong T.
spanning tree tối thiểu của G là cây có tổng trọng lượng càng nhỏ càng tốt.
- Thuật toán Kruskal để tìm spanning tree tối thiểu: Thuật toán này tìm spanning tree tối thiểu T của đồ thị có trọng số liên thông đã cho.
- Nhập vào đồ thị có trọng số liên thông đã cho G với n đỉnh có cây khung nhỏ nhất T, chúng ta muốn tìm.
- Thứ tự tất cả các cạnh của đồ thị G theo trọng số tăng dần.
- Khởi tạo T với tất cả các đỉnh nhưng có bao gồm một cạnh.
Thêm từng đồ thị G trong T không tạo thành chu trình cho đến khi thêm n-1 cạnh.
Ví dụ 1: Xác định cây khung nhỏ nhất của đồ thị có trọng số được hiển thị trong hình:
Giải pháp: Sử dụng thuật toán kruskal sắp xếp tất cả các cạnh của đồ thị có trọng số theo thứ tự tăng dần và khởi tạo cây khung T với tất cả sáu đỉnh của G. Bây giờ bắt đầu thêm các cạnh của G trong T không tạo thành chu trình và có trọng số tối thiểu cho đến năm các cạnh không được thêm vào vì có sáu đỉnh.
Cạnh Trọng lượng được Thêm hay Không
Bước 1:
Bước 2:
Bước 3:
Bước 4:
Bước 5:
Bước 6: Cạnh (A, B), (D, E) và (E, F) bị loại bỏ vì chúng sẽ tạo thành chu trình trong đồ thị.
Vì vậy, dạng spanning tree tối thiểu trong bước 5 là đầu ra và tổng chi phí là 18.
Ví dụ 2: Tìm tất cả cây khung của đồ thị G và tìm cây nào là cây khung nhỏ nhất của G được thể hiện trong hình:
Giải: Có tổng cộng ba cây khung của biểu đồ G được thể hiện trong hình:
Để tìm spanning tree tối thiểu, hãy sử dụng THUẬT TOÁN CỦA KRUSKAL. spanning tree tối thiểu được hiển thị trong hình:
Cái đầu tiên là khung tối thiểu có trọng lượng tối thiểu = 11.
Xem thêm Adversarial Search trong AI
Ứng dụng của Spanning Tree
Cây khung (Spanning Tree) là một khái niệm quan trọng trong lĩnh vực đồ thị và có nhiều ứng dụng thực tế. Dưới đây là một số ứng dụng phổ biến của cây khung:
- Mạng máy tính: Trong mạng máy tính, cây khung được sử dụng để tối ưu hóa việc truyền thông giữa các thiết bị mạng. Cây khung giúp giảm thiểu chi phí truyền thông bằng cách chỉ duy nhất một đường đi giữa các thiết bị mạng.
- Điện lưới: Trong ngành điện, cây khung được sử dụng để tối ưu hóa việc truyền tải điện năng giữa các trạm điện và khách hàng. Cây khung giúp giảm thiểu chi phí xây dựng và vận hành hệ thống điện lưới.
- Mạng giao thông: Trong hệ thống giao thông, cây khung được sử dụng để tối ưu hóa việc kết nối giữa các đường giao thông. Cây khung giúp giảm thiểu thời gian di chuyển và tăng hiệu quả giao thông.
- Mạng xã hội: Trong mạng xã hội và phân tích mạng xã hội, cây khung được sử dụng để phân tích mối quan hệ và kết nối giữa các thành viên trong mạng. Cây khung giúp hiểu rõ hơn về cấu trúc mạng xã hội và tìm ra những thành viên quan trọng trong mạng.
- Khoa học dữ liệu: Trong lĩnh vực khoa học dữ liệu, cây khung được sử dụng để tối ưu hóa việc phân cụm và phân tích dữ liệu. Cây khung giúp tạo ra nhóm dữ liệu có liên quan và giảm thiểu độ phức tạp của quá trình phân tích.
- Truyền thông: Trong truyền thông, cây khung được sử dụng để xây dựng cấu trúc dữ liệu để lưu trữ và truyền tải thông tin. Cây khung giúp tối ưu hóa việc truyền thông và quản lý dữ liệu.
Những ứng dụng trên chỉ là một số ví dụ cơ bản về sự ứng dụng của cây khung. Cây khung có thể được áp dụng rộng rãi trong nhiều lĩnh vực khác nhau tùy thuộc vào yêu cầu và bối cảnh cụ thể của từng vấn đề.
Xem thêm Switch là gì?
