Степень вершины графа: основные понятия и примеры расчета

Степень вершины графа — это фундаментальное понятие в теории графов, которое играет ключевую роль в анализе и моделировании различных систем. В неориентированных графах степень вершины определяется как количество ребер, инцидентных этой вершине, при этом петли учитываются дважды. В ориентированных графах степень делится на входящую и исходящую, что позволяет более детально описывать структуру графа. Понимание степени вершины необходимо для решения задач оптимизации, анализа сетей и моделирования сложных систем в различных областях, таких как компьютерные науки, транспорт, социология и биоинформатика.

В этой статье мы подробно рассмотрим, что такое степень вершины, как её рассчитывать в неориентированных и ориентированных графах, а также разберем примеры и практические задачи. Если вы хотите глубже понять, как работают графы, и научиться применять их в реальных задачах, эта статья станет для вас отличным руководством.

Степень вершины в неориентированном графе

Степенью (валентностью) $deg\ \left( V_{i} \right)$ вершины $V_{i}$ графа называется число инцидентных ей ребер. При подсчёте степени вершины ребро-петля учитывается дважды.

Максимальная и минимальная степени вершин графа $G(V,E)$ обозначаются $\Delta(G)$ и $\delta(G)$ соответственно:

$\Delta(G) = \max_{V_{i}\epsilon V}{deg\ \left( V_{i} \right)}; \quad \delta(G) = \min_{V_{i}\epsilon V}{deg\ \left( V_{i} \right)},$

где $i = 1...n$ , $n = |V|$ — число вершин графа.

Вершина графа, имеющая степень, равную нулю, называется изолированной.

Граф, состоящий из изолированных вершин, называется пустым (нуль-графом).

Вершина графа, имеющая степень, равную 1, называется висячей.

Задача 1.4.1. Дан граф $G$ (рис. 1.4.1), определите степени всех его вершин.

Рисунок 1.4.1 – Неориентированный граф - Теория графов ischanow.com — Рисунок 1.4.1 – Неориентированный граф

Решение.

Найдем последовательно степени всех вершин графа, например, $deg\ \left( V_{1} \right) = 4$ , так как данной вершине инцидентны четыре ребра: $e_{1},\ e_{5},\ e_{4},\ e_{3}$ . Вершина $V_{6}$ инцидентна ребрам $e_{10},\ e_{3},\ e_{7},\ e_{8},\ e_{11}$ , ее степень равна 6, так как ребро-петля $e_{10}$ учитывается два раза. Вершина $V_{8}$ называется висячей, так как она инцидентна одному ребру $e_{11}$ , $deg\ \left( V_{8} \right) = 1$ . Вершина $V_{9}$ не инцидентна ни одному ребру, поэтому $deg\ \left( V_{9} \right) = 0$ , такие вершины называются изолированными. Вершины графа G и соответствующие им степени оформлены в виде таблицы.

Таблица 1.4.1 - Степени вершин графа - Теория графов ischanow.com — Таблица 1.4.1 — Степени вершин графа

Максимальная степень вершин графа G: $\mathrm{\Delta}(G) = 6$ , данную степень имеет вершина $V_{6}$ ; минимальная степень вершин графа G: $\delta(G) = 0$ , данную степень имеет вершина $V_{9}$ .

Вершина называется чётной (нечётной), если её степень — чётное (нечётное) число. Вершина $V_{3}$ является нечетной (рис. 1), так как $deg\ \left( V_{3} \right) = 3$ , вершина $V_{7}$ — четная, так как $deg\ \left( V_{7} \right) = 2$ .

Задача 1.4.2. Определите степени всех вершин графа

Рисунок 1.3.2 – Неориентированный граф - Теория графов ischanow.com — Рисунок 1.3.2 – Неориентированный граф

Задача 1.4.3. Определите степени всех вершин графа

Рисунок 1.3.4 – Неориентированный граф- Теория графов ischanow.com — Рисунок 1.3.4 – Неориентированный граф

Задача 1.4.4. Определите степени всех вершин графа

Рисунок 1.3.6 – Неориентированный граф - Теория графов ischanow.com — Рисунок 1.3.6 – Неориентированный граф

