Obwód (teoria grafów)

W teorii grafów obwód grafu nieskierowanego to długość najkrótszego cyklu zawartego w grafie . Jeśli graf nie zawiera żadnych cykli (czyli jest to las ) , jego obwód określa się jako nieskończoność . Na przykład 4-cyklowy (kwadrat) ma obwód 4. Siatka ma również obwód 4, a siatka trójkątna ma obwód 3. Wykres z obwodem 4 lub większym nie zawiera trójkątów .

Klatki

Graf sześcienny (wszystkie wierzchołki mają stopień trzeci) o obwodzie $g$ , który jest możliwie najmniejszy, jest znany jako klatka $g$ (lub klatka $(3, g)$ ). Wykres Petersena to unikalna klatka 5 (jest to najmniejszy wykres sześcienny o obwodzie 5), wykres Heawood to unikalna klatka 6, wykres McGee to unikalna klatka 7, a klatka ósemkowa Tutte to unikalna klatka 8- klatka szybowa. Dla danego obwodu może istnieć wiele klatek. Na przykład istnieją trzy nieizomorficzne 10-klatki, każda z 70 wierzchołkami: 10-klatka Balabana , graf Harriesa i graf Harriesa-Wonga .

Graf Petersena ma obwód równy 5
Wykres Heawood ma obwód 6
Wykres McGee ma obwód równy 7
Wykres Tutte-Coxetera ( Tutte ósemka ) ma obwód 8

Kolorowanie obwodu i wykresu

Dla dowolnych dodatnich liczb całkowitych $g$ i $χ$ istnieje graf o obwodzie co najmniej $g$ i liczbie chromatycznej co najmniej $χ$ ; na przykład wykres Grötzscha jest pozbawiony trójkątów i ma liczbę chromatyczną 4, a powtórzenie konstrukcji Mycielskiego użytej do utworzenia wykresu Grötzscha daje wykresy bez trójkątów o dowolnie dużej liczbie chromatycznej. Paul Erdős jako pierwszy udowodnił ogólny wynik metodą probabilistyczną . Dokładniej, pokazał, że losowy wykres na $n$ wierzchołkach, utworzony przez niezależne wybranie, czy uwzględnić każdą krawędź z prawdopodobieństwem $n (1- g)/ g$ , ma, z prawdopodobieństwem dążącym do 1, gdy $n$ dąży do nieskończoności, 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} n ⁄ 2$ cykle o długości $g$ lub mniejszej, ale nie ma niezależnego zestawu o rozmiarze $n ⁄ 2 k$ . Dlatego usunięcie jednego wierzchołka z każdego krótkiego cyklu pozostawia mniejszy graf o obwodzie większym niż $g$ , w którym każda klasa kolorów o kolorowaniu musi być mała, a zatem wymaga co najmniej $k$ kolorów w dowolnym kolorowaniu.

Wyraźne, choć duże, grafy o dużym obwodzie i liczbie chromatycznej można skonstruować jako pewne grafy Cayleya grup liniowych na ciałach skończonych . Te niezwykłe wykresy Ramanujana mają również duży współczynnik rozszerzalności .

Pojęcia pokrewne

Nieparzysty i parzysty obwód wykresu to odpowiednio długości najkrótszego nieparzystego cyklu i najkrótszego parzystego cyklu .

Obwód wykresu to długość najdłuższego ( prostego ) cyklu, a nie najkrótszego.

Uważany za najmniejszą długość nietrywialnego cyklu, obwód dopuszcza naturalne uogólnienia, takie jak skurcz 1 lub wyższe skurcze w geometrii skurczowej .

Obwód jest koncepcją dualną z łącznością krawędziową w tym sensie, że obwód grafu planarnego jest łącznością krawędziową jego grafu dualnego i odwrotnie. Pojęcia te są ujednolicone w teorii matroidów przez obwód matroidu , rozmiar najmniejszego zależnego zestawu w matroidzie. W przypadku matroidu graficznego obwód matroidu jest równy obwodowi podstawowego wykresu, podczas gdy w przypadku matroidu kograficznego jest równy łączności krawędzi.

Obliczenie

