Графы, лемма о рукопожатиях

Граф — набор точек (вершиин), некоторые из которых соединены линиями (ребрами).

В задачах часто формулируют условие без графов: например, говорят про компанию знакомых, где люди — вершины графа, а знакомства — его ребра, или про города и дороги, где города — вершины графа, а дороги между ними — ребра.

Связный граф — граф, в котором от каждой вершины можно добраться по ребрам до любой другой его вершины.

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

Как связаны между собой вершины и ребра? Оказывается, если дано число вершин в полном графе, то можно легко посчитать количество ребер в нем.

Рассмотрим полный граф на 4 вершинах и найдем количество ребер в нем. Всего в полном графе 4 вершины, при этом каждая вершина соединена с каждой. Значит, из любой вершины выходит ровно 3 ребра, так как сама с собой вершина не соединена. Таким образом, мы получили ребер. Но это еще не всё.

Рассмотрим одно ребро, например, между первой и третьей вершинами. Это ребро мы посчитали дважды: когда брали первую вершину и считали ее три ребра и когда брали третью вершину и считали ее три ребра. Таким образом, каждое ребро мы посчитали у обеих вершин, которые оно соединяет. Следовательно, полученный результат мы должны поделить на 2. Тогда всего в полном графе на 4 вершинах проведено

Правильность подсчетов легко проверить, нарисовав такой граф:

Наши рассуждения не зависели от количества вершин, поэтому можем написать формулу количества ребер в полном графе на вершинах. В таком графе каждая вершина соединена с другой вершиной, поэтому в графе всего

Степень вершины — количество ребер, выходящих из этой вершины.

Приведем пример. Нарисуем граф и расставим около его вершин их степени.

Рассмотрим сумму степеней вершин этого графа:

Мы получили четное число. Докажем, что в любом графе сумма степеней вершин четна. Для этого поймем, что складывая степени вершин, мы считаем ребра, выходящие из этих вершин. Таким образом, в этой сумме мы считаем оба конца каждого ребра, то есть сумма степеней вершин — это удвоенное количество ребер графа. Следовательно, сумма степеней вершин четна.

Из этого факта следует очень важная лемма.

Лемма о рукопожатиях

В любом графе количество вершин нечетной степени четно.

Доказательство

Мы знаем, что сумма степеней вершин графа четна. Разделим вершины на две группы: вершины четной степени и вершины нечетной степени.

Очевидно, что сумма степеней вершин четной степени четна. Тогда и сумма степеней вершин нечетной степени четна, так как сумма всех степеней вершин четна.

Итак, мы знаем, что сумма степеней вершин нечетной степени четна. Пусть в графе всего вершин нечетной степени. Тогда эта сумма есть ни что иное как сумма нечетных чисел:

Такое возможно только при четном Значит, в любом графе количество вершин нечетной степени четно.

Решим несколько задач на графы.

1.  В стране 96 городов, из которых 24 — «областные». Некоторые пары городов соединены между собой дорогами (но не более чем одной), причём любой путь по дорогам между двумя обычными городами, если он есть, проходит хотя бы через один «областной» город. Какое наибольшее количество дорог могло быть в этой стране?

Ответ. 2004

Решение. Обычные города не соединены дорогами, иначе бы существовал путь, не проходящий через областной город. Значит, максимальное число дорог будет в том случае, когда каждый обычный город соединен с каждым областным и все областные соединены между собой.

Таким образом, ребер вида «областной-областной» будет ровно а ребер вида «обычный-областной» — ровно Тогда всего дорог