Rodiny grafů definované jejich automorfismy | ||||
---|---|---|---|---|
vzdálenost-tranzitivní | → | pravidelná vzdálenost | ← | velmi pravidelné |
↓ | ||||
symetrický (oblouk-tranzitivní) | ← | t -transitivní, ( t ≥ 2) | symetrický vlevo (v) | |
↓ | ||||
(je-li připojen) vrchol-tranzitivní a hrana-tranzitivní |
→ | pravidelné a hranové tranzitivní | → | hrana tranzitivní |
↓ | ↓ | ↓ | ||
top-tranzitivní | → | pravidelný | → |
(je-li bipartitní) biregular |
↑ | ||||
Cayleyův graf | ← | nulově symetrický | asymetrický |
V teorii grafů , je pravidelný graf je graf, kde jsou všechny vrcholy mají stejný počet sousedů, to znamená stejný stupeň nebo mocnost. Pravidelný graf, jehož vrcholy jsou stupně, se nazývá běžný graf nebo pravidelný graf stupňů .
Normální graf 0 je sada odpojených vrcholů; 1-pravidelný graf má sudý počet vrcholů a je množinou odpojených nebo spojovacích hran ; konečně, 2-pravidelný graf je sada odpojených cyklů . 3-pravidelný graf se také nazývá kubický graf .
0-pravidelný graf
1-pravidelný graf
2-pravidelný graf
Petersenův graf (konkrétní kubický graf)
2-pravidelný nekonečný graf
Silně pravidelný graf je pravidelný graf, kde každý pár sousedních vrcholů má stejný počet sousedů společná, a každý pár nesousedících vrcholů má stejný počet sousedů společné. Nejmenší grafy, které jsou pravidelné, aniž by byly silně pravidelné, jsou cyklický graf a cirkulující graf , oba se 6 vrcholy. Úplný graf je silně pravidelný pro všechny
Nutnou a dostatečnou podmínkou pro existenci pravidelného grafu s vrcholy je to, že je sudé a to .
Věta Crispina Nash-Williamse uvádí, že jakýkoli pravidelný graf s vrcholy připouští hamiltonovský cyklus .
Dovolit být matice sousednosti z grafu. Z grafu je pravidelná tehdy a jen tehdy, pokud je vlastní vektor z . Když se jedná o vlastní vektor, odpovídá vlastnímu číslu, které se rovná stupni grafu.
Mnoho problémů s grafy je obtížné, i když se omezíme na třídu běžných grafů. Přesněji, zbarvení , problém s cestujícím prodejcem a problém s maximální stabilitou jsou NP obtížné pro běžné grafy a dokonce i pro k -pravidelné grafy s fixním k .
Na druhé straně lze o problému izomorfismu grafů rozhodnout v polynomiálním čase na grafech omezeného stupně, například pravidelných grafech.
Pravidelné grafy lze generovat pomocí softwaru GenReg.