Материал по теме "Графы"

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

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

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

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