Регулярним графом у теорії графів називають граф, кожна вершина якого має однаковий степінь (тобто кількість суміжних вершин). Якщо даний степінь дорівнює k, то граф називають k-регулярним.
Властивості
- Граф є регулярним тоді і тільки тоді, коли вектор
є власним вектором його матриці суміжності.
- Теорема Неш-Вільямса — довільний 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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Regulyarnim grafom u teoriyi grafiv nazivayut graf kozhna vershina yakogo maye odnakovij stepin tobto kilkist sumizhnih vershin Yaksho danij stepin dorivnyuye k to graf nazivayut k regulyarnim VlastivostiGraf ye regulyarnim todi i tilki todi koli vektor j 1 1 displaystyle textbf j 1 dots 1 ye vlasnim vektorom jogo matrici sumizhnosti Teorema Nesh Vilyamsa dovilnij k regulyarnij graf z 2 k 1 displaystyle 2k 1 yeyu vershinoyu ye gamiltonovim PrikladiDovilnij povnij graf ye regulyarnim 0 regulyarnij graf 1 regulyarnij graf 2 regulyarnij graf 3 regulyarnij graf 3 regulyarnij graf 3 regulyarnij graf 4 regulyarnij grafDiv takozhGraf Gensona Graf Gemminga Grafi Chana Dva grafPrimitkiCvetkovic D M Doob M and Sachs H Spectra of Graphs Theory and Applications 3rd rev enl ed New York Wiley 1998