Степень вершины

Число ребер, инцидентных некоторой вершине v, называется степенью вершины и обозначается deg v. В полном графе Кп степень каждой вершины равна п – 1. максимальная и минимальная степени вершин графа G обозначаются символами D(G) и d(G) соответственно:

.

Вершина степени 0 называется изолированной, вершина степени 1 – концевой (висячей). Ребро, инцидентное концевой вершине, также называется концевым. Вершина графа, смежная с каждой другой его вершиной, называется доминирующей.

Пример 2. В графе Н3 на рис 2.11 вершина 3 – висячая, вершина 2 – доминирующая, .