Graph Vertex Abdeckung - gleichen Grad Vertex Verwirrung

Question

Um das Diagramm Vertex Coverage Problem zu lösen, begann ich mit der Auswahl der Ecke v mit dem maximalen Grad und dann diese Ecke aus der Menge der Ecken zu löschen und auch die Kanten mit Endpunkt zu löschen als v. Ich hatte eine Frage, was passiert, wenn ich nach dem Löschen der obigen Eckpunkte und Kanten mehr als einen Eckpunkt mit dem gleichen Grad habe, welcher Eckpunkt wird mein Greedy-Algorithmus wählen?

Ich habe versucht, online zu suchen, konnte aber keine Vorschläge für das oben genannte Problem finden. Wenn jemand helfen kann. Danke

Answer 1

Krawatten können beliebig gebrochen werden. Zum Beispiel könnten Sie nach dem Zufallsprinzip wählen. Wenn Sie möchten, dass der Algorithmus deterministisch ist, könnten Sie zum Beispiel immer den ersten Eckpunkt auswählen, auf den Sie in Ihrer Datenstruktur stoßen, wo Ihre Eckpunkte gespeichert sind.