Ступінь вершини (теорія графів) - це

Мал. 1. Граф, на вершинах якого відзначені ступеня.

Ступінь вершини (англ. Degree. Також валентність. Англ. Valency) в теорії графів - кількість ребер графа, інцидентних вершині. При підрахунку ступеня ребро-петля враховується двічі. [1] Ступінь вершини позначається як (в західних джерелах -). Максимальна і мінімальна ступінь вершин графа G позначаються відповідно Δ (G) і δ (G). На рис. 1 максимальний ступінь дорівнює 5, мінімальна - 0. В регулярному графі ступеня всіх вершин однакові, тому в даному випадку можна говорити про ступінь графа.

Лемма про рукостискання

За формулою суми ступенів для графа,

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

Послідовність ступенів вершин

Мал. 2. Два неізоморфних графа з однаковою послідовністю ступенів (3, 2, 2, 2, 2, 1, 1, 1).

Послідовність ступенів вершин неорієнтованого графа є незростаюча послідовністю. [2] Для графа, зображеного на рис. 1, вона має вигляд (5, 3, 3, 2, 2, 1, 0). Послідовність ступенів вершин є інваріант графа. тому у ізоморфних графів вона однакова. Однак послідовність ступенів вершин не є унікальною ХАРАКТИРИСТИКИ графа: в деяких випадках неізоморфних графи також мають однакову послідовністю.

Проблема послідовності ступенів полягає в знаходженні деяких або всіх графів із заданою незростаюча послідовністю, що складається з натуральних чисел (нульові ступеня при цьому можуть бути проігноровані, так як їх кількість змінюється додаванням або видаленням ізольованих вершин). Послідовність, що є послідовністю ступенів будь-якого графа, називається графічної (англ. Graphical sequence). З формули суми ступенів слід, що будь-яка послідовність з непарної сумою (як, наприклад, 3, 3, 1) не може бути послідовністю ступенів графа. Зворотне також вірно: якщо послідовність має парну суму, вона являє собою послідовність ступенів мультиграфом. Побудова такого графа здійснюється досить простим способом: необхідно об'єднати вершини непарних ступенів в пари. до решти незаповненими вершин слід додати петлі.

Складніше реалізувати простий граф із заданою послідовністю. Теорема Ердеша - Галлай стверджує, що незростаюча послідовність di (при i = 1, ..., n) може бути послідовністю простого графа тільки якщо її сума парна і виконується нерівність

Наприклад, послідовність (3, 3, 3, 1) не може бути послідовністю простого графа; вона задовольняє нерівності Ердеша - Галлай тільки при k дорівнює 1, 2 або 4, але не при k рівному 3.

С. Л. Хакимі довів, що (d1, d2, ..., dn) є послідовність ступенів простого графа тільки якщо існує (d2 - 1, d3 - 1, ..., dd1 +1 - 1, dd1 +2. Dd1 +3. ..., dn). Цей факт дозволив розробити простий алгоритм знаходження простого графа із заданою реалізованої послідовністю:

Спочатку граф не має ребер.
Складається список вершин, для яких вимоги за ступенями поки не задоволені. Решта вимоги розташовуються в порядку незростання.
Перша вершина з'єднується з наступними d1 вершинами зі списку. Після цього перша вершина видаляється, список пересортіруется. Дія повторюється до тих пір, поки всі вимоги не будуть задоволені.

Проблема знаходження або оцінки числа графів по заданій послідовності відноситься до області перерахування графів.

Приватні значення

Мал. 3. кінцевими вершинами є 4, 5, 6, 7, 10, 11 і 12.

Вершина ступеня 0 називається ізольованою.
Вершина ступеня 1 називається кінцевий (англ. End vertex), висячої (англ. Pendant vertex) або листом графа (англ. Leaf vertex). Ребро, інцидентне такій вершині називається висячим (англ. Terminal (pendant) edge, end-edge). На рис. 3 висячим ребром є. Подібна термінологія використовується в вивченні дерев в загальному і як структур даних.
Вершина ступеня n-1 графа порядку n називається домінуючою (англ. Dominating vertex).

загальні властивості

Якщо все вершини графа мають однаковий ступінь k. граф називають k -Регулярно або регулярним графом ступеня k. У цьому випадку сам граф має ступінь k.
Ейлером шлях існує в неорієнтованому, зв'язкового графі якщо і тільки якщо граф має 0 або 2 вершини непарної ступеня. Якщо граф містить 0 вершин непарної ступеня, Ейлеров шлях є циклом.
Орграф є псевдолесом тільки якщо полустепені заходу кожної вершини не більше 1. Функціональний граф - окремий випадок псевдолеса, в якому полустепені заходу всіх вершин рівні 1.
Згідно з теоремою Брукса, хроматичної число будь-якого графа за винятком кліки або непарного циклу не перевищує максимально його вершин (Δ). Згідно з теоремою Візінга, хроматичний індекс будь-якого графа не перевищує Δ + 1.
k -вирожденним графом називається граф, в якому кожен підграф має вершину ступенем не більше k.

Полустепені заходу і полустепені результату вершин орієнтованих графів
розподіл ступенів

Примітки

Дивитися що таке "Ступінь вершини (теорія графів)" в інших словниках:

Дуга (теорія графів) - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія

Цикл (теорія графів) - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія

Дерево (теорія графів) - Цей термін має також інші значення див. Дерево (значення). Дерево це зв'язний ациклічний граф. [1] Можливості підключення означає наявність шляхів між будь-якою парою вершин, ациклічності відсутність циклів і те, що між парами вершин ... ... Вікіпедія

Графів теорія - розділ кінцевої математики (Див. Кінцева математика), особливістю якого є геометричний підхід до вивчення об'єктів. Основне поняття теорії граф. Граф задається безліччю вершин (точок) і безліччю ребер (зв'язків), що з'єднують ... Велика радянська енциклопедія

Глосарій теорії графів - Ця сторінка глосарій. Див. Також основну статтю: Теорія графів Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці) ... Вікіпедія

Словник термінів теорії графів - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И К Л М Н О П Р С ... Вікіпедія

Практичне застосування розмальовки графів - Цю статтю слід вікіфіціровать. Будь ласка, оформіть її згідно з правилами оформлення статей. Розфарбування графів практично застосовується (постановку задачі разлічіних розмальовок тут обговорюватися не буде) дл ... Вікіпедія

Вершина (граф) - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія

Довжина шляху в орграфе - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія

Ступінь вершини (теорія графів). Джессі Рассел. Ця книга буде виготовлена в відповідності з Вашим замовленням за технологією Print-on-Demand. High Quality Content by WIKIPEDIA articles! Ступінь вершини (англ. Degree, також валентність, англ. ... Детальніше Купити за 1125 руб