Wykres wielokąt-koło

„Wykres pająka” przekierowuje tutaj. Aby zobaczyć wykres, zobacz mapę radarową . Aby zapoznać się z terminem krykietowym, zobacz Słowniczek terminów krykietowych .

Po lewej stronie zbiór wielokątów wpisanych w okrąg; po prawej stronie względny wykres Wielokąt-okrąg (wykres przecięcia wielokątów). Na dole naprzemienna sekwencja wielokątów wokół okręgu.

W dyscyplinie matematycznej teorii grafów , wykres wielokąt-koło jest wykresem przecięcia zbioru wielokątów wypukłych , których wszystkie wierzchołki leżą na wspólnym okręgu. Wykresy te nazywane są także wykresami pająkowymi . Ta klasa grafów została po raz pierwszy zaproponowana przez Michaela Fellowsa w 1988 r., motywowana faktem, że jest ona domknięta pod wpływem skurczu krawędzi i indukowanych operacji na podgrafach.

Wykres wielokąt-okrąg można przedstawić jako „sekwencję naprzemienną”. Taką sekwencję można uzyskać zaburzając wielokąty reprezentujące graf (jeśli to konieczne), tak aby żadne dwa nie miały wspólnego wierzchołka, a następnie wypisując dla każdego wierzchołka (w kolejności kołowej, zaczynając od dowolnego punktu) wielokąt dołączony do tego wierzchołka.

Zamknięcie w przypadku nakłonionych nieletnich

Zawężenie krawędzi wykresu wielokąt-okrąg daje w wyniku inny wykres wielokąt-okrąg. Geometryczną reprezentację nowego wykresu można utworzyć zastępując wielokąty odpowiadające dwóm punktom końcowym ściągniętej krawędzi ich wypukłą obudową . Alternatywnie, w sekwencji naprzemiennej reprezentującej pierwotny wykres, połączenie podciągów reprezentujących punkty końcowe ściągniętej krawędzi w jeden podciąg daje reprezentację ściągniętego wykresu w postaci naprzemiennej sekwencji. Wykresy koła wielokątnego są również zamknięte pod podgrafem indukowanym lub równoważnie operacje usuwania wierzchołków: aby usunąć wierzchołek, usunąć jego wielokąt z reprezentacji geometrycznej lub usunąć jego podciąg punktów z sekwencji naprzemiennej.

Uznanie

M. Koebe ogłosił algorytm rozpoznawania czasu wielomianowego, jednak jego wstępna wersja zawierała „poważne błędy” i wersja ostateczna nigdy nie została opublikowana. Martin Pergel udowodnił później, że problem rozpoznawania tych grafów jest NP-zupełny . NP-zupełne jest również określenie, czy dany graf można przedstawić jako graf wielokąt-koło z co najwyżej k wierzchołkami na wielokąt, dla dowolnego k ≥ 3 .

Powiązane rodziny grafów

Wykresy wielokąt-koło są uogólnieniem wykresów kołowych , które są wykresami przecięcia cięciw koła, oraz wykresów trapezowych , wykresów przecięcia trapezów, których wszystkie wierzchołki leżą na tych samych dwóch równoległych liniach. Obejmują one również wykresy łuku kołowego .

Wykresy wielokątno-kołowe nie są na ogół wykresami doskonałymi , ale są prawie idealne w tym sensie, że ich liczby chromatyczne mogą być ograniczone przez (wykładniczą) funkcję liczby ich klik .