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

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

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

.

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

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

.

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

Пустой граф – граф, не содержащий ни одного ребра. Пустой граф с множеством вершин обозначается .

Полный граф – граф, в котором каждые две вершины смежны. Полный граф с множеством вершин обозначается .

Путь имеет множество вершин , ребрами его являются пары , .

Цикл получается из графа добавлением ребра .

Полный двудольный граф . Множество вершин состоит из двух частей, в одной из них p вершин, в другой q. Любые две вершины из одной части не смежны, любые две вершины из разных частей смежны.