Регулярен граф

Регулярен граф (още правилен граф, еднороден граф) е термин от теорията на графите, с който се означава граф, при който всеки връх има равен брой съседни върхове, т.е. всички върхове на графа са от една и съща степен.

Тривиалният случай на регулярен граф от нулева степен е граф, състоящ се само от множество върхове, несвързани с ребра (празен граф). Регулярният граф от първа степен се състои от несвързани помежду си ребра. Малко по-сложен е случаят при регулярен граф от степен 2, тъй като графът може да е безкраен или краен, като крайният граф може да е свързан или несвързан. Краен свързан регулярен граф от втора степен се нарича цикъл.

За регулярните графи са в сила следните твърдения (теореми):

• Броят на върховете на краен регулярен граф от нечетна степен е винаги четно число.
• За краен регулярен граф от степен k с m на брой върхове, броят на ребрата M = k.m / 2.
• За всяко четно естествено число m ≥ 4 съществува краен регулярен граф от трета степен с m на брой върхове.
• Всеки краен регулярен граф от степен k с 2k + 1 върха съдържа Хамилтонов цикъл. (Теорема на Криспин Наш-Уилямс)

• Регулярни графи
• 
  Краен регулярен граф от степен 0
• 
  Краен регулярен граф от степен 1
• 
  Краен несвързан регулярен граф от степен 2 (два цикъла)
• 
  Безкраен регулярен граф от степен 2
• 
  Краен регулярен граф от степен 3 с 4 върха
• 
  Краен регулярен граф от степен 3 с 6 върха
• 
  Краен регулярен граф от степен 3 с 8 върха
• 
  Краен регулярен граф от степен 3 с 20 върха
• 
  Безкраен регулярен граф от 3 степен
• 
  Краен регулярен граф от 4 степен с 6 върха

Източници

• „Теория на графите“, Иржи Седлачек, „Наука и изкуство“, София, 1967
• ((en)) Regular Graph, Wolfram MathWorld