Rodziny grafów określone przez ich automorfizmy | ||||
---|---|---|---|---|
odległość-przechodnia | → | regularne odległości | ← | mocno regularne |
↓ | ||||
symetryczny (przechodni łuku) | ← | t - przechodnie, ( t ≥ 2) | symetryczny lewy ( cal ) | |
↓ | ||||
(jeśli są połączone) przechodnie przez wierzchołki i przechodnie od krawędzi |
→ | regularne i przechodnie krawędziowe | → | przechodnia krawędziowa |
↓ | ↓ | ↓ | ||
przechodni w górę | → | regularny | → |
(jeśli dwustronne) dwurzędowe |
↑ | ||||
Wykres Cayleya | ← | zero-symetryczny | asymetryczny |
W teorii wykres , A regularne wykres jest wykres, na którym wszystkie wierzchołki posiadają taką samą liczbę sąsiadów, to znaczy sam poziom lub wartościowość. Zwykły wykres, którego wierzchołki określają stopień, nazywany jest zwykłym wykresem lub regularnym wykresem stopnia .
Graf regularny 0 to zbiór niepowiązanych wierzchołków; 1-regularny graf ma parzystą liczbę wierzchołków i jest zbiorem rozłączonych lub sprzęgających się krawędzi ; wreszcie, 2-regularny wykres to zbiór odłączonych cykli . 3-regularny wykres jest również nazywany wykresem sześciennym .
0-regularny wykres
1-regularny wykres
2-regularny wykres
Wykres Petersena (konkretny wykres sześcienny)
2-regularny wykres nieskończony
Bardzo regularny graf to zwykły graf, w którym każda para sąsiednich wierzchołków ma taką samą liczbę wspólnych sąsiadów, a każda para niesąsiadujących wierzchołków ma taką samą liczbę wspólnych sąsiadów. Najmniejsze wykresy, które są regularne, ale nie są zbyt regularne, to wykres cykliczny i wykres krążący , oba z 6 wierzchołkami. Graf pełny jest silnie regularny dla wszystkich
Warunkiem koniecznym i wystarczającym dla istnienia regularnego grafu z wierzchołkami jest to, aby był parzysty i taki .
Twierdzenie Crispina Nash-Williamsa stwierdza, że każdy regularny graf z wierzchołkami dopuszcza cykl Hamiltona .
Pozwolić macierz sąsiedztwa z wykresu. Wykres jest regularny wtedy i tylko wtedy jest wektorem własnym z . Kiedy jest wektorem własnym, odpowiada wartości własnej, która jest równa stopniowi wykresu.
Wiele problemów z wykresami jest trudnych, nawet jeśli ograniczymy się do klasy zwykłych wykresów. Dokładniej, farbowanie , podróżowanie sprzedawca problemem i problemem maksymalne stabilne są NP-trudne dla zwykłych wykresów, a nawet k -regular wykresach z k stałej.
Z drugiej strony, problem izomorfizmu grafów można rozstrzygnąć w czasie wielomianowym na wykresach o ograniczonym stopniu, na przykład na grafach regularnych.
Regularne wykresy można generować za pomocą oprogramowania GenReg.