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