Методическая разработка на тему Графы. Методы решения задач

ГРАФЫ И ИХ ПРИМЕНЕНИЕ ПРИ РЕШЕНИИ ЗАДАЧ
Методическая разработка
Учитель Синявина Надежда Васильевна
Задачи, приводящие к графам
1. Женя, Дима, Максим и Алеша сыграли между собой по одной партии в шахматы. Сколько всего партий было сыграно?
Решение:
Женя сыграл партию с Димой, партию с Максимом и партию с Алешей - всего три партии. Дима также сыграл три партии - с Женей, Максимом и Алешей. Но партию Димы с Женей мы уже посчитали. Остается добавить одну партию, которую сыграли Максим с Алешей. Поэтому искомое число партий равно значению выражения 3+2+1.
Проще решить эту задачу с помощью рисунка.




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

2. Вася, Коля, Петя, Аня и Наташа - лучшие лыжники в пятом классе. Для участия в соревнованиях нужно выбрать из них одного мальчика и одну девочку. Сколькими способами это можно сделать?
Решение:
Эту задачу можно решить с помощью следующей схемы.
Ответ: 6 способов.
3. Пятеро ученых, участвовавших в научной конференции, обменялись рукопожатиями. Сколько всего было сделано рукопожатий?
На прощание эти ученые обменялись визитными карточками. Сколько карточек было передано из рук в руки?
Решение:
Ответ: 10 рукопожатий, 20 визитных карточек.
4. Как вы помните, охотник за мертвыми душами Павел Иванович Чичиков побывал у известных вам помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжогло, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаимное расположение имений и проселочных дорог, соединяющих их (рис. 1.1). Установите, какое имение кому принадлежит, если ни по одной из дорог Чичиков не проезжал более одного раза.
Решение. По схеме видно, что путешествие Чичиков начал с имения Е, а кончил имением О. Замечаем, что в имения В и С ведут только по две дороги, поэтому по этим дорогам Чичиков должен был проехать. Отметим их жирной линией. Определены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и AM Чичиков не ездил. Перечеркнем их (рис. 1.2К Отметим жирной линией ED; перечеркнем DK. Перечеркнем МО И МН отметим жирной линией МF; перечеркнем FO; отметим жирной линией FH, НК и КО. Найдем единственно возможный при данном условии маршрут.
Подведем первый итог: задача решена в ходе преобразования картинки. С рисунка остается только считать ответ: имение Е принадлежит Манилову, D Коробочке, С Ноздреву, А Собакевичу, В Плюшкину, М Тентетникову, F Бетрищеву, Н Петуху, К Констанжогло, О Кошкареву.




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





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


Дополнением графа Г называется граф Г с теми же вершинами, что и граф Г, и с теми и только теми ребрами, которые необходимо добавить к графу Г, чтобы получился полный граф.
Степенью вершины называется число ребер графа, которым принадлежит эта вершина.
Вершина называется нечетной, если ее степень число нечетное. Вершина называется четной, если ее степень число четное.
Путем от А1 до Аn в графе называется такая последовательность ребер ведущая от А1 до Аn , в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза.
Циклом называется путь, в котором совпадают его начальная и конечная вершины.
Длиной пути называется число ребер этого пути.
Длиной цикла называется число ребер в этом цикле.
Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.
Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их.




В графе вершины А и В связные, а вершины А и Н несвязные.
Граф называется связным, если каждые две вершины его связные.
Граф называется несвязным, если хотя бы две вершины его несвязные.
Деревом называется всякий связный граф, не имеющий циклов.


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




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




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






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

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







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

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

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

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


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




Литература.
Т. Варга Математика 2. Плоскость и пространство. Деревья и графы. Комбинаторика и вероятность: (Математические игры и опыты). Пер. с нем. – М.: Педагогика, 1978.– 112 с. с ил.
Л. Ю. Березина Графы и их применение: Пособие для учителей. – М.: Просвещение, 1979. – 143 с. с ил.
А. Г. Ванцян Математика: Учеб для 5 кл. - Самара, «Федоров», 1999.
15