Решение задач с помощью графов

Задача 1. Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только с двумя другими. Возможна ли такая компания?

Решение. Каждого из этой компании изобразим на рисунке кружком. Если двое знакомы, соединим соответствующие кружки отрезком. Оказывается, что такие ситуации не только возможны, но все их можно описать аналогичными схемами. Из рассматриваемой компании нельзя выделить ни «четырехугольник», ни «треугольник», поскольку тогда из оставшихся нельзя будет составить компанию, удовлетворяющую условию, т. е. схема знакомства единственная.

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

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

Каждая вершина графа с девятью вершинами может иметь степень, равную 0, 1, 2,…,7, 8. Предположим, что существует граф Г, все вершины которого имеют разную степень, т. е. каждое из чисел последовательности 0, 1, 2 7, 8 является степенью одной и только одной из его вершин. Но этого не может быть. Действительно, если в графе есть вершина А степени 0, то в нем не найдется вершина В со степенью 8, так как эта вершина В должна быть соединена ребрами со всеми остальными вершинами графа, в том числе и с А. Иначе говоря, в графе с девятью вершинами не могут быть одновременно вершины степени 0 и 8. Следовательно, найдутся хотя бы две вершины, степени которых равны между собой.

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

Задача 3. Может ли так случиться, что в одной компании из шести человек каждый знаком с двумя и только с двумя другими?

Решение.

Участника этой компании изобразим вершиной графа, а отношение знакомства между двумя участниками - ребром. Изобразим графы, которые могут соответствовать такой компании.

Итак, ситуация, рассмотренная в задаче, вполне возможна. Но случай, рассмотренный на втором рисунке, соответствует не одной, а двум компаниям, участники одной из них не знакомы с участниками другой.

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

Во втором случае получились два простых цикла, не сцепленные между собой в вершинах.

Задача 4. Кубок по настольному теннису разыгрывается по олимпийской системе. Встречи проводятся без ничьих. К очередному туру допускается только победившая в предыдущем туре команда. Проигравшие выбывают из игры. Для завоевания кубка команда должна победить во всех турах.

На участие в розыгрыше кубка поданы заявки от 16 команд. Схема проведения игр изображается графом на рисунке.

Вершины нижнего «яруса» дерева (закрашенные) интерпретируем как команды, участвующие в розыгрыше кубка, вершины второго снизу яруса — как команды-победительницы в одной шестнадцатой финала, вершины третьего яруса — как команды победительницы в одной восьмой финала и т.д.

Какую информацию можно получить с помощью этого дерева?

Непосредственно с него считываются:

1) число всех участников розыгрыша кубка (число закрашенных вершин);

2) число этапов проведения розыгрыша (число ярусов из вершин в дереве не считая нижнего);

3) число команд, участвовавших в одной восьмой финала, в одной четвертой финала, в одной второй финала (число вершин соответственно в четвертом сверху ярусе, в третьем сверху ярусе, во втором сверху ярусе);

4) число матчей, которые придется сыграть командам для выявления обладателя кубка (число незакрашенных вершин в графе). Кстати, это число легко определяется и без дерева. (В каждом матче выбывает одна команда. Для того чтобы была выявлена команда-победительница остальные должны выбыть из соревнования. Поэтому число матчей равно числу команд без одной, а именно 15.)

Задача 5. Вершины графа обозначают населенные пункты, ребра – дороги. Сколькими способами можно выбрать путь из А в С? Сколькими способами можно доехать из А в С, затем вернуться обратно, если нельзя проезжать дважды по одной и той же дороге?

Решение:

5 · 3=15 способами можно выбрать путь из А в С.

5 · 3 · 2 ·4 =120 способами можно доехать из А в С, затем вернуться обратно, если нельзя проезжать дважды по одной и той же дороге.

Задача 6. На гору ведут 5 дорог. Сколькими способами можно выбрать маршрут для того, чтобы подняться на гору, а затем спуститься с неё? Как изменится ответ, если нельзя подниматься и спускаться по одной и той же дороге?

Решение:

5 · 5=25 способами можно выбрать маршрут для того, чтобы подняться на гору, а затем спуститься с неё.

5 · 4 =20 способами можно выбрать маршрут для того, чтобы подняться на гору, а затем спуститься с неё, если нельзя подниматься и спускаться по одной и той же дороге.

Заключение.

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

Были решены 10 задач с использованием теории графов. Мы решили гораздо больше задач, но в работу постарались включить самые разные и наиболее интересные.

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

Литература.

1. Т. Варга Математика 2. Плоскость и пространство. Деревья и графы. Комбинаторика и вероятность: (Математические игры и опыты). Пер. с нем. – М.: Педагогика, 1978.– 112 с. с ил.

2. Л. Ю. Березина Графы и их применение: Пособие для учителей. – М.: Просвещение, 1979. – 143 с. с ил.

3. А. Г. Ванцян Математика: Учеб для 5 кл. - Самара, «Федоров», 1999.