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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

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

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

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


Източници[редактиране | edit source]

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