M
Jester schrieb:
Magst Du es trotzdem noch auflösen?
Gerne. Da niemand etwas eingereicht hat, hat mir die Motivation gefehlt, eine Lösung zu schreiben, die im Zweifel niemanden interessiert. Freut mich, dass es nicht so ist.
Für alle, die keine Erfahrung mit Beweisen haben: Schnappt euch ein Blatt Papier und malt das Geschehen auf. Die Beweise sind nicht schwer.
Meine Motivation kommt daher, dass ich gefragt wurde, wie man einen Independency Tree, also einen Spannbaum mit paarweise nicht benachbarten Blättern, in Linearzeit berechnet. Dieser existiert immer, wenn der Graph nicht gerade ein Kreis, der vollständige Graph oder der vollständige bipartite Graph mit gleich großen Seiten ist. Netterweise lösen Independency Trees unser Problem, wenn man den Weihnachtsmann in einem Blatt starten lässt.
Ein simpler Algorithmus mit quadratischer Laufzeit (für unser Problem) lässt sich direkt dem Paper entnehmen: Starte mit einem beliebigen Spannbaum T und betrachte zwei Blätter v und w, die im Originalgraphen benachbart sind. Dann enthält T zusammen mit der Kante {u,v} (im Folgenden T + {u,v}) einen Kreis C, und wenn es sich nicht gerade um einen Hamiltonkreis handelt (also ein Kreis, der alle Knoten enthält, womit wir uns zufrieden geben), dann gibt es einen Knoten w im Kreis C mit mindestens Grad 3 bzgl. T + {u,v}. Löschen wir eine der zu w inzidenten Kreiskanten aus T + {u,v}, so erhalten wir wieder einen Spannbaum, aber die Anzahl der Blätter hat sich reduziert, weil u und v durch das Hinzufügen von {u,v} keine Blätter mehr sind und beim anschließenden Löschen höchstens ein Blatt hinzukommt, weil w kein Blatt werden kann. Das bedeutet, dass wir nach höchstens n solcher Austauschaktionen einen Hamiltonkreis oder einen Independency Tree gefunden haben, weil die Anzahl der Blätter nicht negativ werden kann. Für jeden Tausch benötigen wir lineare Laufzeit, was bei maximal n Austauschaktionen quadratische Laufzeit ergibt.
Nun wollen wir ja aber lineare Laufzeit und keine quadratische. Also starten wir mit einem Tiefensuchbaum T, weil bei diesem, wie du bereits erwähnt hast, zwei Blätter, die nicht gerade die Wurzel sind, nicht benachbart sein können. Also ist das einzige problematische Blatt die Wurzel r, falls diese denn ein Blatt ist. Sei u ein anderes Blatt, das zu r im Originalgraphen benachbart ist. Wir führen nun dieselbe Austauschaktion durch wie vorher, nur passen wir auf, dass das neu entstehende Blatt zu keinem anderen Blatt benachbart ist. Dann reicht insgesamt ein Tausch aus. Mit der Suche nach einem passenden Knoten w in dem Kreis in T + {r,u} starten wir im Blatt u und gehen den u-r-Weg in T nach oben, bis wir den ersten Knoten w mit Grad mindestens 3 gefunden haben. Sei {v,w} die letzte dabei benutzte Kante. Dann ist T' := T + {r,u} - {v,w} wieder ein Spannbaum und v ist ein Blatt von T'. Wir müssen nur noch zeigen, dass v zu keinem anderen Blatt von T' benachbart ist. Sei l ein solches Blatt. Zum Zeitpunkt, als die Tiefensuche l gefunden hat, war v auf dem Stack, denn wäre v noch nicht bekannt gewesen, so wäre l kein Blatt, weil v dranhängen würde, und v kann nicht vom Stack entfernt werden, bevor alle Nachbarn, insbesondere l, gefunden wurden. Also ist l im Subbaum von v bzgl. T. Aber v und w sind gerade so gewählt, dass der Subbaum von v ein einfacher Pfad ist und somit gibt es dort keine weiteren Blätter außer u. Nun ist aber u = v oder u ist kein Blatt mehr, was ein Widerspruch zur Wahl von l ist.
In Code gegossen, sieht das so aus (ich hoffe, das ist die richtige Version):
enum class VisitedState
{
unfound,
found
};
vector<Street> helpSanta(size_t numberOfHouses, const vector<Street>& streets)
{
if(numberOfHouses <= 1)
return {};
vector<vector<size_t> > neighbors(numberOfHouses);
for(const auto& edge : streets)
{
neighbors[edge.startId].push_back(edge.endId);
neighbors[edge.endId].push_back(edge.startId);
}
vector<VisitedState> visited(numberOfHouses, VisitedState::unfound);
vector<size_t> predecessor(numberOfHouses, -1);
stack<size_t> callStack;
callStack.push(0); // Wurzel
size_t numberOfNonRootLeaves = 0;
size_t criticalLeaf = -1; // Blatt, das mit der Wurzel benachbart ist
vector<Street> tree;
vector<size_t> position(numberOfHouses, -1);
size_t rootDegree = 0;
while(!callStack.empty()) // Tiefensuche, merke dir die Vorgänger jedes Knotens
{
auto vertex = callStack.top();
callStack.pop();
if(visited[vertex] == VisitedState::unfound)
{
if(vertex != 0) // Die Wurzel hat keinen Vorgänger
{
tree.push_back({vertex, predecessor[vertex]});
if(predecessor[vertex] == 0)
++rootDegree;
}
visited[vertex] = VisitedState::found;
position[vertex] = tree.size();
bool isLeaf = true;
for(auto neighbor : neighbors[vertex])
{
if(visited[neighbor] == VisitedState::unfound)
{
predecessor[neighbor] = vertex;
callStack.push(neighbor);
isLeaf = false;
}
}
if(isLeaf)
{
++numberOfNonRootLeaves;
if(criticalLeaf == -1 && find(begin(neighbors[vertex]), end(neighbors[vertex]), 0) != end(neighbors[vertex]))
criticalLeaf = vertex;
}
}
}
if(tree.size() != numberOfHouses - 1) // Graph nicht zusammenhängend
return {};
if(numberOfNonRootLeaves == 1) // Hamiltonpfad
return tree;
if(rootDegree >= 2) // Wurzel ist kein Blatt => alle Blätter nicht benachbart
return tree;
if(criticalLeaf == -1) // Es gibt kein Blatt, das mit der Wurzel benachbart ist
return tree;
vector<size_t> degree(numberOfHouses, 0); // Grad bzgl. des gefundenen Baums
for(auto edge : tree)
{
++degree[edge.startId];
++degree[edge.endId];
}
assert(degree[criticalLeaf] == 1);
// Finde ersten Knoten auf criticalLeaf-Wurzel-Pfad mit Grad >= 3 und tausche Kanten aus.
size_t father = predecessor[criticalLeaf];
size_t son = criticalLeaf;
while(degree[father] == 2)
{
son = father;
father = predecessor[father];
}
tree[position[son] - 1] = {0, criticalLeaf};
return tree;
}
Man kann übrigens auch, wie im Paper angedeutet (so richtig klar wird es dort finde ich nicht, wie man es machen soll), zuerst einen passenden Pfad suchen und dann bei der Tiefensuche mit genau diesem Pfad anfangen, sodass die Wurzel der Tiefensuche von Anfang an nicht mit den Blättern benachbart sein kann. Grobe Skizze: Starte von einem beliebigen Knoten u aus einen möglichst langen Pfad P_1 in beliebige Richtung. Sei v der Endknoten von P_1. Dann sind alle Nachbarn von v in P_1. Starte dann ebenfalls von u aus einen zweiten möglichst langen Pfad P_2 in eine andere Richtung, sodass kein Knoten aus P_1 nochmals besucht wird, und sei w der Endknoten dieses Pfades. Wenn v und w nicht benachbart sind, können wir unsere Tiefensuche in w starten, weil alle Nachbarn von w in P_1 + P_2 liegen und alle diese Knoten außer v keine Blätter sein können. Wenn v und w allerdings benachbart sind, gehe von v rückwärts entlang P_1, bis man anders abbiegen kann. Folge dann der neuen Richtung wieder so weit wie möglich. Dann muss man auch von w aus wieder den Pfad so weit wie möglich verlängern. Dann weiß man sicher, dass die neuen Endknoten der Pfade nicht benachbart sind, weil das P_2-Ende in der Knotenmenge von P_1 + P_2 bleibt, aber das P_1-Ende nicht in dieser Knotenmenge liegt.
Problem aller bisherigen Beschreibungen war immer, wenn man zufällig einen Hamiltonkreis gefunden hat. Das bedeutet noch nicht, dass es keinen Independency Tree gibt, aber es gibt dann tatsächlich nur genau dann einen, wenn es einen Hamiltonpfad (also einen Pfad, der alle Knoten enthält) mit nicht benachbarten Endknoten gibt, was genau dann der Fall ist, wenn keiner der oben genannten drei Spezialfälle eintritt. Dieser Hamiltonpfad ist dann auch direkt ein Independency Tree. Die Existenz ist nicht direkt ersichtlich, weshalb ich die Sonderregel mit dem Hamiltonkreis in die Aufgabe eingefügt habe. Wie man außerhalb der Spezialfälle von dem gefundenen Hamiltonkreis in Linearzeit zu einem Hamiltonpfad mit nicht benachbarten Endknoten kommt, erspare ich mir, wenn keiner explizit danach fragt, aber im Prinzip ist es das sorgfältige Anwenden des Beweises aus dem Paper.
