Umwandlung eines beliebigen Covers in ein Vertex-Cover

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

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 gleicher Kardinalität umwandeln kann , wenn jedes in an a gesetzt wird Eckpunkt , und umfasst noch . $C$ $C'$ $c \in C'$ $\mathcal{G}$ $G$ $C'$ $G$

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 aus ergibt . $C$ $C'$ $C$

Hat jemand eine Idee?

algorithms graph-theory set-cover user695652
quelle

Ich verstehe das Problem nicht ganz. Was bedeutet "

"? Wie genau messen Sie Entfernungen? Wenn Sie meinen, dass

immer auf einer Kante ist, dann scheint es, dass, wenn Sie es an einem Ende platzieren, jeder Punkt, der höchstens

von ihm entfernt ist - nämlich beide Endpunkte -, immer noch höchstens

von ihm entfernt ist. Für welche Orientierung auch immer.

p

$p$

G

$\mathcal{G}$

p

$p$

1

$1$

1

$1$

Yuval Filmus

@Yuval Filmus

ist eine Jordanische Bogenzeichnung von

, dh eine Teilmenge von

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

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 behandelt

G

$\mathcal{G}$

G

$G$

\mathhbb R^{2}

$\mathhbb{R}^2$

p \in G

$p \in \mathcal{G}$

G

$\mathcal{G}$

user695652

Antworten:

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

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 . $\mathcal{G}$ $C$

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