Использование графов при решении задач

Графы удобно использовать при решении некоторых классов задач.

Задача 1

Сколькими способами можно рассадить в ряд на три стула трех учеников? Выписать все возможные случаи.

Решение этой задачи удобнее всего представить в виде дерева. За его корневую вершину возьмем произвольную точку плоскости О.

На первый стул можно посадить любого из трех учени­ков — обозначим их А, В и С. На схеме это соответствует трем ветвям, исходящим из точки О:

схема

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

схема

Очевидно, что третий стул в каждом случае займет оставшийся ученик. Это соответствует одной ветви дерева, которая «вырастает» на каждой из предыдущих ветвей.

схема

Выпишем все пути от вершин первого уровня к верши­нам третьего уровня:  А-В-С, А-С-В, ВАС, В-С-А, С-А-В, С-В-А. Каждый из выписанных путей определяет один из вариантов рассаживания учеников на стулья. Так как других путей нет, то искомое число способов — 6.

Дерево можно не строить, если не требуется выписывать все возможные варианты, а нужно просто указать их число. В этом случае рассуждать нужно так: на первый стул можно усадить одного из трех человек, на второй — одного из двух оставшихся, на третий — одного оставшегося: 3-21 = 6.

Задача 2

Чтобы принести Царю-батюшке молодильные яблоки, должен Иван-царевич найти единственный верный путь к волшебному саду. Встретил Иван-царевич на развилке трех дорог старого ворона и вот какие советы от него услышал:

1)  иди сейчас по правой тропинке;

2)  на следующей развилке не выбирай правую тропинку;

3)  на третьей развилке не ходи по левой тропинке.

Пролетавший мимо голубь шепнул Ивану-царевичу, что только один совет ворона верный и что обязательно надо пройти по тропинкам разных направлений. Наш герой выполнил задание и попал в волшебный сад. Каким маршрутом он воспользовался?

схема


Обозначим левую, среднюю и правую тропинки соответственно Л, С и П. Возможные маршруты представим в виде графа. При этом подсказки ворона отметим более «жирными» ребрами. Так как только один совет ворона верен, то на графе ему будет соответствовать маршрут, имеющий одно «жирное» ребро. Этот маршрут обозначен дополнительной пунктирной линией.

 


Hosted by uCoz