84989 (Обучение решению математических задач с помощью графов), страница 2

Кто играет Тяпкина-Ляпкина. В школьном драмкружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Все началось с Ляпкина-Тяпкина.

Ляпкиным-Тяпкиным буду я! – решительно заявил Гена.

Нет, я буду Ляпкиным-Тяпкиным, - возразил Дима, - с раннего детства мечтал воплотить этот образ на сцене.

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

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

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

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

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

Решение. Попробуем построить граф для данной ситуации. Изобразим юных актеров кружками верхнего ряда: А –Алик, Б – Боря, В – Вова, Г – Гена, Д – Дима, а роли, которые они собираются играть, - кружками второго ряда (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

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

П.Т.З. 7. "Наибольшее и наименьшее число элементов".

Город имеет в плане вид прямоугольника, разбитого на клетки: n улиц параллельны друг другу, m других пересекаются под прямым углом. На улицах города – но не на перекрестках – стоят милиционеры. Каждый милиционер сообщает номер проходящего мимо него автомобиля, направление его движения и время, когда он проехал. Какое наименьшее число милиционеров нужно расставить на улицах, чтобы по их показаниям можно было однозначно восстановить путь любого автомобиля, едущего по замкнутому маршруту (маршрут не проходит по одному и тому же участку улицы дважды)?

Решение:

Наименьшее число милиционеров равно (m-1)(n-1).

Если милиционеры расставлены требуемым образом, то вся сетка улиц распадается на какое-то число k кусков, не содержащих замкнутых маршрутов (циклов), - иначе найдется цикл, по которому можно проехать не будучи замененным ни одним милиционером. Если оставшийся кусок сетки содержит р перекрестков то в нем содержится ровно р – 1 отрезков улиц. Так как перекрестков всего m n, то число отрезков, на которых нет милиционеров, равно mn – k. Общее число отрезков улиц равно 2mn – m – n. Таким образом, число занятых отрезков равно

mn – m – n + k (n – 1)(n – 1).

Пример нужной расстановки (n – 1)(n – 1) милиционеров показан на рисунке

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://www.khspu.ru