Przystań (teoria grafów)

W teorii grafów przystań jest pewnym rodzajem funkcji na zbiorach wierzchołków grafu nieskierowanego . Jeśli istnieje przystań, unikający może ją wykorzystać do wygrania gry pościg-unik na wykresie, sprawdzając funkcję na każdym etapie gry, aby określić bezpieczny zestaw wierzchołków, do których można się poruszać. Havens zostały po raz pierwszy wprowadzone przez Seymoura i Thomasa (1993) jako narzędzie do charakteryzowania szerokości drzewa grafów. Ich inne zastosowania obejmują udowodnienie istnienia małych separatorów na drugorzędowe rodziny grafów domkniętych oraz charakterystyka końców i klik mniejszych grafów nieskończonych .

Definicja

Jeśli $G$ jest grafem nieskierowanym, a $X$ jest zbiorem wierzchołków, to klapa $X$ jest niepustą spójną składową podgrafu $G$ utworzonego przez usunięcie $X$ . Przystań rzędu $k$ w $G$ $jest$ funkcją $β$ , która przypisuje klapkę $X$ $β (X)$ każdemu zbiorowi X mniejszemu niż $k$ wierzchołki. Funkcja ta musi również spełniać dodatkowe ograniczenia, które różnie podają różni autorzy. Liczba $k$ nazywana jest porządkiem raju.

W oryginalnej definicji Seymoura i Thomasa raj jest wymagany, aby spełnić właściwość, zgodnie z którą każde dwie klapy $β (X)$ i $β (Y)$ muszą się stykać: albo mają wspólny wierzchołek, albo istnieje krawędź z jednym końcem w każda klapa. W definicji użytej później przez Alona, Seymoura i Thomasa raje są zamiast tego wymagane, aby spełnić słabszą monotoniczności : jeśli $X \subseteq Y$ , a zarówno $X ,$ jak i $Y$ mają mniej niż $k$ wierzchołki, to $β (Y) \subseteq β (X)$ . Właściwość dotykania implikuje właściwość monotoniczności, ale niekoniecznie odwrotnie. Jednak z wyników Seymoura i Thomasa wynika, że w grafach skończonych, jeśli istnieje przystań z właściwością monotoniczności, to istnieje również przystań o tym samym porządku i właściwości dotykania.

Cierń rzędu czwartego. Przystań wywodząca się z tego jeżyna odwzorowuje każdy zbiór

X

złożony z trzech lub mniej wierzchołków na unikalny spójny składnik

G \ X

, który zawiera co najmniej jeden podwykres z jeżyna.

Przystanie z definicją wzruszającą są blisko spokrewnione z jeżynami , rodzinami połączonych podgrafów danego grafu, które wszystkie stykają się ze sobą. Kolejność jeżyn to minimalna liczba wierzchołków potrzebna w zbiorze wierzchołków, który trafia na wszystkie podgrafy w rodzinie. Zbiór klap $β (X)$ dla przystani rzędu $k$ (z wzruszającą definicją) tworzy cierń rzędu co najmniej $k$ , ponieważ każdy zbiór $Y$ o mniej niż $k$ wierzchołkach nie trafia w podgraf $β (Y)$ . I odwrotnie, z dowolnego jeżyna rzędu $k$ można zbudować przystań tego samego rzędu, definiując $β (X)$ (dla każdego wyboru $X$ ) jako klapę $X$ , która zawiera wszystkie podgrafy w jeżynie, które są rozłączne od $X.$ _ Wymóg, aby wszystkie podgrafy w jeżynie stykały się ze sobą, można wykorzystać do wykazania, że ta $X$ istnieje i że wszystkie klapy $β (X)$ wybrane w ten sposób stykają się ze sobą. Zatem graf ma cierń rzędu $k$ wtedy i tylko wtedy, gdy ma przystań rzędu $k$ .

Przykład

Jako przykład niech $G będzie$ grafem siatkowym z dziewięcioma wierzchołkami . Zdefiniuj przystań rzędu 4 w $G$ , odwzorowując każdy zestaw $X$ złożony z trzech lub mniej wierzchołków na klapę $X$ $β (X)$ w następujący sposób:

Jeśli istnieje unikalna klapka $X$ , która jest większa niż jakakolwiek inna klapka $X$ , niech $β (X)$ będzie tą unikalną dużą klapką $X.$
W przeciwnym razie wybierz arbitralnie $β (X)$ jako dowolną klapę $X.$

