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

Регулярним графом у теорії графів називають граф, кожна вершина якого має однаковий степінь (тобто кількість суміжних вершин). Якщо даний степінь дорівнює k, то граф називають k-регулярним.

Властивості

Граф є регулярним тоді і тільки тоді, коли вектор ${\textbf {j}}=(1,\dots ,1)$ є власним вектором його матриці суміжності.[1]
Теорема Неш-Вільямса — довільний k-регулярний граф з $(2k+1)$ - єю вершиною є гамільтоновим.

Приклади

Довільний повний граф є регулярним.

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.