Umwandlung eines beliebigen Covers in ein Vertex-Cover

16

Gegeben sei ein ebener Graph und G bezeichne seine Einbettung in die Ebene st, wobei jede Kante die Länge 1 hat . Ich habe außerdem eine Menge C von Punkten, bei denen jeder Punkt c C in G enthalten ist . Weiterhin gilt für jeden Punkt p in G, dass es ein c C mit höchstens einem geodätischen Abstand zu p gibt . (Die Entfernung wird als kürzeste Entfernung innerhalb von G gemessen .)G=(V,E)G1CcCGpGcCpG

Ich möchte argumentieren, dass ich ein gegebenes für das die obige Bedingung gilt, leicht in eine Scheitelpunktabdeckung umwandeln oder anders ausgedrückt in ein C ' gleicher Kardinalität umwandeln kann , wenn jedes c C ' in G an a gesetzt wird Eckpunkt G , und C ' umfasst noch G .CCcCGGCG

Mein Ansatz bestand darin, die Kanten auszurichten und die Punkte in am Endscheitelpunkt des Bogens zu verschieben. Bisher habe ich jedoch keine korrekte Orientierung gefunden, die C ' aus C ergibt .CCC

Hat jemand eine Idee?

user695652
quelle
Ich verstehe das Problem nicht ganz. Was bedeutet " in G "? Wie genau messen Sie Entfernungen? Wenn Sie meinen, dass p immer auf einer Kante ist, dann scheint es, dass, wenn Sie es an einem Ende platzieren, jeder Punkt, der höchstens 1 von ihm entfernt ist - nämlich beide Endpunkte -, immer noch höchstens 1 von ihm entfernt ist. Für welche Orientierung auch immer. pGp11
Yuval Filmus
1
@Yuval Filmus ist eine Jordanische Bogenzeichnung von G , dh eine Teilmenge von \ mathhbb R 2 . p G bedeutet nur, dass der Punkt in der Zeichnung enthalten sein muss und nicht irgendwo in der Ebene. Die Entfernung wird als geodätische Entfernung in G gemessen , dh der kürzeste Weg, der zwei Punkte in der Zeichnung verbindet. Nehmen Sie für Ihre letzte Bemerkung einen Zyklus von 4 und setzen Sie zwei Punkte in die Mitte der ersten und dritten Kante. Dies deckt den gesamten Graphen ab, aber wenn Sie jetzt einen Punkt an seinem Scheitelpunktendpunkt im Uhrzeigersinn und einen Punkt an seinem Scheitelpunktendpunkt gegen den Uhrzeigersinn verschieben, wird dies behandeltGG\mathhbbR2pGG
user695652

Antworten:

5

Wenn keine Punkte in genau auf dem Mittelpunkt einer Kante in G liegen , reicht es aus, jeden Punkt in C dem nächsten Scheitelpunkt in G zuzuordnen . Ich überlasse es dem Leser als Übung, dies zu beweisen (Hinweis: durch Widerspruch beweisen).CGCG

Wenn andererseits Punkte in auf der Mitte der Kanten liegen dürfen, können wir ein Gegenbeispiel liefern:C

Bildbeschreibung hier eingeben

Die blauen Linien und Kreise sind und die roten Kreuze sind C .GC

EDITIERT ZUM HINZUFÜGEN: Ein Beispiel mit einem zweifach verbundenen Diagramm

Bildbeschreibung hier eingeben

mhum
quelle
Vielen Dank für das Gegenbeispiel. Stimmen Sie zu, dass die Behauptung wahr ist, wenn wir die zu verbindenden Diagramme einschränken, auch wenn alle Punkte in der Mitte liegen?
user695652
Ich glaube nicht, dass Bi-Connectedness Sie retten wird. Ich habe meine Antwort mit einem neuen Beispiel bearbeitet.
Mhum
Das ist eine ganz andere Frage. Es kann sinnvoll sein, es separat zu posten.
mhum
@mhum Wie hast du Bilder von Graphen gemacht? Gibt es dazu ein Programm?
Tacet
@Tacet Ich erinnere mich nicht genau, wie ich das gemacht habe. Ich denke, der erste könnte MS Paint oder GIMP gewesen sein. Der zweite könnte entweder GIMP oder Geogebra sein.
mhum