Łatwo jest zweryfikować za pomocą analizy przypadku , że ta funkcja $β$ spełnia wymaganą właściwość przystani w zakresie monotoniczności. Jeśli $X \subseteq Y$ i $X$ ma mniej niż dwa wierzchołki lub $X$ ma dwa wierzchołki, które nie są dwoma sąsiadami wierzchołka narożnego siatki, to jest tylko jedna klapka $X$ i zawiera ona każdą klapkę $Y.$ W pozostałym przypadku $X$ składa się z dwóch sąsiadów wierzchołka narożnego i ma dwa $X$ -klapy: jedna składająca się z tego wierzchołka narożnego, a druga (wybrana jako $β (X)$ ) składająca się z sześciu pozostałych wierzchołków. Bez względu na to, który wierzchołek zostanie dodany do $X ,$ aby utworzyć $Y$ , będzie klapka $Y$ z co najmniej czterema wierzchołkami, która musi być unikalną największą klapą, ponieważ zawiera ponad połowę wierzchołków spoza $Y$ . Ta duża $Y$ zostanie wybrana jako $β (Y)$ i będzie podzbiorem $β (X)$ . Tak więc w każdym przypadku zachodzi monotoniczność.

Pościg – unik

Przystanie modelują pewną klasę strategii dla unikającego w grze pościg-unik, w której mniej niż $k$ ścigających próbuje schwytać pojedynczego unikającego, zarówno ścigający, jak i unikający są ograniczeni do wierzchołków danego nieskierowanego grafu, a pozycje prześladowcy i unikający są znani obu graczom. W każdym ruchu gry nowy prześladowca może zostać dodany do dowolnego wierzchołka grafu (o ile w dowolnym momencie na grafie znajduje się mniej niż $k prześladowców) lub jeden z już dodanych prześladowców może zostać usunięty z$ wykres. Jednak zanim zostanie dodany nowy prześladowca, unikający jest najpierw informowany o swojej nowej lokalizacji i może poruszać się wzdłuż krawędzi grafu do dowolnego niezajętego wierzchołka. Podczas ruchu unikający nie może przejść przez żaden wierzchołek, który jest już zajęty przez ścigającego.

Jeśli $k$ -haven (z właściwością monotoniczności) istnieje, wtedy unikający może uniknąć schwytania w nieskończoność i wygrać grę, zawsze przesuwając się do wierzchołka $β (X)$ , gdzie $X$ jest zbiorem wierzchołków, które będą zajęte przez prześladowcy na końcu ruchu. Własność monotoniczności przystani gwarantuje, że gdy nowy prześladowca zostanie dodany do wierzchołka grafu, wierzchołki w $β (X)$ są zawsze osiągalne z aktualnej pozycji unikającego.

Na przykład unikający może wygrać tę grę z trzema prześladowcami na siatce 3 × 3, postępując zgodnie z tą strategią z przystanią rzędu 4 opisaną w przykładzie. Jednak na tym samym wykresie czterech ścigających zawsze może schwytać unikającego, najpierw przechodząc na trzy wierzchołki, które dzielą siatkę na dwie trzywierzchołkowe ścieżki, a następnie przechodząc na środek ścieżki zawierającej unikającego, zmuszając unikającego do jednego z wierzchołki narożne, a na koniec usunięcie jednego z prześladowców, który nie sąsiaduje z tym rogiem i umieszczenie go na uniku. Dlatego 3 × 3 nie może mieć przystani rzędu 5.

Przystanie z właściwością dotykania pozwalają uciekinierowi wygrać grę z potężniejszymi prześladowcami, którzy mogą jednocześnie przeskakiwać z jednego zestawu zajętych wierzchołków do drugiego.

Połączenia z szerokością drzewa, separatorami i drugorzędnymi

Przystani można użyć do scharakteryzowania szerokości drzewa grafów: graf ma przystań rzędu $k$ wtedy i tylko wtedy, gdy ma szerokość drzewa co najmniej $k - 1$ . Dekompozycja drzewa może być wykorzystana do opisania zwycięskiej strategii dla prześladowców w tej samej grze pościg-unik, więc prawdą jest również, że graf ma przystań rzędu k wtedy i tylko wtedy, gdy unikający wygrywa z najlepszą grą przeciwko $mniej$ niż $k$ prześladowcy. W grach wygranych przez unikającego zawsze istnieje optymalna strategia w postaci opisanej przez przystań, aw grach wygranych przez ścigającego zawsze istnieje strategia optymalna w postaci opisanej przez dekompozycję drzewa. Na przykład, ponieważ 3 × 3 ma przystań rzędu 4, ale nie ma przystani rzędu 5, musi mieć szerokość drzewa dokładnie 3. To samo twierdzenie min-max można uogólnić na nieskończone wykresy o skończonej szerokości drzewa, z definicja szerokości drzewa, w której wymagane jest, aby drzewo leżące pod spodem było pozbawione promieni (to znaczy nie miało końcówek ).

Przystanie są również ściśle związane z istnieniem separatorów , małych zestawów $X$ wierzchołków w grafie $n$ -wierzchołków, tak że każda klapa $X$ ma co najwyżej $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} 2 n / 3$ wierzchołki. Jeśli graf $G$ nie ma $k$ - separatora wierzchołków, to każdy zbiór $X$ złożony z co najwyżej $k$ wierzchołków ma (unikalną) klapkę $X$ z więcej niż $2 n ⁄ 3$ wierzchołkami. W tym przypadku $G$ ma przystań rzędu $k + 1$ , w której $β (X)$ jest zdefiniowana jako ta wyjątkowa duża klapa $X.$ Oznacza to, że każdy wykres ma albo mały separator, albo przystań wysokiego rzędu.

Jeśli graf $G$ ma przystań rzędu $k$ , przy czym $k \geq h 3/2 n 1/2$ dla pewnej liczby całkowitej $h$ , to $G$ musi mieć pełny graf $K h$ jako drugorzędny . Innymi słowy, liczba Hadwigera n $-$ wierzchołkowego grafu z przystanią rzędu $k$ wynosi co najmniej $k 2/3 n -1/3$ . $Kh W$ konsekwencji Grafy bez drugorzędnych mają szerokość drzewa mniejszą niż $h 3/2 n 1/2$ i separatory o rozmiarze mniejszym niż $h 3/2 n 1/2$ . Mówiąc bardziej ogólnie, ograniczenie dotyczące szerokości drzewa i rozmiaru separatora zachodzi dla dowolnej nietrywialnej rodziny grafów, którą można scharakteryzować za pomocą zabronionych nieletnich , ponieważ dla każdej takiej rodziny istnieje O ( n ) {\ Displaystyle O ({\ $}})$ stała $h$ taka, że rodzina nie obejmuje $K h$ .

W nieskończonych grafach

Jeśli wykres $G$ zawiera promień, półnieskończoną prostą ścieżkę z wierzchołkiem początkowym, ale bez wierzchołka końcowego, to ma przystań porządku $ℵ 0$ : to znaczy funkcję $β$ , która odwzorowuje każdy skończony zbiór $X$ wierzchołków na $X$ - klapa, spełniająca warunek konsystencji dla przystani. Mianowicie zdefiniuj $β (X)$ jako unikalny $X$ -flap, który zawiera nieskończenie wiele wierzchołków promienia. Tak więc w przypadku grafów nieskończonych związek między szerokością drzewa a przystaniami załamuje się: pojedynczy promień, mimo że sam jest drzewem, ma przystanie wszystkich skończonych rzędów, a jeszcze silniej przystań porządku $ℵ 0$ . Dwa promienie nieskończonego wykresu są uważane za równoważne, jeśli nie ma skończonego zbioru wierzchołków, który oddziela nieskończenie wiele wierzchołków jednego promienia od nieskończenie wielu wierzchołków drugiego promienia; jest to relacja równoważności , a jej klasy równoważności nazywane są końcami grafu.

Końce dowolnego grafu są w relacji jeden do jednego z jego przystaniami porządku $ℵ 0$ . Bo każdy promień określa przystań, a każde dwa równoważne promienie określają tę samą przystań. I odwrotnie, każda przystań jest określona przez promień w ten sposób, jak pokazuje poniższa analiza przypadku:

Jeśli przystań ma właściwość skrzyżowania
${\ Displaystyle S = \ bigcap _ {X} \ lewo (\ beta (X) \ kubek X \ prawej)}$

(gdzie przecięcie rozciąga się na wszystkie skończone zbiory $X$ ) samo jest zbiorem nieskończonym $S$ , to każda skończona prosta ścieżka, która kończy się wierzchołkiem $S$ , może zostać przedłużona, aby osiągnąć dodatkowy wierzchołek $S$ , a powtórzenie tego procesu wydłużania daje promień przechodzący przez nieskończenie wiele wierzchołków $S$ . Ten promień określa daną przystań.
Z drugiej strony, jeśli $S$ jest skończony, to (pracując w podgrafie $G \ S$ ) można założyć, że jest pusty. W tym przypadku dla każdego skończonego zbioru $X ja$ wierzchołków istnieje skończony zbiór $X ja +1$ z właściwością, że $X ja$ jest rozłączny z ${\ Displaystyle X_ {i + 1 }\cup \beta (X_{i+1})}$ . Jeśli rabuś postępuje zgodnie ze strategią unikania określoną przez schronienie, a policja postępuje zgodnie ze strategią określoną przez tę sekwencję zestawów, to ścieżka, którą podąża rabuś, tworzy promień, który określa schronienie.

Zatem każda klasa równoważności promieni definiuje unikalną przystań, a każda przystań jest zdefiniowana przez klasę równoważności promieni.

Dla dowolnej $liczby$ kardynalnej nieskończony wykres $G$ ma przystań porządku $κ wtedy i$ $wtedy,$ ma klikę mniejszą . Oznacza to, że dla niezliczonych liczności największym rzędem raju w $G$ jest liczba Hadwigera $G$ .