Wykres kwartalny
W matematycznej dziedzinie teorii grafów graf kwartalny to graf , w którym wszystkie wierzchołki mają stopień 4. Innymi słowy, graf kwartalny to graf 4-regularny .
Przykłady
Kilka dobrze znanych grafów jest kwartalnych. Zawierają:
- Pełny graf K 5 , graf kwartalny z 5 wierzchołkami, najmniejszy możliwy graf kwartalny.
- Graf Chvátal , kolejny graf kwartalny z 12 wierzchołkami, najmniejszy graf kwartalny, który nie ma trójkątów i nie można go pokolorować trzema kolorami.
- Graf Folkmana , graf kwartalny z 20 wierzchołkami, najmniejszy graf półsymetryczny .
- Graf Mereditha , graf kwartalny z 70 wierzchołkami, który jest 4-połączony , ale nie ma cyklu Hamiltona , obalający przypuszczenie Crispina Nasha-Williamsa .
Każdy wykres środkowy jest wykresem płaszczyzny kwartalnej , a każdy wykres płaszczyzny kwartalnej jest wykresem środkowym pary grafów dwupłaszczyznowych lub multigrafów. Diagramy węzłów i diagramy połączeń są również multigrafami płaszczyzny kwarcowej , w których wierzchołki reprezentują przecięcia diagramu i są oznaczone dodatkowymi informacjami o tym, która z dwóch gałęzi węzła przecina drugą gałąź w tym punkcie.
Nieruchomości
Ponieważ stopień każdego wierzchołka w grafie kwartalnym jest parzysty, każdy spójny graf kwartalny ma trasę Eulera . Podobnie jak w przypadku zwykłych grafów dwudzielnych bardziej ogólnie, każdy dwudzielny graf kwartalny ma idealne dopasowanie . W tym przypadku możliwy jest znacznie prostszy i szybszy algorytm znajdowania takiego dopasowania niż w przypadku grafów nieregularnych: wybierając co drugą krawędź trasy Eulera, można znaleźć dwuczynnikowy , który w tym przypadku musi być zbiorem cykli, każdy o parzystej długości, z każdym wierzchołkiem grafu występującym dokładnie w jednym cyklu. Wybierając ponownie co drugą krawędź w tych cyklach, uzyskuje się idealne dopasowanie w czasie liniowym . Tej samej metody można również użyć do pokolorowania krawędzi wykresu czterema kolorami w czasie liniowym.
Grafy kwartyczne mają parzystą liczbę rozkładów hamiltonowskich .
Otwarte problemy
Jest otwartą hipotezą, czy wszystkie kwartalne grafy Hamiltona mają parzystą liczbę obwodów Hamiltona , czy też mają więcej niż jeden obwód Hamiltona. Wiadomo, że odpowiedź jest fałszywa dla multigrafów kwartalnych .