Obwód wykresu nieskierowanego można obliczyć, uruchamiając przeszukiwanie wszerz z każdego węzła ze złożonością, gdzie jest ${\ Displaystyle$ wierzchołków wykresu $O (nm)}$ a to $krawędzi$ . Praktyczną optymalizacją jest ograniczenie głębokości BFS do głębokości, która zależy od długości najmniejszego dotychczas odkrytego cyklu. Lepsze algorytmy są znane w przypadku, gdy obwód jest parzysty i gdy wykres jest płaski. Jeśli chodzi o dolne granice, obliczenie obwodu wykresu jest co najmniej tak trudne, jak rozwiązanie problemu znalezienia trójkąta na wykresie.

^ R. Diestel, Teoria grafów , s. 8. Wydanie 3, Springer-Verlag, 2005
^ Weisstein, Eric W. , „Obwód” , MathWorld
^ Brouwer, Andries E. , klatki . Elektroniczny dodatek do książki Distance-Regular Graphs (Brouwer, Cohen i Neumaier 1989, Springer-Verlag).
Bibliografia _ _ _ _ _ _ _ _ _ _ _ _ _
Bibliografia _ _ Sarnak, Piotr ; Valette, Alain (2003), Elementarna teoria liczb, teoria grup i wykresy Ramanujana , London Mathematical Society Student Texts, tom. 55, Cambridge University Press, Cambridge, doi : 10.1017/CBO9780511615825 , ISBN 0-521-82426-5 , MR 1989434
Bibliografia _ Chen, Yong; Ding, Yu (2007), „Na (współ) obwodzie połączonej matroidy”, Discrete Applied Mathematics , 155 (18): 2456–2470, doi : 10.1016/j.dam.2007.06.015 , MR 2365057 .
Bibliografia _
^ Völkel, Christoph Dürr, Louis Abraham i Finn (2016-11-06). „Najkrótszy cykl” . Wypróbuj Algo . Źródło 22.02.2023 .
^ "ds.algorithms - Optymalny algorytm znajdowania obwodu rzadkiego wykresu?" . Wymiana stosu informatyki teoretycznej . Źródło 22.02.2023 .
^ Chang, Hsien-Chih; Lu, Hsueh-I. (2013). „Obliczanie obwodu płaskiego wykresu w czasie liniowym” . SIAM Journal o informatyce . 42 (3): 1077–1094. doi : 10.1137/110832033 . ISSN 0097-5397 .

[1] R. Diestel, Teoria grafów , s. 8. Wydanie 3, Springer-Verlag, 2005

[2] Weisstein, Eric W. , „Obwód” , MathWorld

[3] Brouwer, Andries E. , klatki . Elektroniczny dodatek do książki Distance-Regular Graphs (Brouwer, Cohen i Neumaier 1989, Springer-Verlag).

[4] Bibliografia _ _ _ _ _ _ _ _ _ _ _ _ _

[5] Bibliografia _ _ Sarnak, Piotr ; Valette, Alain (2003), Elementarna teoria liczb, teoria grup i wykresy Ramanujana , London Mathematical Society Student Texts, tom. 55, Cambridge University Press, Cambridge, doi : 10.1017/CBO9780511615825 , ISBN 0-521-82426-5 , MR 1989434

[6] Bibliografia _ Chen, Yong; Ding, Yu (2007), „Na (współ) obwodzie połączonej matroidy”, Discrete Applied Mathematics , 155 (18): 2456–2470, doi : 10.1016/j.dam.2007.06.015 , MR 2365057 .

[7] Bibliografia _

[8] Völkel, Christoph Dürr, Louis Abraham i Finn (2016-11-06). „Najkrótszy cykl” . Wypróbuj Algo . Źródło 22.02.2023 .

[9] "ds.algorithms - Optymalny algorytm znajdowania obwodu rzadkiego wykresu?" . Wymiana stosu informatyki teoretycznej . Źródło 22.02.2023 .

[10] Chang, Hsien-Chih; Lu, Hsueh-I. (2013). „Obliczanie obwodu płaskiego wykresu w czasie liniowym” . SIAM Journal o informatyce . 42 (3): 1077–1094. doi : 10.1137/110832033 . ISSN 0097-5397 .