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

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

Властивості

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

Приклади

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

• 
  0-регулярний граф
• 
  1-регулярний граф
• 
  2-регулярний граф
• 
  3-регулярний граф
• 
  3-регулярний граф
• 
  3-регулярний граф
• 
  4-регулярний граф

Див. також

• Граф Генсона
• Граф Геммінга
• Графи Чана
• Два-граф