Степінь вершини (англ. degree, також валентність, англ. valency) в теорії графів — кількість ребер графу , інцидентних вершині . При підрахунку степені ребро-петля враховується двічі. Степінь вершини позначається як , інколи як . Максимальна і мінімальна степені вершин графу G позначаються відповідно Δ(G) і δ(G). На рисунку 1 максимальна степінь дорівнює 5, мінімальна — 0. В регулярному графі степені всіх вершин однакові, тому в цьому випадку можна говорити про степінь графу.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOWtMMlEyTDFWdVpHbHlaV04wWldSRVpXZHlaV1Z6WHlVeU9FeHZiM0FsTWprdWMzWm5Mekl5TUhCNExWVnVaR2x5WldOMFpXUkVaV2R5WldWelh5VXlPRXh2YjNBbE1qa3VjM1puTG5CdVp3PT0ucG5n.png)
Лема про рукостискання
За формулою суми степенів для графу ,
тобто сума степенів вершин будь-якого графу дорівнює подвоєному числу його ребер. Крім того, формула стверджує, що в будь-якому графі число вершин непарного степеня парне. Це твердження (і сама формула) відомі як лема про рукостискання. Назва походить від відомої математичної задачі: необхідно довести, що в будь-якій групі число людей, що потиснули руку непарній кількості інших людей, буде парним.
Послідовність степенів вершин
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODFMelZrTDBOdmJtcDFaMkYwWlMxa1pYTnphVzV6TG5OMlp5OHlNREJ3ZUMxRGIyNXFkV2RoZEdVdFpHVnpjMmx1Y3k1emRtY3VjRzVuLnBuZw==.png)
Послідовність степенів вершин неорієнтовного графу є незростаюча послідовність степенів вершин графу. Для графу, зображеного на рисунку 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 разу, отримуємо весь граф.
Проблема знаходження або оцінки числа графів по заданій послідовності відноситься до (перерахування графів).
Окремі випадки
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHhMekZtTDBSbGNIUm9MV1pwY25OMExYUnlaV1V1YzNabkx6SXlNSEI0TFVSbGNIUm9MV1pwY25OMExYUnlaV1V1YzNabkxuQnVadz09LnBuZw==.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 стор. 5
- Diestel стор. 278
Див. також
- (Степенева матриця)
Джерела
- Diestel, Reinhard (2005), Graph Theory (вид. 3rd), Berlin, New York: Springer-Verlag, ISBN .
- Erdős, P.; (1960), Gráfok előírt fokszámú pontokkal (PDF), Matematikai Lapok (Hungarian) , 11: 264—274.
- (1955), A remark on the existence of finite graphs, Časopis pro pěstování matematiky (Czech) , 80: 477—480
- (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, , 15 (2): 223—231, doi:10.1002/jgt.3190150209, MR 1106533.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет