Numer gliniarza - Cop number

W teorii grafów , gałąź matematyki, liczba gliną lub copnumber o undirected wykresu jest minimalna liczba policjantów, że wystarczy, aby zapewnić zwycięstwo (czyli przechwytywania złodzieja) w pewnym pogoń-evasion gry na wykresie.

Zasady

W tej grze jeden gracz kontroluje pozycję określonej liczby policjantów, a drugi gracz kontroluje pozycję złodzieja. Gliniarze próbują złapać złodzieja, przesuwając się do tej samej pozycji, podczas gdy złodziej stara się pozostać niezauważonym. W ten sposób gracze wykonują następujące akcje, naprzemiennie ze sobą:

• W pierwszej turze gry gracz kontrolujący policjantów umieszcza każdego policjanta na wierzchołku wykresu (pozwalając na umieszczenie więcej niż jednego policjanta na tym samym wierzchołku).
• Następnie gracz kontrolujący złodzieja umieszcza złodzieja na wierzchołku wykresu.
• W każdej kolejnej turze gracz kontrolujący policjantów wybiera (prawdopodobnie pustą) podgrupę policjantów i przenosi każdego z tych policjantów do sąsiednich wierzchołków. Pozostali gliniarze (jeśli są) zostają.
• W swojej turze złodziej może przesunąć się do sąsiedniego wierzchołka lub pozostać w miejscu.

Gra kończy się wygraną dla gliniarzy, gdy złodziej zajmuje ten sam wierzchołek co glina. Jeśli tak się nie stanie, złodziej wygrywa.

Liczba gliniarzy na wykresie to minimalna liczba, dzięki której gliniarze mogą wygrać grę . ${\ Displaystyle G}$${\displaystyle k}$${\displaystyle k}$${\ Displaystyle G}$

Przykład

Na drzewie numer gliniarza to jeden. Policjant może zacząć wszędzie, a na każdym kroku przemieszczać się do wyjątkowego sąsiada, który jest bliżej złodzieja. Każdy krok gliniarza zmniejsza rozmiar poddrzewa, do którego przykuty jest złodziej, więc gra w końcu się kończy.

Stopniowo zbliżając się do siebie, dwóch gliniarzy może w końcu złapać złodzieja na dowolnym cyklu (tutaj, baseballowy diament)

Na wykresie cyklu o długości większej niż trzy liczba policjantów wynosi dwa. Jeśli jest tylko jeden gliniarz, złodziej może przesunąć się na pozycję dwa kroki od gliniarza i zawsze zachowywać tę samą odległość po każdym ruchu złodzieja. W ten sposób złodziej może na zawsze uniknąć schwytania. Jeśli jednak jest dwóch gliniarzy, jeden może pozostać na jednym wierzchołku i sprawić, że złodziej i drugi gliniarz zagrają na pozostałej ścieżce. Jeśli drugi policjant zastosuje się do strategii drzewa, złodziej w końcu przegra.

Ogólne wyniki

Każdy wykres, którego obwód jest większy niż cztery, ma liczbę policjantów co najmniej równą jego minimalnemu stopniowi . Wynika z tego, że istnieją wykresy arbitralnie wysokiej liczby policjantów.

Henri Meyniel (znany również z grafów Meyniela ) przypuszczał w 1985 roku, że każdy połączony graf z wierzchołkami ma numer policjanta . Te wykresy Levi (lub wykresy zachorowalności) o ograniczonych płaszczyzn rzutowych mieć obwód sześć i minimalny stopień , więc jeśli to prawda związany byłby najlepszy możliwy. ${\ Displaystyle n}$${\ Displaystyle O ({\ sqrt {n}})}$${\ Displaystyle \ Omega ({\ sqrt {n}})}$

Wszystkie wykresy mają podliniową liczbę policjantów. Jednym ze sposobów udowodnienia tego jest użycie podwykresów, których może strzec pojedynczy gliniarz: gliniarz może poruszać się, by wyśledzić złodzieja w taki sposób, że jeśli złodziej kiedykolwiek wejdzie do podwykresu, gliniarz może natychmiast go schwytać. Dwa typy podgrafu, które można chronić, to zamknięte sąsiedztwo pojedynczego wierzchołka i najkrótsza ścieżka między dowolnymi dwoma wierzchołkami. Moore związany w błąd stopni średnicy oznacza, że co najmniej jeden z tych dwóch rodzajów guardable zestawów posiada rozmiar . Używanie jednego policjanta do pilnowania tego zestawu i powtarzanie się w połączonych komponentach pozostałych wierzchołków wykresu pokazuje, że liczba policjantów wynosi najwyżej . ${\ Displaystyle \ Omega (\ log n / \ log \ log n)}$${\ Displaystyle O (n \ log \ log n / \ log n)}$

Bardziej subliniowa górna granica liczby policjantów,

${\ Displaystyle {\ Frac {n} {2 ^ {(1-o (1)) {\ sqrt {\ log n}}}}},}$

jest znana. Jednak problemy z uzyskaniem ścisłego związku i udowodnienia lub obalenia hipotezy Meyniela pozostają nierozwiązane. Nie wiadomo nawet, czy miękka hipoteza Meyniela , że istnieje stała, dla której liczba policjanta jest zawsze prawdziwa, jest prawdziwa. ${\displaystyle c<1}$${\ Displaystyle O (n ^ {c})}$

Obliczenie liczby policjantów danego wykresu to EXPTIME-hard , a hard dla sparametryzowanej złożoności .

Specjalne klasy grafów

Te wykresy COP-win są wykresy z numerem cop równa jeden.

Każdy wykres planarny ma najwyżej trzy liczby policjantów. Mówiąc bardziej ogólnie, każdy wykres ma liczbę policjantów co najwyżej proporcjonalną do jego rodzaju . Jednak najbardziej znana dolna granica liczby policjantów pod względem rodzaju to w przybliżeniu pierwiastek kwadratowy z rodzaju, który jest daleki od górnej granicy, gdy rodzaj jest duży.

Treewidth wykresu można także otrzymać w wyniku prowadzenia gry-uchylania się, ale w którym złodziej może przemieszczać się wzdłuż ścieżki dowolna długości zamiast jednej krawędzi w każdym kroku. Ta dodatkowa swoboda oznacza, że ​​liczba policjantów jest zazwyczaj mniejsza niż szerokość drzewa. Dokładniej, na wykresach szerokości drzewa liczba policjantów wynosi co najwyżej . ${\ Displaystyle w}$${\displaystyle \lpodłoga z 2\rpodłoga +1}$

Bibliografia