Ich habe ein Diagramm und muss einen minimalen Spannbaum für ein bestimmtes Diagramm finden. Was ist zu tun, damit die erhaltene Ausgabe ein Binärbaum ist?
8
Ich habe ein Diagramm und muss einen minimalen Spannbaum für ein bestimmtes Diagramm finden. Was ist zu tun, damit die erhaltene Ausgabe ein Binärbaum ist?
Antworten:
Es ist nichts zu tun: Lassen Sie zum Beispiel den Sterngraphen mit Blättern bezeichnen. Der Graph hat einen eindeutigen Spannbaum (der S_k selbst ist) und einen Scheitelpunkt mit dem Grad genau k .Sk k Sk Sk k
Tatsächlich ist das allgemeine Problem , einen gradbeschränkten minimalen Spannbaum zu finden, NP-vollständig.
quelle