Регулярний граф
Регулярним графом у теорії графів називають граф, кожна вершина якого має однаковий степінь (тобто кількість суміжних вершин). Якщо даний степінь дорівнює k, то граф називають k-регулярним.
Властивості
- Граф є регулярним тоді і тільки тоді, коли вектор є власним вектором його матриці суміжності.[1]
- Теорема Неш-Вільямса — довільний k-регулярний граф з - єю вершиною є гамільтоновим.
Приклади
Довільний повний граф є регулярним.
-
0-регулярний граф
-
1-регулярний граф
-
2-регулярний граф
-
3-регулярний граф
-
3-регулярний граф
-
3-регулярний граф
-
4-регулярний граф
Примітки
- ↑ Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.