Wykres skrzyżowania - Intersection graph

Przykład tego, jak przecinające się zbiory definiują graf.

W teorii wykres An wykres przecięcia jest wykresem , który przedstawia wzór przecięcia z rodziny zestawów . Dowolny graf może być reprezentowany jako graf przecięcia, ale niektóre ważne specjalne klasy grafów mogą być definiowane przez typy zbiorów, które są używane do tworzenia ich reprezentacji przecięcia.

Formalna definicja

Formalnie graf przecięcia G jest grafem nieskierowanym utworzonym z rodziny zbiorów

S _ja , ja = 0, 1, 2, ...

tworząc jeden wierzchołek V _i na każdy zestaw S ma _I , łączący dwa wierzchołki v _{: i} i v _j przez krawędź, gdy odpowiednie dwa zestawy posiada przecięcie niepusty, to znaczy

E ( G ) = {{ v _i , v _j } | I ≠ j , S _i ∩ S _j ≠ ∅}.

Wszystkie wykresy są wykresami przecięcia

Każdy nieukierunkowane wykres G może być przedstawiony w postaci wykresu przecięcia: dla każdego wierzchołka v _I o G , tworzą zbiór S _i złożony z wypadku krawędzi do v _ı ; wtedy dwa takie zbiory mają niepuste przecięcie wtedy i tylko wtedy, gdy odpowiadające im wierzchołki mają wspólną krawędź. Erdős, Goodman i Pósa (1966) podają konstrukcję, która jest bardziej wydajna (co oznacza, że ​​wymaga mniejszej całkowitej liczby elementów we wszystkich zbiorach S _i połączonych), w której całkowita liczba elementów zbioru wynosi co najwyżej n ² / 4 gdzie n to liczba wierzchołków na wykresie. Obserwację, że wszystkie grafy są grafami przecięcia przypisują Szpilrajn-Marczewski (1945) , ale powiedzmy, że zobacz także Čulíka (1964) . Liczba przecięcia wykresu jest minimalna liczba elementów w dowolnej reprezentacji przecięcia wykresu.

Klasy grafów przecięcia

Wiele ważnych rodzin grafów można opisać jako grafy przecięcia bardziej ograniczonych typów rodzin zbiorów, na przykład zbiory wywodzące się z pewnego rodzaju konfiguracji geometrycznej:

• Przedział wykresu określa się jako wykresu przecięcia odstępach na prostej lub podłączonych subgraphs o wykres drogi .
• Wykres obojętność może być zdefiniowana jako wykresu przecięcia odstępów jednostkowych na prostej
• Okrągły wykres łuku określa się jako wykresu przecięcia łuków na okręgu .
• Wykres wielokąt-koło jest określona jako przecięcie wielokątów z narożnikami na okręgu.
• Jedną z cech grafu akordowego jest graf przecięcia połączonych podgrafów drzewa .
• Trapezowy wykresu określa się jako wykresu przecięcia trapezów utworzone z dwóch równoległych linii. Stanowią one uogólnienie pojęcia grafu permutacyjnego , z kolei są szczególnym przypadkiem rodziny dopełnień grafów porównywalności zwanych grafami współporównywalności.
• Wykres twardego jednostka jest zdefiniowana jako wykresu przecięcia płyt jednostkowych w płaszczyźnie.
• Wykres koło jest wykresem przecięcia zbioru cięciwy okręgu.
• Koło pakowania twierdzenie stwierdza, że płaskie wykresy są dokładnie wykresy przecięcia rodzin zamkniętych dysków w płaszczyźnie ograniczonym kręgach zakaz przejściach.
• Przypuszczenie Scheinermana (teraz twierdzenie) stwierdza, że ​​każdy wykres płaski może być również reprezentowany jako wykres przecięcia odcinków linii w płaszczyźnie. Jednak wykresy przecięcia odcinków linii mogą być również niepłaskie, a rozpoznanie wykresów przecięcia odcinków linii jest kompletne dla egzystencjalnej teorii rzeczywistości ( Schaefer 2010 ).
• Wykres liniowy grafu G jest definiowane jako wykresu przecięcia krawędzi G , gdzie stanowią co krawędź jako zestaw dwóch końcowych.
• Wykres łańcuch jest wykresem przecięcia krzywych na płaszczyźnie .
• Wykres ma boksowość k, jeśli jest wykresem przecięcia wielowymiarowych pudełek o wymiarze k , ale nie o żadnym mniejszym wymiarze.
• Wykres klika przedstawiono wykres przecięcia maksymalnej klik innego wykresu
• Wykres blokowy z klik drzewa jest wykresem przecięcia dwuspójna składowa innego wykresu

