Графы и их применение при решении задач.

Графы и их применение при решении задач.

Естественно – математическое направление

(Политехническая секция в классах с казахским и русским языках обучения)

Выполнила: Мурзабекова Мадина

     Класс 7 «А»

Руководитель: Дубогрей Светлана Ивановна

                                              с. Заречное, апрель 2010г.

Содержание

1. Введение

2. История возникновения графов

3. Примеры применения теории графов

4. Основные понятия теории графов

а) понятие графа

б) подсчет числа ребер

в) Эйлеровы графы

г) связные графы

д) деревья

е) плоские графы

ж) ориентированные графы

5. Примеры решения задач с помощью графов

6. Практическое применение графов

7. Заключение

Введение

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

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

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

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

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

1. История возникновения графов

        Леонард Эйлер – российский, немецкий и швейцарский математик, внесший огромный вклад в развитие математики. С его именем связана история появления графов. Часто упоминается его задача о Кенигсбергских мостах.

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

3. Примеры применения теории графов наглядно видны на рисунках, представленных в прилагаемой призентации.

4. Основные понятия теории графов

а) понятие графа

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

        Понятие графа проще всего выяснить на примере.

Задача

        В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проходит по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галина с Еленой; Борис, как уже говорилось, с Андреем и еще с Галиной; Виктор – с Галиной, Дмитрий с Виктором и Елена – с Андреем и Виктором. Сколько игр проведено к настоящему моменту и сколько еще осталось?

                                 б

                                                              д

                               б

        д

Задача

Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу).
Сколько всего рукопожатий было сделано?

б) подсчет числа ребер

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

        В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

        Решение. 

        Пусть это возможно. Рассмотрим граф, вершины которого соответствуют телефонам, а ребра – соединяющим их проводам. В этом графе 15 вершин, степень каждой из которых равна 5.Для подсчета количества ребер в этом графе сложим степени всех его вершин. При таком подсчете каждое ребро учтено дважды. Поэтому число ребер графа должно быть равно 15 · 5 / 2. Но это число нецелое. Значит, такого графа не существует и соединить телефоны невозможно.

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

Задача.

        В государстве 50 городов, и из каждого выходит 8 дорог. Сколько всего дорог в государстве?

        Решение.

        50 · 8 / 2 = 200 дорог. При решении задач очень полезна следующая теорема.

        Теорема. Число нечетных вершин любого графа четно.

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

в) Эйлеровы графы

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

Задача.

        Можно ли нарисовать граф, изображенный на рисунках (а) и (б), не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?

          (а)

        Решение.

        а) Можно б) Нельзя.

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

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

Задача.

        Схема мостов города изображена на рисунке. Можно ли совершить прогулку, пройдя по каждому мосту один раз?

        Решение. Нельзя, у соответствующего графа есть 4 нечетные вершины.

Задача.

Хулиган Вася решил прогуляться по парку и его окрестностям так, чтобы при этом перелезть через каждый забор ровно один раз. Сможет ли он это сделать?

г) связные графы

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

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

Задача.

        В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.

        Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам.

        Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.

        Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:

д) деревья

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

е) плоские графы

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

Задача.

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

        Проведенные в графе на рисунке ребра А1, А2, A3 и В1,В2, ВЗ (соответствующие тропинкам от домов А и В ко всем колодцам). Построенный граф разбил плоскость на три области: X, У, Z. Вершина Б, в зависимости от ее расположения на плоскости, попадает в одну из этих трех областей. Если  рассмотреть каждый из трех случаев «попадания» вершины Б в одну из областей X, Y или Z, то всякий раз одна из вершин графа 1, 2 или 3 (один из колодцев) будет «недоступной» для вершины Б (т. е. нельзя будет провести одно из ребер Б1, Б2 или Б3. которое не пересекло бы уже имеющихся в графе ребер).
Таким образом, ответ на вопрос задачи будет таким: «Нельзя!»

Формула Эйлера.

        Правильный нарисованный плоский граф разбивает плоскость на куски. Если обозначить число кусков через F, число вершин через V, число ребер через E, то получаем V = 4, Е = 6, F = 4.

        Для правильно нарисованного связного плоского графа имеет место равенство

        V – E + F = 2

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

ж) ориентированные графы

        Граф, на ребрах которого расставлены стрелки называется ориентированным.

Задача.

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

Решение.

        Количество «втекающих» рек должно быть ровно общему количеству «вытекающих» рек.

        Изучив данную тему, полученные знания я применила для построения генеалогического дерева моей семьи. Я сделала вывод, что родословная моей семьи – это типичный граф.

5. Примеры решения задач с помощью графов

1. Из города А в город В ведут три дороги, а из города В в город С - четыре дороги. Сколькими способами можно проехать из А в С через В?

Возьмем одну дорогу, ведущую из А в В. Ее можно продолжить до С четырьмя различными способами. То же самое можно сделать с каждой из двух других дорог, ведущих из А в В. Всего из А в С через В можно проехать 3 · 4 = 12 способами.

2. Сегодня учитель объявил отметки за контрольную работу. Члены математического кружка Витя, Коля, Петя, Наташа, Ира, Марина и др. решили наглядно показать, какую отметку кто получил. Как это сделать?

В данной задаче есть два множества. Нам следует установить зависимость между элементами этих множеств.

{В, К, П, Н, И, М} – множество учеников,

{1, 2, 3, 4, 5} – множество отметок.

Такой чертеж называют графом:

Решение задачи можно показать и в виде таблицы.

