spannender Baum mit genau k farbigen Kanten

Question

Ich habe einen verbundenen, ungerichteten Graphen mit Kanten, die entweder schwarz oder weiß sind, und eine ganze Zahl k. Ich versuche einen Algorithmus zu schreiben, der sagt, ob ein spannender Baum mit genau k schwarzen Kanten existiert (muss nicht unbedingt den tatsächlichen Baum finden).

Ich benutzte Kruskal-Algorithmus, um die minimale und maximale Anzahl der schwarzen Kanten in einem Spannbaum zu finden. Wenn k außerhalb dieses Bereichs liegt, kann kein aufspannender Baum mit k Kanten existieren.

Aber ich habe Schwierigkeiten, mich Gedanken darüber zu machen, ob es für jedes k in diesem Bereich notwendigerweise einen Spannbaum gibt. Meine Intuition sagt ja, und es funktioniert für jedes Beispiel, das ich versucht habe, aber ich kann nicht herausfinden, wie ich es beweisen soll.

Irgendwelche Ratschläge? Danke im Voraus.

Answer 1

Sei G_min = Spannbaum mit der minimalen Anzahl schwarzer Kanten.

Sei G_max = Spannbaum mit der maximalen Anzahl schwarzer Kanten.

Let k_min = Anzahl der schwarzen Ränder in g_min

Lassen k_max = Anzahl der schwarzen Ränder in g_max

Der Beweis geht wie folgt. Setze G = G_min. Wiederholen Sie dies für jeden schwarzen Rand in g_max:

1) If the edge is already in G, do nothing. 
    2) If the edge is not in G, add it to G and remove another edge 
    from the cycle thus induced in G. Remove one not in G_max. 

Schritt 2 immer möglich ist, weil es zumindest eine Kante nicht in g_max in jedem Zyklus ist.

Dieser Algorithmus behält die Spanning-Tree-Ness von G bei, wie es geht. Es fügt höchstens eine schwarze Kante pro Schritt hinzu, also zeigt G einen aufspannenden Baum mit k schwarzen Kanten für alle k zwischen k_min und k_max, wie es geht.

Answer 2

Kruskals finden Sie die minimale Wight Spanning Tree - so Gmin zu finden, müssen Sie dies anders herum tun. gmin = Fall alle schwarzen Kanten geben der Wight 1 und die weiße die Wight 0. Die Art, wie der Algorithmus zuerst alle weißen Kanten und dann die schwarzen verwendet. Auf diese Weise erhalten wir Gmin.