Граф $G = (V,E)$ называется регулярным или однородным, если степени всех его вершин одинаковы. Так как в регулярном графе степени всех вершин одинаковы, то в данном случае можно говорить о степени графа.

Рисунок 1.4.2 – Регулярный граф - Теория графов ischanow.com — Рисунок 1.4.2 – Регулярный граф

Утверждение («лемма о рукопожатиях») Сумма степеней всех вершин графа $G = (V,E)$ равна удвоенному числу ребер:

$\sum_{i = 1}^{n}{deg\ \left( V_{i} \right) = 2m},$

где $n = |V|$ — число вершин графа; $m = |E|$ — число ребер графа.

Степень вершины в ориентированном графе

Степень вершины в ориентированном графе определяется количеством рёбер, инцидентных этой вершине. В отличие от неориентированных графов, в ориентированных графах рёбра имеют направление, поэтому степень вершины может быть разделена на два компонента.

Входящая степень (in-degree) $\deg^{+}\left( V_{i} \right)$ . Это количество рёбер, входящих в вершину. То есть это количество рёбер, направленных к данной вершине.

Исходящая степень (out-degree) $\deg^{-}\left( V_{i} \right)$ . Это количество рёбер, исходящих из вершины. То есть это количество рёбер, направленных от данной вершины.

Таким образом, общая степень вершины в ориентированном графе равна сумме её входящей и исходящей степеней:

$deg\ \left( V_{i} \right) = \deg^{+}\left( V_{i} \right) + \deg^{-}\left( V_{i} \right).$

Например, если у вершины есть 2 входящих и 3 исходящих ребра, то её общая степень будет равна 5.

Степень вершины является важным понятием в анализе ориентированных графов, так как она может отражать важные характеристики структуры графа, такие как центральность, связность и т. д.

Задача 1.4.5. Дан ориентированный граф (рис. 1.4.3), определите степени всех его вершин.

Рисунок 1.4.3 – Ориентированный граф - Теория графов ischanow.com — Рисунок 1.4.3 – Ориентированный граф

Решение.

Найдем последовательно степени всех вершин графа. Вершина $V_{1}$ имеет входящую степень равную единице: $\deg^{+}\left( V_{1} \right) = 1$ , так как к этой вершине направлено одно ребро $e_{3}$ ; исходящая степень вершины равна трем: $\deg^{-}\left( V_{1} \right) = 3$ , так как из нее выходят три ребра $e_{1},\ e_{5},\ e_{4}$ . Общая степень вершины равна четырем, так как данной вершине инцидентны четыре ребра: $e_{1},\ e_{5},\ e_{4},\ e_{3}$ . Также можно посчитать по формуле:

$deg\ \left( V_{1} \right) = \deg^{+}\left( V_{1} \right) + \deg^{-}\left( V_{1} \right) = 1 + 3 = 4.$

Вершина $V_{6}$ : входящая степень $\deg^{+}\left( V_{6} \right) = 2$ , так как в данную вершину входят два ребра $e_{10},\ e_{7}$ ; исходящая степень вершины равна четырем $\deg^{-}\left( V_{6} \right) = 4$ , так как из нее выходят четыре ребра $e_{10},\ e_{3},\ e_{8},\ e_{11}$ . Общая степень вершины равна шести:

$deg\ \left( V_{6} \right) = \deg^{+}\left( V_{6} \right) + \deg^{-}\left( V_{6} \right) = 2 + 4 = 6.$

Вершина $V_{8}$ : входящая степень $\deg^{+}\left( V_{8} \right) = 1$ , так как в данную вершину входит одно ребро $e_{11}$ ; исходящая степень вершины равна нулю $\deg^{-}\left( V_{8} \right) = 0$ , так как из нее не выходит ни одно ребро. Общая степень вершины равна единице:

$deg\ \left( V_{8} \right) = \deg^{+}\left( V_{8} \right) + \deg^{-}\left( V_{8} \right) = 1 + 0 = 1.$

Вершина $V_{9}$ не инцидента ни одному ребру, поэтому $\deg^{+}\left( V_{9} \right) = 0$ и $\deg^{-}\left( V_{9} \right) = 0$ , соответственно $deg\ \left( V_{9} \right) = 0$ .