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

Odpowiedzi:

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,