Окрестности и степени
Множество вершин, смежных с данной вершиной х в некотором графе, называется окрестностью этой вершины и обозначается через N(x). Число вершин в N(x) называется степенью вершины х и обозначается через deg(x).
Если сложить степени всех вершин графа, то каждое ребро внесет в эту сумму вклад, равный 2. Следовательно, сумма степеней всех вершин равна удвоенному числу ребер графа:
.
Это утверждение называют теоремой о рукопожатиях.
В ориентированном графе для каждой вершины х можно ввести два числа: – число заходящих ребер и – число выходящих. Их называют соответственно полустепенью захода и полустепенью исхода. Аналогом теоремы о рукопожатиях для ориентированного графа является очевидное равенство
.
Некоторые специальные графы
Пустой граф – граф, не содержащий ни одного ребра. Пустой граф с множеством вершин обозначается .
Полный граф – граф, в котором каждые две вершины смежны. Полный граф с множеством вершин обозначается .
Путь имеет множество вершин , ребрами его являются пары , .
Цикл получается из графа добавлением ребра .
Полный двудольный граф . Множество вершин состоит из двух частей, в одной из них p вершин, в другой q. Любые две вершины из одной части не смежны, любые две вершины из разных частей смежны.