Відкрити головне меню
Рисунок 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). Послідовність степенів вершин є інваріантом графа, при цьому в ізоморфні графи мають однакову послідовність. Проте послідовність степенів вершин не є унікальною характеристикою графа: в деяких випадках не ізоморфні графи також володіють однаковою послідовністю (див. рис. 2).

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

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

 

Згідно до алгоритму Гавела-Хакімі[en], якщо незростаюча послідовність (d1d2, …, dn) буде послідовністю степенів простого графа, то (d2 − 1, d3 − 1, …, dd1+1 − 1, dd1+2, dd1+3, …, dn) деяка послідовність степенів простого графа. Цей факт дозволяє побудувати поліноміальний алгоритм знаходження простого графа з визначеною послідовністю.

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

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

Окремі випадкиРедагувати

 
Рисунок 3. Кінцевими вершинами є 4, 5, 6, 7, 10, 11 и 12.
  • Вершина степеня 0 називається ізольованою.
  • Вершина степеня 1 називається кінцевою (англ. end vertex), висячою (англ. pendant vertex) або листком графу (англ. leaf vertex). Ребро, інцидентне такій вершині називається висячим (англ. terminal (pendant) edge, end-edge). На рисунку 3 висячим ребром є {3,5}. Така термінологія застосовується як при дослідженні дерев в цілому, так і структур даних.
  • Вершина степеня n-1 графа порядку n називається домінуючою[en] (англ. dominating vertex) або універсальною (англ. universal vertex).

Загальні властивостіРедагувати

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

ПриміткиРедагувати

  1. Diestel стор. 5
  2. Diestel стор. 278

Див. такожРедагувати

ДжерелаРедагувати