Regulární graf

V teorii grafů je regulární graf (pravidelný) takový graf, jehož všechny vrcholy mají stejný stupeň. Regulární graf s vrcholy, které mají stupeň k, se nazývá k-regulární.

Regulární grafy stupně nejvýše 2 lze jednoduše popsat: 0-regulární graf se skládá ze samostatných vrcholů (bez hran), 1-regulární ze samostatných hran a 2-regulární ze samostatných cyklů. 3-regulární graf se nazývá kubický.

Soubor:0-regular graph.svg|0-regulární graf Soubor:1-regular graph.svg|1-regulární graf Soubor:2-regular graph.svg|2-regulární graf Soubor:3-regular graph.svg|3-regulární graf

Silně regulární graf je takový graf, v němž má každá dvojice sousedních vrcholů stejný počet k společných sousedů a každá dvojice nesousedních vrcholů stejný počet n společných sousedů. Nejmenší regulární graf, který není silně regulární, je cyklický graf na 6 vrcholech.

Úplný graf Kn je silně regulární pro libovolné n.

Externí odkazy

Kategorie:Typy grafů