Степень вершины
Степень вершины — это число рёбер, которые с ней соединены. По степеням вершин можно быстро определить, есть ли у вершины соседи, является ли она листовой, а также проверять некоторые свойства графа.
Как находить степень
Чтобы найти степень вершины, нужно пересчитать все рёбра, выходящие из неё или входящие в неё. В неориентированном графе направление не учитывается: каждое ребро, соединяющее вершину с другой вершиной, увеличивает её степень на 1. Если несколько рёбер соединяют одну и ту же пару вершин, каждое из них считается отдельно.
Пусть вершина \(A\) соединена рёбрами \(AB\), \(AC\) и \(AD\). Тогда ей инцидентны три ребра, поэтому \(\deg(A)=3\). Вершина \(D\), соединённая только ребром \(AD\), имеет степень \(1\) и является листовой вершиной.
Степень вершины — это число рёбер, а не число других вершин во всём графе. В простом графе эти числа совпадают с количеством соседей, но при наличии кратных рёбер одно и то же соседство может быть учтено несколько раз. Петля, то есть ребро из вершины в неё же, в неориентированном графе увеличивает степень вершины на 2: у петли два конца находятся в одной вершине.
В задачах степень помогает определить вершины с особыми свойствами. Вершина степени \(0\) изолирована и не связана с другими вершинами. Вершина степени \(1\) — листовая. Также сумма степеней всех вершин неориентированного графа равна удвоенному числу его рёбер: каждое ребро имеет два конца.
В графе вершина \(B\) соединена с вершинами \(A\), \(C\) и \(D\). Какова её степень?
Главное
- Степень вершины — число рёбер, инцидентных этой вершине.
- Вершины степени \(0\) и \(1\) называют соответственно изолированной и листовой.
- В неориентированном графе сумма степеней всех вершин равна \(2|E|\).