Przekształcanie arbitralnej osłony w osłonę wierzchołków

Podano wykres płaski $G=(V,E)$ i niech oznacza jego osadzenie w płaszczyźnie st, każda krawędź ma długość . Mam ponadto zestaw punktów, w których każdy punkt jest zawarty w . Ponadto, dla dowolnego punktu w istnieje z odległością geodezyjną do co najwyżej jeden. (Odległość jest mierzona jako najkrótsza odległość w obrębie .) $\mathcal{G}$ $1$ $C$ $c \in C$ $\mathcal{G}$ $p$ $\mathcal{G}$ $c \in C$ $p$ $\mathcal{G}$

Chcę argumentować, że biorąc pod uwagę dla którego obowiązuje powyższy warunek, mogę łatwo przekształcić go w osłonę wierzchołków lub inaczej, przekształcić go w o tej samej liczności, o ile dowolne jest umieszczone w na wierzchołku i nadal obejmuje . $C$ $C'$ $c \in C'$ $\mathcal{G}$ $G$ $C'$ $G$

Moje podejście polegało na zorientowaniu krawędzi i przesunięciu punktów w na końcowym wierzchołku łuku. Ale do tej pory nie mogę znaleźć prawidłową orientację co przynosi z . $C$ $C'$ $C$

Czy ktoś ma pomysł?

algorithms graph-theory set-cover

— użytkownik695652
źródło

Nie do końca rozumiem problem. Co oznacza „

”? Jak dokładnie mierzysz odległości? Jeśli masz na myśli, że

jest zawsze na krawędzi, to wydaje się, że jeśli umieścisz go na dowolnym końcu, to każdy punkt w odległości co najwyżej

od niego - mianowicie oba punkty końcowe - będzie nadal w odległości co najwyżej

od niego. Bez względu na orientację.

p

$p$

G

$\mathcal{G}$

p

$p$

1

$1$

1

$1$

— Yuval Filmus

@Yuval Filmus

znajduje się Jordan łuku rysunek

, czyli podzbiór

oznacza po prostu, że punkt musi znajdować się na rysunku, a nie tylko w dowolnym miejscu na płaszczyźnie. Odległość jest mierzona jako odległość geodezyjna w

, tj. Najkrótsza ścieżka łącząca dwa punkty na rysunku. Na ostatnią uwagę weź 4 cykl i umieść dwa punkty na środku pierwszej i trzeciej krawędzi. Obejmuje to cały wykres, ale jeśli teraz przesuniesz jeden punkt w punkcie końcowym wierzchołka zgodnym z ruchem wskazówek zegara i jeden punkt w punkcie końcowym wierzchołka przeciwnego do ruchu wskazówek zegara, to nie obejmuje

G

$\mathcal{G}$

G

$G$

\mathhbb R^{2}

$\mathhbb{R}^2$

p \in G

$p \in \mathcal{G}$

G

$\mathcal{G}$

— użytkownik695652

Jeśli żadne punkty w leżą dokładnie w punkcie środkowym krawędź w , to wystarczy skojarzyć każdy punkt w z dokładnością do wierzchołka w . Pozostawię to jako ćwiczenie dla czytelnika, aby to udowodnić (wskazówka: udowodnij przez sprzeczność). $C$ $\mathcal{G}$ $C$ $\mathcal{G}$

Z drugiej strony, jeśli punkty w mogą leżeć na środkowym punkcie krawędzi, możemy podać przeciwny przykład: $C$

enter image description here

Niebieskie i okręgi są i czerwone krzyże . $\mathcal{G}$ $C$

ZMIENIONO DO DODANIA: Przykład z podwójnie połączonym wykresem

enter image description here

— mum
źródło

Wielkie dzięki za kontrprzykład. Czy zgadzasz się, że jeśli ograniczymy możliwość łączenia wykresów, to twierdzenie jest prawdziwe, nawet jeśli wszystkie punkty są w środku?

— user695652 21.04.13

Nie sądzę, że bi-łączność cię uratuje. Zredagowałem swoją odpowiedź na nowym przykładzie.

— mhum

To jest raczej inne pytanie. Sensowne może być opublikowanie go osobno.

— mhum,

@mhum Jak zrobiłeś zdjęcia wykresów? Czy istnieje jakiś program do tego?

— Tacet,

@Tacet Nie pamiętam dokładnie, jak to zrobiłem. Myślę, że pierwszym może być MS Paint lub GIMP. Drugim może być GIMP lub Geogebra.

— mhum,