Теория графов при решении задач

Министерство образования и науки Республики Бурятия

Отдел образования МО «Еравнинский район»

МБОУ «Сосново-Озерская средняя общеобразовательная школа №2»

Конференция «Шаг в будущее»

Секция «Культурология»

Теория графов при решении различных задач

Автор: ученица 9 «б» класса

Максимова Аюна

Руководитель: учитель  математики,

Дугарнимаева Эржена Баировна

с. Сосново-Озерское

2017 год

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

        Датой рождения теории графов принято считать 1736 год, когда Леонард Эйлер решил задачу о кенигсбергских мостах. Рукава реки Прегель, на берегу которой расположен город Кенигсберг, образовывали два острова. В эту эпоху четыре образовавшихся участка суши (правый и левый берег и два острова) соединяло семь мостов так, как это показано на рисунке. Во время прогулки по городу Эйлер захотел пройти по всем мостам, причем по каждому только один раз. Однако ему это не удалось. Вернувшись домой, ученый составил схему, изобразил участки суши точками, а мосты отрезками то и был первый граф. Термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Широкое развитие теория графов получила с 50-х годах 20 века в связи со становлением кибернетики и развитием вычислительной техники. Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. С дворянским титулом «граф» их связывает общее происхождение от латинского слова «графио» - пишу.

Теория графов.

Рассмотрим задачу.

Задача 1 . Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

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

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

Такая картинка называется графом. Точки при этом называются вершинами, а линии –ребрами графа.

Степени вершин и подсчет числа ребер графа

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

С понятием степени вершины связана одна из основных теорем теории графов –теорема о честности числа нечетных вершин.

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

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

Ответ. Соединить телефоны таким образом невозможно.

Теорема: Любой граф содержит четное число нечетных вершин.

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

Связность графа

Есть еще одно важное понятие, относящееся к графам – понятие связности.

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

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

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

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

Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.”

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

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

Задача 4. В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.

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

Графы Эйлера

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

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

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

Сейчас мы доказали теорему об Эйлеровых графах:

Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.

Применение графов при решении задач.

Графы при решении комбинаторных задач. Комбинаторика - раздел математики, рассматривающий вопросы(задачи), связанные с подсчётом числа всевозможных комбинаций из элементов данного конечного множества при сделанных исходных предположениях. 

Задача:

Имеются шары. Их всего 3 - жѐлтый, красный и синий. Олег должен разложить их на полке всеми возможными способами.

Ответ выглядит так:

Графы при решении логических задач.

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

 Висячей вершиной называется вершина, из которой выходит ровно одно ребро.

Задача: Первенство класса.

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

Решение: Изобразим данные задачи в виде схемы. Участников изобразим точками по первым буквам имени. Если двое участников уже сыграли между собой, то будем соединять изображающие их точки отрезками. Такие схемы и называются графами. Точки А, Б, В, Г, Д, Е – вершины графа, соединяющие их отрезки – ребрами графа. Заметьте, что точки пересечения ребер графа не являются его вершинами. Во избежание путаницы вершины графа часто изображают маленькими кружочками, а не точками. Ребра же зачастую удобнее изображать не прямолинейными отрезками, а дугами.  

                              Б         В                                                  Б              В  

                А                                   Г                           А                         

                                                                                                                             Г

                                                                                            Е                   Д

                             Рис.1                                                          Рис.2

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

Задача. Колхозница принесла на базар корзину яблок. I покупателю она продала половину всех яблок и еще 1 яблоко, II – половину остатка и еще 1 яблоко, III – половину нового остатка и еще 1 яблоко и т.д. Последнему – шестому покупателю она также продала половину оставшихся яблок и еще 1 яблоко, причем оказалось, что она продала все свои яблоки. Сколько яблок принесла для продажи колхозница?

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

Решая, действия делаем обратно.

Ответ: 126 яблок.

Графы при решении задач по теории вероятности.

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

  Каким образом звездочёт должен разместить шары в урнах, чтобы обеспечить себе максимальную возможность уцелеть?

Ответ: Звездочёту надо в одну урну положить один белый шар, а все остальные во вторую. Тогда вероятность выжить составит 2/3.

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

Графы при решении задач ГИА.

Задача: В фирме «Чистая вода» стоимость (в рублях) колодца из железобетонных колец рассчитывается по формуле  , где   — число колец, установленных при рытье колодца. Пользуясь этой формулой, рассчитайте стоимость колодца из 11 колец.

Заключение.

        Чтобы найти ответ на интересующую меня задачу, мне пришлось познакомиться с новым разделом математики «Теории графов», который не изучается в школьном курсе, но облегчает решение многих задач. В любой области науки и техники встречаешься с графами. Графы - это замечательные математические объекты, с помощью которых можно решать математические, экономические и логические задачи, различные головоломки и упрощать условия задач по физике, химии, электронике, автоматике. Многие математические факты удобно формулировать на языке графов. Теория графов — одна из самых красивых и наглядных математических теорий.