Регулярен граф
Регулярен граф (още правилен граф, еднороден граф) е термин от теорията на графите, с който се означава граф, при който всеки връх има равен брой съседни върхове, т.е. всички върхове на графа са от една и съща степен.
Тривиалният случай на регулярен граф от нулева степен е граф, състоящ се само от множество върхове, несвързани с ребра (празен граф). Регулярният граф от първа степен се състои от несвързани помежду си ребра. Малко по-сложен е случаят при регулярен граф от степен 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
🔥 Top keywords: Начална страницаHell's Kitchen БългарияКъщата с маймункатаЕргенътНова КаледонияСпециални:ТърсенеПавел VIСловакияРоберт ФицоКъщата с ягодитеДен на светите братя Кирил и Методий, на българската азбука, просвета и култура и на славянската книжовностБългарияСписък на страните по телефонен кодРобърт ГрейСикстинска капелаБергамотИстория на телевизията в БългарияБузовградПФК „Ботев“ (Пловдив)Дяволското гърло (сериал)Виктор АнгеловПарламентарни избори в България (2024)24 майРегистрационен номер на МПС (България)Специални:Последни промениЧервен брег16 майСофияХристо БотевКолю ФичетоВладимир ЗомбориСтиви УондърКирил и МетодийIl VoloКоклюшГеорги АспаруховПаронимСтоян КамбаревНационална купа на България по футбол