Cây bao trùm là một tập hợp con của đồ thị G, có tất cả các đỉnh được phủ với số cạnh tối thiểu có thể. Do đó, một cây bao trùm không có chu kỳ và nó không thể bị ngắt kết nối ..
Theo định nghĩa này, chúng ta có thể rút ra một kết luận rằng mọi Đồ thị G được kết nối và không bị chặn đều có ít nhất một cây bao trùm. Một biểu đồ bị ngắt kết nối không có bất kỳ cây bao trùm nào, vì nó không thể được kéo dài đến tất cả các đỉnh của nó.
Chúng tôi tìm thấy ba cây bao trùm từ một đồ thị hoàn chỉnh. Một đồ thị vô hướng hoàn chỉnh có thể có tối đa n n-2 số cây bao trùm, trong đó n là số nút. Trong ví dụ được đề cập ở trên, n là 3, do đó 3 3−2 = 3 cây bao trùm là có thể.
Đặc tính chung của cây Spanning
Bây giờ chúng ta hiểu rằng một biểu đồ có thể có nhiều hơn một cây bao trùm. Sau đây là một vài thuộc tính của cây bao trùm được kết nối với biểu đồ G -
- Một đồ thị G được kết nối có thể có nhiều hơn một cây bao trùm.
- Tất cả các cây bao trùm có thể của đồ thị G, có cùng số cạnh và đỉnh.
- Cây bao trùm không có bất kỳ chu kỳ (vòng lặp).
- Loại bỏ một cạnh khỏi cây bao trùm sẽ làm cho biểu đồ bị ngắt kết nối, tức là cây bao trùm được kết nối tối thiểu .
- Thêm một cạnh vào cây bao trùm sẽ tạo ra một mạch hoặc vòng lặp, tức là cây bao trùm có tính chu kỳ tối đa .
Tính chất toán học của cây Spanning
- Cây kéo dài có n-1 cạnh, trong đó n là số nút (đỉnh).
- Từ một biểu đồ hoàn chỉnh, bằng cách loại bỏ các cạnh e - n + 1 tối đa , chúng ta có thể xây dựng một cây bao trùm.
- Một đồ thị hoàn chỉnh có thể có tối đa n n-2 số cây bao trùm.
Do đó, chúng ta có thể kết luận rằng các cây bao trùm là một tập hợp con của Biểu đồ G được kết nối và các biểu đồ bị ngắt kết nối không có cây bao trùm.
Ứng dụng của Spanning Tree
Cây Spanning về cơ bản được sử dụng để tìm một đường dẫn tối thiểu để kết nối tất cả các nút trong biểu đồ. Ứng dụng phổ biến của cây bao trùm là -
- Quy hoạch mạng lưới dân sự
- Giao thức định tuyến mạng máy tính
- Phân tích cluster
Hãy để chúng tôi hiểu điều này thông qua một ví dụ nhỏ. Hãy xem xét, mạng thành phố như một biểu đồ khổng lồ và hiện có kế hoạch triển khai các đường dây điện thoại theo cách mà trong các đường tối thiểu chúng ta có thể kết nối với tất cả các nút của thành phố. Đây là nơi cây bao trùm đi vào hình ảnh.
Cây Spanning tối thiểu (MST)
Trong biểu đồ có trọng số, cây bao trùm tối thiểu là cây bao trùm có trọng lượng tối thiểu hơn tất cả các cây bao trùm khác của cùng biểu đồ. Trong các tình huống trong thế giới thực, trọng số này có thể được đo bằng khoảng cách, tắc nghẽn, tải lưu lượng hoặc bất kỳ giá trị tùy ý nào được biểu thị cho các cạnh.
Được cập nhật: 15 tháng 4 lúc 15:45:11 | Lượt xem: 521
