Головна

Статечне безліч графа

  1. Авторська позиція в «Анні Кареніній» Л. Толстого. Сенс епіграфа до роману.
  2. Алгоритм укладання графа на площині
  3. Алгоритмічні завдання пошуку в графах: завдання Прима-Краскала, Дейкстри, Форда-Фалкерсона.
  4. Алгоритми обходу графа в ширину і глибину.
  5. АФЧХ, АЧХ і ФЧХ. Комплексна площину для побудови годографа.
  6. Блок-схема електрокардіографа з мікропроцесором і без мікропроцесора.
  7. Блок-схеми електрокардіографа

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

 Статечне безліч графа G позначимо через S (G). Так, для графа G, зображеного на рис. 52.1, S (G) = = {1, 2, 3}.

Хоча статечна послідовність графа задовольняє певним умовам, проте статечним безліччю графа може бути довільне безліч. Про це свідчить наступна

Теорема 52.1. Будь-яке кінцеве безліч S натуральних чисел є статечним безліччю деякого порогового графа. Мінімальний порядок таких графів дорівнює s +1, де s - максимальне число з множини S. Очевидно, що з цієї теореми випливає

Слідство 52.2. Будь-яке кінцеве безліч цілих, невід'ємних чисел є статечним безліччю деякого графа.

 
 

 Доказ теореми 52.1. якщо S (G) = = S, то \ G \ ? s + 1, так що потрібно тільки довести існування відповідного графа G. Затвердження тривіально для одноелементна безлічі S, оскільки S (Kn) = {N - 1}. нехай тепер

 
 

 і нехай, для визначеності, п = 2р - парне число. Потрібний граф будемо шукати у вигляді

де КХ° Н граф, отриманий з графа Н додаванням х домінуючих вершин, а ОУ° Н - Граф, отриманий з графа Н додаванням у ізольованих вершин. Будь-граф виду (1) є граничним. Спробуємо підібрати числа ха и y? в натуральному вираженні (1) так, щоб виконувалося - рівність S (G) = S. Для цього має бути

 
 

 
 

 Очевидно, що система уравненій (2) щодо невідомих хi, Yj (i = 1, p, j = 1, р) має рішення, всі координати якого є позитивними:

 
 

 Підставивши у вираз (1) числа, що визначаються рівностями (3), отримаємо граф G, для котрого S (G) = S. Число його вершин одно

 
 

 для непарного п = 2р + 1 побудова аналогічно, толь-to замість формули (1) використовується формула


глава IX



порогові графи | Основні визначення

Ейлерови графи | глава VIII | графічна послідовність | Критерії графичности послідовності | Реалізація графічної послідовності з максимальною связностью | Гамильтонова реалізація графічної послідовності | розщеплюються графи | Полустепені результату і полустепені заходу | База і ядро |

© um.co.ua - учбові матеріали та реферати