Теория графов и ее применение в науке

Картинка

Задачи

Существует огромное множество различного рода задач в теории графов. Здесь мы рассмотрим лишь некоторые: от самых простых до более сложных.

Задача 1: задача коммивояжера

Задача коммивояжера - одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.
Это оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных 43 589 145 600вариантов.
Картинка

Задача 2: Росчерком пера

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

Задача 3

Необходимо составить фрагмент расписания для одного дня занятий с учетом следующих обстоятельств:

• учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок:

• учитель литературы может дать один, либо второй, либо третий урок;

• математик готов дать либо только первый, либо только второй урок;

• Преподаватель физкультуры может дать только последний урок.

Сколько можно составить вариантов расписания так, чтобы оно устроило всех учителей? (Обозначения: М – математика, Ф – физкультура, И – история, Л – литература)

Картинка

Решение:

Согласно условию задачи, первый урок может провести И и М, второй – И, Л и М, третий – И или Л, и четвертый урок – только Ф. Построим усеченный граф-дерево. Ветви, которые отсекаются на этапе построения, указаны красным цветом.

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

Ответ: три варианта.