3. Беседуют трое друзей: Белокуров, Чернов и Рыжов. Брюнет сказал Белокурову: «Любопытно, что один из нас блондин, другой брюнет, а третий рыжий, но ни у одного цвет волос не соответствует фамилии». Какой цвет волос имеет каждый из друзей?

Задачу можно решать с помощью рассуждений: а) так как Белокуров разговаривает с брюнетом, значит, Белокуров не брюнет. б) кроме того, Белокуров не блондин, так как цвет его волос не совпадает с фамилией, остается Белокуров - рыжий. в) Чернов и Рыжов не рыжие. г) так как Чернов не рыжий и не брюнет, значит, он блондин. д) Рыжов – брюнет.

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

                                      а)                                                                                     б)

Каждому из друзей должен соответствовать только один цвет волос. Во втором множестве рисунка, а – есть один элемент (брюнет), из которого идут две пунктирные линии, значит, из этой точки должна идти одна сплошная линия и провести ее можно только к Рыжову. От Белокурова идут две пунктирные линии, значит, от него надо провести сплошную линию, и провести ее можно только к «рыжему». Остается Чернов – блондин.

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

Решение. 1-й способ: так как у Наташи туфли зеленые, а  Вали не белые, а значит, и не зеленые, то у Вали туфли синие, поэтому у Ани туфли белые, но у нее и платье того же цвета, т.е. белое. У Наташи туфли зеленые, а платье другого цвета и не белое, значит, у наташи платье синее, поэтому у Вали платье зеленое. 2-й способ: пользуясь графами, получим рис.:

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

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

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

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

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

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

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

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

Решение. Построим граф:

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

Нужно из десяти выбрать пять ребер, не имеющих общих вершин.

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

6. Один из ребят сказал: «А у нас в классе 25 человек, и каждый дружит ровно с семью одноклассниками!»

«Не может быть этого», - ответил приятелю Витя Иванов, победитель олимпиады. Почему он так ответил?

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

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

Решение. Рассмотрим город А. Он соединен дорогами с не менее чем семью городами В1, В2, …, В7, … Всего получилось не меньше 8 городов. Предположим, что есть город С, не связанный ни с А ни с В1, В2, …, В7, … Значит он связан только с теми городами, которые остались вне этого списка. Но таких городов меньше 7, что противоречит условию.

8. В классе 28 человек. Каждая девочка дружит с 4 мальчиками, а каждый мальчик – с 3 девочками. Сколько в классе мальчиков и девочек?

Решение. В графе, для этой задачи вершины, соответствующие мальчикам, выкрасим синим цветом, а вершины, соответствующие девочкам – красным. Каждое ребро графа соединяет ровно две вершины: одну синюю и одну красную. Пусть  всего x красных и y синих вершин (x+y=28 – уравнение №1). Выразим количество ребер в графе. С одной стороны, оно равно 3x, с другой – 4y. Получим уравнение №2: 3x=4y. Решая систему из двух уравнений, легко найти, что x=16 а y=12.

Задача 4. Докажите, что среди учеников любого класса найдутся двое, имеющие одинаковое число знакомых в этом классе (если, конечно, в этом классе не менее двух учеников).

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

9. Расположите на плоскости 6 точек и соедините их непересекающимися линиями так, чтобы из каждой точки выходили четыре линии.

Решение. Смотри рисунок .

10. В марсианском метро 100 станций. От любой станции до любой другой можно проехать. Забастовочный комитет хочет закрыть проезд через одну из станций так, чтобы между всеми остальными станциями был возможен проезд. Докажите, что такая станция найдётся.

Решение. План марсианского метро является связным графом. Возможны два  варианта:

1 случай. Граф является деревом. Тогда этот граф имеет «висячую» вершину. Ее и следует перекрыть.

2 случай. Граф имеет циклы. Тогда нужно перекрыть одну из станций, принадлежащих этому циклу.

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

Решение.

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

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

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

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

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

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

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

3) число команд, участвующих

в 1/8 финала, в 1/4 финала,  в 1/2 финала (число вершин соответственно в четвертом сверху ярусе, в третьем сверху ярусе, во втором сверху ярусе);

4) число матчей, которые придется сыграть командам для выявления обладателя кубка (число незакрашенных вершин в графе).

13. Между планетами введено космическое сообщение по следующим маршрутам: З-К, П-В, З-П, П-К, К-В, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?

Решение:

Составим схему-граф маршрутов:

Мы видим, что от З до М добраться нельзя.

14. В пяти корзинах лежали яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; в корзинах А, Б, В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д – третьего. Пронумеруйте каждую корзину так, чтобы в корзине № 1 были яблоки первого сорта (хотя бы одно); в корзине № 2  - второго и т.д.

Решение:

Составим граф

Ответ: №1 – Г; №2 – А или №2 – Б; №3 – Д; №4 – В; №5 – Б или №5 – А.

6. Практическое применение графов

Родословная.

6. Заключение

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

Использованная литература.

1. Горбачев Н.В., Сборник олимпиадных задач по математике, Москва, 2004.
2. Гусев В.А., Орлов А.И. Внеклассная работа по математике в 6-8 классах.
3. Журнал «Математика в школе» №2, 1994.
4. Игнатьев Е.И., Математическая смекалка, Москва, 2002.
5. Интернет ресурсы.
6. Перельман Я.И., Веселые задачи, Москва, 2003.

Диофантовы  уравнения

Естественно – математическое направление

(Политехническая секция в классах с казахским и русским языках обучения)

Выполнила Мурзабекова Мадина

Класс 8 «Б»

Руководитель Дубогрей Светлана Ивановна

с. Заречное, апрель 2011 г.