Окрестности и степени

Множество вершин, смежных с данной вершиной х в некотором графе, называется окрестностью этой вершины и обозначается через N (x). Число вершин в N (x) называется степенью вершины х и обозначается через deg(x).

Если сложить степени всех вершин графа, то каждое ребро внесет в эту сумму вклад, равный 2. Следовательно, сумма степеней всех вершин равна удвоенному числу ребер графа:

.

Это утверждение называют теоремой о рукопожатиях.

В ориентированном графе для каждой вершины х можно ввести два числа: – число заходящих ребер и – число выходящих. Их называют соответственно полустепенью захода и полустепенью исхода. Аналогом теоремы о рукопожатиях для ориентированного графа является очевидное равенство

.

Некоторые специальные графы