Umwandlung einer willkürlichen Abdeckung in eine Scheitelpunktabdeckung

Question

Vorgegeben ist ein Planargraf, $ g = (v, e) $ und $ mathcal {g} $ seine Einbettung in die Ebene bezeichnen jede Kante hat eine Länge $ $ $. Ich habe außerdem einen Satz $ c $ von Punkten, bei denen jeder Punkt $ C in C $ in $ mathcal {g} $ enthalten ist. Darüber hinaus gilt es für jeden Punkt $ p $ in $ mathcal {g} $, dass es einen $ c in c $ mit geodätischer Distanz auf $ p $ höchstens eins gibt. (Die Entfernung wird als kürzeste Entfernung innerhalb von $ mathcal {g} $ gemessen.)

Ich möchte argumentieren, dass ich angesichts einer $ c $, für die die obige Bedingung gilt, sie leicht in eine Scheitelpunktabdeckung verwandeln oder anders in ein $ C '$ von gleichen Cardinality steger $ C in C verwandeln kann. $ wird in $ mathcal {g} $ bei einem Scheitelpunkt von $ g $ platziert und $ C '$ deckt immer noch $ g $ ab.

Mein Ansatz war es, die Kanten zu orientieren und die Punkte am Ende des Bogens in $ C $ zu verschieben. Aber bisher habe ich keine korrekte Orientierung gefunden, die C '$ von $ C $ liefert.

Hat jemand eine Idee?

Answer 1

Wenn keine Punkte in $ c $ genau auf dem Mittelpunkt eines Vorsprung in $ mathcal {g} $ liegen, reicht es aus, jeden Punkt in $ c $ dem nächsten Scheitelpunkt in $ mathcal {g} $ zu verknüpfen. Ich werde es dem Leser als Übung überlassen, um dies zu beweisen (Hinweis: Nachweis durch Widerspruch).

Wenn dagegen Punkte in $ C $ am Mittelpunkt der Kanten liegen dürfen, können wir ein Gegenbeispiel bereitstellen:

Die blauen Linien und Kreise sind $ mathcal {g} $ und die roten Kreuze sind $ C $.

Bearbeitet zum Hinzufügen: Ein Beispiel mit einer bikonbeierten Grafik