Граф это математический объект состоящий из двух множеств. Первое — множество вершин, второе — множество ребер. При этом каждое ребро соединяет две вершины (инцидентно двум вершинам). Подробно останавливаться на теории графом здесь не имеет смысла, любой желающий без проблем может найти книги и статьи по теме. Мы же рассмотрим задачу которую можно решить с помощью теории графов, а все необходимые определения введем по ходу решения (если это конечно понадобится).
Условие:
В Тридевятом царстве лишь один вид транспорта — ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний — одна, а из всех остальных городов — по 20. Докажите, что из столицы можно долететь в Дальний (возможно, с пересадками) .
Решение:
Представим себе граф в котором вершинами являются города (столица, Дальний и остальные), а ребрами будут ковролинии их соединяющие.
Будем решать задачу методом от противного. Предположим, что из столицы никак нельзя попасть в город Дальний (в случае когда не существует пути из одной вершины в другую граф называется несвязным). Таким образом наш граф разделен минимум на две части (компоненты связности) в одной из которых находится столица, а во второй город Дальний. Каждая компонента связности так же должна являться графом.
Немного отступим. Степень вершины задается как число ребер выходящих из этой вершины. Легко заметить, что сумма степеней всех вершин графа должна быть четным числом. Так как каждое ребро считается дважды (для одной и для второй вершины).
Вернемся к нашим городам. Найдем сумму степеней всех вершин в той части в которой у нас находится столица. Это число равное 21+n*20, где n – число остальных городов. Очевидно, что это число нечетное, а значит такого графа существовать не может.
Получили противоречие, доказывающее, что из столицы можно попасть в город Дальний (напрямую или с пересадками).
Всем кто дочитал, спасибо за внимание! Удачных вам вычислений!