Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

Регулярний граф - граф, ступеня всіх вершин якого рівні, тобто кожна вершина має однакову кількість сусідів. Ступінь регулярності є інваріантом графа і позначається r (G) . Для нерегулярних графів r (G) не визначено. Регулярні графи представляють особливу складність для багатьох алгоритмів.

Регулярний граф з вершинами ступеня k називається k -Регулярним, або регулярним графом ступеня k .

Регулярні графи мірою не більше двох легко класифікувати: 0-регулярний граф складається з ізольованих вершин (нуль-граф), 1-регулярний - з ізольованих ребер, а 2-регулярний - з розрізнених циклів.

3-регулярний граф відомий також як кубічний.

Сильно регулярний граф є регулярний граф, у якого кожна пара суміжних вершин має однакову кількість l загальних сусідів, і кожна пара несуміжних вершин має однакову кількість n загальних сусідів. Найменші графи, які регулярні, але не сильно регулярні - циклічний граф і ціркулянтний граф на шести вершинах.

Повний граф K m є сильно регулярним для будь-якого m .

Теорема Неш-Вільямса свідчить, що кожен k -Регулярний граф на 2 k + 1 вершинах має гамільтонів цикл.

  • 0-регулярний граф

  • 1-регулярний граф

  • 2-регулярний граф

  • 3-регулярний граф


1. Алгебраїчні властивості

Нехай A є матриця суміжності графа. Тоді граф регулярний тоді і тільки тоді, коли \ Textbf {j} = (1, \ dots, 1) є власний вектор A. [1] Його власне число буде постійною ступенем графа. Власні вектори, відповідні іншим власним числам, ортогональні \ Textbf {j} , Тому для власних векторів v = (v_1, \ dots, v_n) ми маємо \ Sum_ {i = 1} ^ n v_i = 0 .

Регулярний граф ступеня k зв'язний тоді й тільки тоді, коли власне число k має одиничну кратність. [1]

Інший критерій регулярності і зв'язності графа: граф зв'язний і регулярний тільки і тільки тоді, коли матриця J з J i j = 1 знаходиться в алгебрі суміжності графа.

Нехай G є k-регулярний граф діаметра D і з власними числами матриці суміжності k = \ lambda_0> \ lambda_1 \ geq \ dots \ geq \ lambda_ {n-1} . Якщо G не двудолен:

D \ leq \ frac {\ log {(n-1)}} {\ log (k / \ lambda)} +1

то

\ Lambda = \ max_ {i> 0} \ {\ mid \ lambda_i \ mid \} . [джерело не вказано 671 день]


2. Генерація

Регулярний граф можна згенерувати програмою GenReg. [2]

Примітки

  1. 1 2 Д. М. Цветкович, М. Дуб і Х. Сачс, "Спектр графів: теорія і застосування", 3-я редакція, Нью-Йорк: Уайлі, 1998.
  2. М. Мерінгер, "Теорія графів", 1999, 30, 137.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Регулярний парк
Граф
Граф Нулін
Граф Петерсена
Граф, Девід
Граф, Штеффі
Граф Монтенегро
Граф алгоритму
Граф Ессекс
© Усі права захищені
написати до нас
Рейтинг@Mail.ru