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ý.

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

Média použitá na této stránce

0-regular graph.svg
Autor: 0x24a537r9, Licence: CC BY-SA 3.0
An example of a 0-regular graph
1-regular graph.svg
Autor: 0x24a537r9, Licence: CC BY-SA 3.0
An example of a 1-regular graph
2-regular graph.svg
Autor: 0x24a537r9, Licence: CC BY-SA 3.0
An example of a 2-regular graph
3-regular graph.svg
Autor: 0x24a537r9, Licence: CC BY-SA 3.0
An example of a 3-regular graph