Scheinerman (1985) scharakteryzował klasy przecięcia grafów , rodziny grafów skończonych, które można opisać jako grafy przecięcia zbiorów wylosowanych z danej rodziny zbiorów. Konieczne i wystarczające jest, aby rodzina posiadała następujące właściwości:

• Każdy indukowany podgraf grafu w rodzinie musi również należeć do rodziny.
• Każdy graf utworzony z grafu w rodzinie przez zastąpienie wierzchołka kliką musi również należeć do rodziny.
• W rodzinie istnieje nieskończona sekwencja grafów, z których każdy jest indukowanym podgrafem następnego grafu w sekwencji, z tą właściwością, że każdy graf w rodzinie jest indukowanym podgrafem grafu w sekwencji.

Jeśli reprezentacje grafów przecięcia mają dodatkowy wymóg, aby różne wierzchołki były reprezentowane przez różne zbiory, to właściwość rozwinięcia kliki może zostać pominięta.

Pojęcia pokrewne

Zamówień teoretyczna analogowo wykresach przecięcia są zlecenia integracji . W ten sam sposób, że reprezentacja przecięcia wykresu etykietuje każdy wierzchołek z zestawu, co wierzchołki przylegają wtedy i tylko wtedy, gdy ich zestawy posiadają niepusty przecięcia tak reprezentacja włączenie F z poset etykiet każdy element w zestawie tak, że dla każdego x i y w posecie, x  ≤  y wtedy i tylko wtedy, gdy f ( x ) ⊆  f ( y ).

Zobacz też

• Wykres kontaktu

Bibliografia

• Čulík, K. (1964), „Zastosowania teorii grafów do logiki matematycznej i lingwistyki”, Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963) , Praga: Publ. Dom Czechosłowacki Acad. Sci., s. 13–20, MR  0176940.
• Erdős, Paul ; Goodman, AW; Pósa, Louis (1966), „Reprezentacja wykresu za pomocą określonych przecięć” (PDF) , Canadian Journal of Mathematics , 18 (1): 106-112, doi : 10.4153/CJM-1966-014-3 , MR  0186575.
• Golumbic, Martin Charles (1980), Algorytmiczna teoria grafów i doskonałe wykresy , Academic Press, ISBN 0-12-289260-7.
• McKee, Terry A.; McMorris, FR (1999), Topics in Intersection Graph Theory , SIAM Monographs on Discrete Mathematics and Applications, 2 , Philadelphia: Society for Industrial and Applied Mathematics, ISBN 0-89871-430-3, MR  1672910.
• Szpilrajn-Marczewski, E. (1945), „Sur deux propriétés des class d'ensembles”, Fundusz. Matematyka. , 33 : 303-307 , MR  0015448.
• Schaefer, Marcus (2010), „Złożoność niektórych problemów geometrycznych i topologicznych” (PDF) , Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, wrzesień 2009, Revised Papers , Lecture Notes in Computer Science, 5849 , Springer-Verlag, s. 334-344, doi : 10.1007/978-3-642-11805-0_32 , ISBN 978-3-642-11804-3.
• Scheinerman, Edward R. (1985), "Charakteryzowanie klas przecięcia wykresów", Matematyka dyskretna , 55 (2): 185-193, doi : 10.1016/0012-365X (85) 90047-0 , MR  0798535.

Dalsza lektura

• Aby zapoznać się z przeglądem zarówno teorii grafów przecięcia, jak i ważnych specjalnych klas grafów przecięcia, patrz McKee i McMorris (1999) .

Linki zewnętrzne

• Jan Kratochvíl, Wykład wideo o wykresach skrzyżowań (czerwiec 2007)
• E. Prisner, Podróż przez Hrabstwo Intersection Graph