Степінь вершини (теорія графів) — Вікіпедія
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d6/UndirectedDegrees_%28Loop%29.svg/220px-UndirectedDegrees_%28Loop%29.svg.png)
Степінь вершини (англ. degree, також валентність, англ. valency) в теорії графів — кількість ребер графу , інцидентних вершині . При підрахунку степені ребро-петля враховується двічі[1]. Степінь вершини позначається як , інколи як . Максимальна і мінімальна степені вершин графу G позначаються відповідно Δ(G) і δ(G). На рисунку 1 максимальна степінь дорівнює 5, мінімальна — 0. В регулярному графі степені всіх вершин однакові, тому в цьому випадку можна говорити про степінь графу.
За формулою суми степенів для графу ,
тобто сума степенів вершин будь-якого графу дорівнює подвоєному числу його ребер. Крім того, формула стверджує, що в будь-якому графі число вершин непарного степеня парне. Це твердження (і сама формула) відомі як лема про рукостискання. Назва походить від відомої математичної задачі: необхідно довести, що в будь-якій групі число людей, що потиснули руку непарній кількості інших людей, буде парним.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5d/Conjugate-dessins.svg/200px-Conjugate-dessins.svg.png)
Послідовність степенів вершин неорієнтовного графу є незростаюча послідовність степенів вершин графу[2]. Для графу, зображеного на рисунку 1, вона має вигляд (5, 3, 3, 2, 2, 1, 0). Послідовність степенів вершин є інваріантом графу, при цьому в ізоморфні графи мають однакову послідовність. Проте послідовність степенів вершин не є унікальною характеристикою графу: в деяких випадках не ізоморфні графи також володіють однаковою послідовністю (див. рис. 2).
Проблема послідовностей степенів полягає в знаходженні деяких або усіх графів з заданою незростаючою послідовністю, що складається з натуральних чисел (нульові степені при цьому можуть бути проігноровані, через те, що їх кількість змінюється додаванням або видаленням ізольованих вершин). Послідовність, яка є послідовністю степенів будь-якого графу, називається графічною (англ. graphical sequence). Із формули суми степенів випливає, що будь-яка послідовність з непарною сумою (як, наприклад, 3, 3, 1) не може бути послідовністю степенів графу. Зворотне також вірно: якщо послідовність має парну суму, вона являє собою послідовність степенів мультиграфу. Побудова такого графу здійснюється доволі просто: спочатку ребрами з'єднуються вершини непарних степенів, до вершин, що залишились незаповненими, додаються петлі.
Складніше реалізувати[en] простий граф з заданою послідовністю. Теорема Ердеша — Галлаї[en] стверджує, що незростаюча послідовність di (при i = 1,…,n) може бути послідовністю простого графу тільки якщо її сума парна і виконується нерівність
Відповідно до алгоритму Гавела-Хакімі[en], якщо незростаюча послідовність (d1, d2, …, dn) буде послідовністю степенів простого графу, то (d2 − 1, d3 − 1, …, dd1+1 − 1, dd1+2, dd1+3, …, dn) деяка послідовність степенів простого графу. Цей факт дозволяє побудувати поліноміальний алгоритм знаходження простого графу з визначеною послідовністю.
Співставимо вихідній послідовності чисел вершини графу без ребер з потрібним степенями. Вказане перетворення послідовностей задає як мінімум одну вершину графу, усі інцидентні їй ребра і множина вершин з новими додатками степенів. Впорядкування решти вершини по незростанню додатків степенів, дає незростаючу послідовність степенів простого графу. Повторюючи перетворення і впорядкування не більше n-1 разу, отримуємо весь граф.
Проблема знаходження або оцінки числа графів по заданій послідовності відноситься до перерахування графів.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Depth-first-tree.svg/220px-Depth-first-tree.svg.png)
- Вершина степеня 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.