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

Рисунок 1. Граф з відміченими степенями вершин.

Степінь вершини (англ. degree, також валентність, англ. valency) в теорії графів — кількість ребер графу $G$, інцидентних вершині $v$. При підрахунку степені ребро-петля враховується двічі. Степінь вершини позначається як $\deg(v)$, інколи як $d(v)$. Максимальна і мінімальна степені вершин графу G позначаються відповідно Δ(G) і δ(G). На рисунку 1 максимальна степінь дорівнює 5, мінімальна — 0. В регулярному графі степені всіх вершин однакові, тому в цьому випадку можна говорити про степінь графу.

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

За формулою суми степенів для графу $G=(V,E)$,

$\sum _{v\in V}\deg(v)=2|E|\,,$

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

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

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

Послідовність степенів вершин неорієнтовного графу є незростаюча послідовність степенів вершин графу. Для графу, зображеного на рисунку 1, вона має вигляд (5, 3, 3, 2, 2, 1, 0). Послідовність степенів вершин є інваріантом графу, при цьому в ізоморфні графи мають однакову послідовність. Проте послідовність степенів вершин не є унікальною характеристикою графу: в деяких випадках не ізоморфні графи також володіють однаковою послідовністю (див. рис. 2).

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

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

$\sum _{i=1}^{k}d_{i}\leq k(k-1)+\sum _{i=k+1}^{n}\min(d_{i},k)\quad \ k\in \{1,\dots ,n-1\}\,.$

Відповідно до алгоритму Гавела-Хакімі, якщо незростаюча послідовність (d₁, d₂, …, d_n) буде послідовністю степенів простого графу, то (d₂ − 1, d₃ − 1, …, d_d1+1 − 1, d_d1+2, d_d1+3, …, d_n) деяка послідовність степенів простого графу. Цей факт дозволяє побудувати поліноміальний алгоритм знаходження простого графу з визначеною послідовністю.

Співставимо вихідній послідовності чисел вершини графу без ребер з потрібним степенями. Вказане перетворення послідовностей задає як мінімум одну вершину графу, усі інцидентні їй ребра і множина вершин з новими додатками степенів. Впорядкування решти вершини по незростанню додатків степенів, дає незростаючу послідовність степенів простого графу. Повторюючи перетворення і впорядкування не більше 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 називається домінівною (англ. dominating vertex) або універсальною (англ. universal vertex).

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

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

Див. також

• Степенева матриця

Джерела

• Diestel, Reinhard (2005), Graph Theory (вид. 3rd), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4.
• Erdős, P.; Gallai, T. (1960), Gráfok előírt fokszámú pontokkal (PDF), Matematikai Lapok (Hungarian) , 11: 264—274.
• Havel, Václav (1955), A remark on the existence of finite graphs, Časopis pro pěstování matematiky (Czech) , 80: 477—480
• Hakimi, S. L. (1962), On realizability of a set of integers as degrees of the vertices of a linear graph. I, Journal of the Society for Industrial and Applied Mathematics, 10: 496—506, MR 0148049.
• Sierksma, Gerard; Hoogeveen, Han (1991), Seven criteria for integer sequences being graphic, Journal of Graph Theory, 15 (2): 223—231, doi:10.1002/jgt.3190150209, MR 1106533.