ГРАФЫ

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

Определение. Под графом мы будем понимать картинку, адекватно описывающую задачу. При этом элементы множеств, как правило, показываются точками. Желательно, чтобы при решении точки не лежали на одной или паре прямых. Точки при этом называются вершинами графа, а линии, соединяющие эти точки, — ребрами. Отметим, что точки могут соединяться произвольными (не обязательно прямыми) линиями.

Поясним понятие графа на примере нескольких задач.

Пример 1. Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля — Меркурий, Плутон — Венера, Земля — Плутон, Плутон - Меркурий, Меркурий - Венера, Уран - Нептун, Нептун - Сатурн, Сатурн — Юпитер, Юпитер — Марс и Марс — Уран. Можно ли добраться (возможны пересадки) с Земли до Марса?

Решение. Нарисуем схему: планетам будут соответствовать точки, а соединяющим их маршрутам - непересекающиеся между собой линии.

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

Пример 2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией тогда и только тогда, когда двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли из города 1 добраться в город 9?

Решение. Покажем возможные маршруты, нарисовав графИ в этой задаче 1 и 9 попали в две разных части графа. Ясно, что в правой части графа сгруппировались города-цифры нацело делящиеся на 3, а в левой части графа ребра соединяют две цифры: одну — делящуюся на 3 с остатком 1, а другую — делящуюся на 3 с остатком 2.

Примечание. Отметим, что один и тот же граф можно нарисовать по-разному. Если учащиеся одного класса нарисуют графы к одной задаче, то мы можем получить столько графов, сколько учащихся их рисовали. Нарисованные по-разному графы (если они нарисованы без ошибок) принято называть изоморфными. Любой читатель может нарисовать бесконечное множество изоморфных графов.