Với một đồ thị có hướng với các cạnh có trọng số, thuật toán nào có thể được sử dụng để cung cấp cho một đồ thị phụ có trọng lượng tối thiểu. (theo giả thiết rằng đường đi giữa hai đỉnh bất kỳ luôn tồn tại).Một cây bao trùm tối thiểu hai chiều của một đồ thị có hướng
Thuật toán có tồn tại không?
Điều này có vẻ là NP-Hard: Trọng lượng tối thiểu được kết nối chặt chẽ với biểu đồ đường con.
Tôi tin rằng vấn đề chu trình Hamilton có thể giảm xuống: Cho đồ thị G (V, E), xây dựng một bản đồ DG với trọng số 1 cho các cạnh xuất hiện và trọng lượng 100 (| V | +1) 't. DG có trọng số tối thiểu được kết nối chặt chẽ với biểu đồ chính xác trọng lượng | V | nếu và chỉ khi G có chu kỳ hamiltonian.
Bài báo ở đây có thuật toán xấp xỉ: http://portal.acm.org/citation.cfm?id=844363
Mặc dù họ đã không đúng bản thân, dành thời gian để theo các liên kết Wikipedia Vitalii nhanh chóng phát hiện ra thuật toán này:
http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm
Chia mỗi nút trong đồ thị dưới thành hai nút. Một nút sẽ chấp nhận tất cả các cạnh đến của nút gốc và nút kia sẽ có tất cả các cạnh đi. Sau đó, thả hướng trên tất cả các cạnh, vì vậy biểu đồ không bị hướng. Sau đó, bạn có thể chạy một thuật toán MST chuẩn trên đồ thị (Prim's, Kruskal's) và bạn sẽ đảm bảo rằng mọi nút gốc có thể được chuyển đến bởi tất cả các nút gốc khác.
Thật không may điều này sẽ không hoạt động, vì nó sẽ thêm các cạnh không cần thiết vào đồ thị cuối cùng. Ít nhất một nút sẽ có thêm cạnh gắn liền với nó, ngay cả khi nó không cần phải có cạnh đó. Ví dụ, trong đồ thị có đỉnh A, B, C và cạnh AB, BA, BC, CB, AC, CA, khoảng cách tối thiểu của biểu đồ có thể chỉ là các cạnh AB, BC, CA. Nhưng sử dụng phương pháp của bạn, 3 cạnh đó sẽ không được gắn vào nhau, và các cạnh bổ sung sẽ cần phải được thêm vào để hoàn thành MST. –
Chọn bất kỳ nút nào và trả lại.
Bạn có lẽ có nghĩa là tìm ra lớn mạnh kết nối đồ thị con (ít nhất là số nút loại bỏ càng tốt), hoặc tối thiểu trọng lượng kéo dài đồ thị con (không gỡ bỏ nút cho phép)?
Tiêu đề nói 'cây bao trùm', vì vậy tôi giả sử cái sau. –
@Moron: Ah, tôi đã bỏ lỡ điều đó :) trong trường hợp đó, câu trả lời của bạn là chính xác. –
Đây là Cây Steiner được chỉ định sự cố. Là cây Steiner, đó là NP-Hard.
Bạn có thể tìm thấy một số thuật toán aproximate đây: Thuật toán
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.8774&rep=rep1&type=ps
Nhưng một cây Steiner chỉ đạo đòi hỏi một gốc, phải không? – highBandWidth
Đỉnh gốc tối ưu có thể được tìm thấy bởi các thuật toán nhưng bạn có thể chỉ định một gốc cùng với tập đỉnh. – jwinandy
Edmond của chỉ đảm bảo rằng tất cả các nút trong một đồ thị có thể truy cập từ gốc, không phải là mỗi nút sẽ có thể truy cập từ tất cả các nút khác. –
Đây là NP-Hard. -1. –
Phân loại NP của liên kết của tôi có liên quan gì đến sự liên quan của nó với câu hỏi gốc? – Mathew