Читать статья по математике: "Обучение решению математических задач с помощью графов" Страница 4

(Назад) (Cкачать работу)

Ну, хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена.

. . . А мне – Осипа, - не уступил ему в великодушии Дима.

Хочу быть Земляникой или Городничим, - сказал Вова.

Нет, Городничим буду я, - хором закричали Алик и Боря. – Или Хлестаковым, добавили они одновременно.

Удастся ли распределить роли так, чтобы исполнители были довольны?

Решение. Попробуем построить граф для данной ситуации. Изобразим юных актеров кружками верхнего ряда: А –Алик, Б – Боря, В – Вова, Г – Гена, Д – Дима, а роли, которые они собираются играть, - кружками второго ряда (1 – Ляпкин-Тяпкин, 2 – Хлестаков, 3 – Осип, 4 – Земляника, 5 - Городничий). Затем от каждого участника проведем отрезки, т.е. ребра к ролям, которые он хотел бы сыграть. У нас получится граф с десятью вершинами и десятью ребрами.

А Б В Г Д

1 2 3 4 5

Чтобы решить задачу, нужно из десяти выбрать пять ребер, не имеющих общих вершин. Сделать это легко. Достаточно заметить, что в вершины 3 и 4 ведет по одному ребру, из вершин Д и В соответственно. Это означает, что Осипа (вершина 3) должен играть Дима, а Землянику – Вова. Вершина 1 – Ляпкин-Тяпкин соединена ребрами с Г и Д. Ребро 1 – Д отпадает, так как Дима уже занят, остается ребро 1 – Г, Ляпкина-Тяпкина должен играть Гена. Остается соединить вершины А и Б с вершинами 2 и 5, соответствующим ролям Хлестакова и Городничего. Это можно сделать двумя способами: либо выбрать ребра А - 5 и Б – 2, либо ребра А – 2 и Б – 5. В первом случае Алик будет играть Городничего, а Боря – Хлестакова, во втором случае – наоборот.

П.Т.З. 6. "Мосты".

Задача о Кенигсбергских мостах. Город Кенигсберг (ныне Калининград) расположен на берегах и двух островах реки Прегель (Преголи). Различные части города соединены семью мостами, как показано на рисунке. В воскресные дни горожане совершают прогулки по городу. Можно ли выбрать такой маршрут, чтобы пройти один и только один раз по каждому мосту и притом вернуться в начальную точку пути?

С g

с d

D A e

f

a b В

Решение.

Обозначим различные части города буквами А, В, С, D, а мосты – буквами a, b, c, d, e, f, g. В этой задаче существенны лишь переходы через мосты: переходя через любой мост, мы всегда из одной части города попадем в другую, и, наоборот, переходя из одной части города в другую мы непременно пройдем по мосту. Поэтому изобразим план города в виде графа, вершины которого изображают отдельные части города, а ребра – мосты, соединяющие соответствующие части города.

С g c d D

A

a b

B f

Если бы существовал маршрут, удовлетворяющий условию задачи, то существовал бы замкнутый и непрерывный обход этого графа, проходящий один раз по каждому ребру. Иными словами, этот граф можно было бы вычертить, не отрывая карандаша от бумаги и не проходя дважды по одному и тому же ребру. Но это невозможно – какую бы вершину мы ни выбирали за исходную, нам придется проходить через остальные вершины, и при этом каждому «входящему» ребру (мосту, по которому мы вошли в эту часть города) будет соответствовать выходящее ребро (мост, которым мы воспользуемся затем, чтобы покинуть эту часть города): число ребер, входящих в каждую вершину, будет равно числу ребер выходящих из нее, т.е. общее число ребер, сходящихся в каждой вершине должно быть

Похожие работы