Перегляд вихідного коду сторінки Степінь вершини (теорія графів)

[[Файл:UndirectedDegrees (Loop).svg|thumb|Рисунок 1. Граф з відміченими степенями вершин.]]

'''Степінь вершини''' ({{lang-en|degree}}, також '''валентність''', {{lang-en|valency}}) в [[Теорія графів|теорії графів]]&nbsp;— кількість ребер графа <math>G</math>, [[Словник термінів теорії графів#Інцидентність|інцидентних]] вершині <math>v</math>. При підрахунку степені ребро-[[Петля (теорія графів)|петля]] враховується двічі<ref>Diestel стор. 5</ref>. Степінь вершини позначається як <math>\deg(v)</math>, інколи як <math>d(v)</math>. Максимальна і мінімальна степені вершин графа G позначаються відповідно Δ(''G'') і δ(''G''). На рисунку 1 максимальна степінь дорівнює 5, мінімальна&nbsp;— 0. В [[Регулярний граф|регулярному графі]] степені всіх вершин однакові, тому в цьому випадку можна говорити про ''степінь графа''.

== Лема про рукостискання ==
{{main|Лема про рукостискання}}
За '''формулою суми степенів''' для графа <math>G=(V, E)</math>,

: <math>\sum_{v \in V} \deg(v) = 2|E|\, ,</math>

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

== Послідовність степенів вершин ==
[[Файл:Conjugate-dessins.svg|thumb|200px|Рисунок 2. Два не [[Ізоморфізм графів|ізоморфні графи]] з однаковою послідовністю степенів (3, 2, 2, 2, 2, 1, 1, 1).]]

'''Послідовність степенів вершин''' неорієнтовного графа є [[Монотонна послідовність|незростаюча послідовність]] степенів вершин графа<ref>Diestel стор. 278</ref>. Для графа, зображеного на рисунку 1, вона має вигляд (5, 3, 3, 2, 2, 1, 0). Послідовність степенів вершин є [[інваріант графа|інваріантом графа]], при цьому в [[Ізоморфізм графів|ізоморфні]] графи мають однакову послідовність. Проте послідовність степенів вершин не є унікальною характеристикою графа: в деяких випадках не ізоморфні графи також володіють однаковою послідовністю (див. рис. 2).

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

Складніше {{Нп|Задача про реалізацію графа|реалізувати||Graph realization problem}} [[Словник термінів теорії графів#Простий граф|простий граф]] з заданою послідовністю. {{нп|Теорема Ердеша — Галлаї|||Erdős–Gallai theorem}} стверджує, що незростаюча послідовність ''d''<sub>''i''</sub> (при ''i'' = 1,…,''n'') може бути послідовністю простого графа ''тільки'' якщо її сума парна і виконується нерівність
: <math>\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\} \, .</math>

Згідно до {{Нп|алгоритм Гавела-Хакімі|алгоритму Гавела-Хакімі||Havel–Hakimi algorithm}}, якщо незростаюча послідовність (''d''<sub>1</sub>, ''d''<sub>2</sub>, …, ''d''<sub>''n''</sub>) буде послідовністю степенів простого графа, то (''d''<sub>2</sub> − 1, ''d''<sub>3</sub> − 1, …, ''d''<sub>''d''<sub>1</sub>+1</sub> − 1, ''d''<sub>''d''<sub>1</sub>+2</sub>, ''d''<sub>''d''<sub>1</sub>+3</sub>, …, ''d''<sub>''n''</sub>) деяка послідовність степенів простого графа. Цей факт дозволяє побудувати поліноміальний алгоритм знаходження простого графа з визначеною послідовністю.

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

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

== Окремі випадки ==
[[Файл:Depth-first-tree.svg|thumb|Рисунок 3. Кінцевими вершинами є 4, 5, 6, 7, 10, 11 и 12.]]
* Вершина степеня 0 називається [[Вершина (теорія графів)#Типи вершин|ізольованою]].
* Вершина степеня 1 називається ''кінцевою'' ({{lang-en|end vertex}}), ''висячою'' ({{lang-en|pendant vertex}}) або ''листком'' графу ({{lang-en|leaf vertex}}). Ребро, інцидентне такій вершині називається ''висячим'' ({{lang-en|terminal (pendant) edge, end-edge}}). На рисунку 3 висячим ребром є {3,5}. Така термінологія застосовується як при дослідженні [[Дерево (теорія графів)|дерев]] в цілому, так і [[Дерево (структура даних)|структур даних]].
* Вершина степеня ''n-1'' графа порядку ''n'' називається {{Нп|Універсальна вершина|домінуючою||Universal vertex}} ({{lang-en|dominating vertex}}) або універсальною ({{lang-en|universal vertex}}).

== Загальні властивості ==
* Якщо всі вершини графа мають однаковий степінь ''k'', граф називається ''k''-[[Регулярний граф|регулярним]] або регулярним графом степеня ''k''. В цьому випадку граф має степінь ''k''. Аналогічно, [[двочастковий граф]] у якого кожна пара вершин однієї частки має однакові степені, називається {{Нп|Бірегулярний граф|бірегулярним графом||Biregular graph}}.
* [[Ейлерів ланцюг]] існує в [[Орієнтований граф|неорієнтованому]], [[Зв'язний граф|зв'язному]] графі якщо і тільки якщо граф має 0 або 2 вершини непарного степеня. Якщо граф містить 0 вершин непарного степеня, Ейлерів ланцюг є Ейлеровим циклом.
* [[Орієнтований граф|Орграф]] є {{Нп|псевдоліс|псевдолісом||Pseudoforest}} тоді, і тільки тоді, коли півстепінь виходів з кожної вершини не перевищує 1. Функціональний граф&nbsp;— частковий випадок псевдолісу, у котрому півстепені виходів всіх вершин дорівнюють 1.
* Згідно [[Теорема Брукса|теоремі Брукса]], [[хроматичне число]] будь-якого графа за виключенням [[Кліка (теорія графів)|кліки]] або непарного циклу не перевищує максимального степеня його вершин Δ. Згідно [[Теорема Візінга|теореми Візінга]], [[хроматичний індекс]] будь-якого графа не перевищує Δ + 1.
* ''k''-{{Нп|Виродженість (теорія графів)|виродженим||Degeneracy (graph theory)}} графом називається граф, в котрому кожен підграф має вершину зі степенем не більше ''k''.

== Примітки ==
{{Примітки}}

== Див. також ==
* [[Степенева матриця]]

== Джерела ==
*{{Citation | last1=Diestel | first1=Reinhard | title=Graph Theory | url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ | publisher=Springer-Verlag | location=Berlin, New York | edition=3rd | isbn=978-3-540-26183-4 | year=2005 }}.
*{{citation|first1=P.|last1=Erdős|author1-link=Пал Ердеш|first2=T.|last2=Gallai|author2-link=Tibor Gallai|title=Gráfok előírt fokszámú pontokkal|language=Hungarian|journal=Matematikai Lapok|volume=11|year=1960|pages=264&ndash;274|url=http://www.renyi.hu/~p_erdos/1961-05.pdf}}.
*{{citation
| last= Havel
| first= Václav
| authorlink =V. J. Havel
| year = 1955
| title = A remark on the existence of finite graphs
| language = Czech
| journal = Časopis pro pěstování matematiky
| volume = 80
| pages = 477–480
| url = http://eudml.org/doc/19050
}}
*{{citation
 | last = Hakimi | first = S. L. | authorlink = S. L. Hakimi
 | journal = Journal of the [[Society for Industrial and Applied Mathematics]]
 | mr = 0148049
 | pages = 496–506
 | title = On realizability of a set of integers as degrees of the vertices of a linear graph. I
 | volume = 10
 | year = 1962}}.
*{{citation
 | last1 = Sierksma | first1 = Gerard
 | last2 = Hoogeveen | first2 = Han
 | doi = 10.1002/jgt.3190150209
 | issue = 2
 | journal = [[Journal of Graph Theory]]
 | mr = 1106533
 | pages = 223–231
 | title = Seven criteria for integer sequences being graphic
 | volume = 15
 | year = 1991}}.

[[Категорія:Теорія графів]]