Применение графов при решении логических задач

Секция математики

Проект на тему: « Применение графов в логических задачах»

                                   Выполнила: Ненашева Екатерина Сергеевна

ученица 7 «Б» класса ГБОУ СОШ №8

им. С.П.Алексеева

Руководитель: Гриднева Анна Владимировна,

учитель математики ГБОУ СОШ №8

им.С.П.Алексеева

г.о. Отрадный

2017 г.

Содержание проекта:

1. Введение (цель, задачи, актуальность)
2. Основная часть: графы, примеры задач
3. Вывод
4. Список используемой литературы, сайты

Введение

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

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

Цель.

Научиться решать логические задачи с помощью графов

Задачи:

1. Узнать что такое графы.
2. Узнать, для каких задач применяется метод графов.
3. Научиться решать разные логические задачи с помощью графов.

                Что такое графы?

Какие разные, не похожие друг на друга произведения искусства! Но что их объединяет. Все они созданы разными инструментами, но по одному принципу – без единого разрыва.

А можно ли, не портя бумагу, выяснить: решаема задача или нет? На самом деле, существуют правила решения таких задач. Они были сформулированы ещё в 18 веке, но сначала я расскажу вам одну историю.

В XIII веке возник город Кенигсберг (ныне Калининград). Он состоял из 4 частей, на которые делила его река Прегель. Для связи и торговли было построено 7 мостов. И с тех пор жители города бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз? Эту задачу решали и теоретически - на бумаге, и на практике, на прогулках - проходя по этим самым мостам. Над её решением бились великие умы того времени. Но никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по мостам никто не мог

В 1736 году над этой проблемой задумался известный математик Леонард Эйлер. Он взялся решить задачу о семи мостах. Учёный изобразил часть города в виде схемы, которую, спустя ровно 200 лет назвали красивым словом ГРАФ!

Теория графов получила развитие с 50-х гг. 20 в. в связи со становлением кибернетики и развитием вычислительной техники. И в современном мире графы имеют огромное значение и достаточно широко применяются:

• медицине (определение донорской крови);
• химии, биологии (химические реакции, отображение структуры молекул, их цепочек);
• в математике (логические задачи), истории (генеалогические деревья)
• физике, электротехнике, электронике (эл. цепи, конструирование печатных схем);
• экономике, управлении (выбор оптимального пути для потоков грузового транспорта, поток денег, схема метро);
• информатике (блок-схемы программ для ЭВМ, маршрутизация данных в интернете);
• в промышленности (вентиляцией на горных предприятиях);
• схемы авиалиний, которые часто вывешивается в аэропортах;
• схемы метро, дорог, газопроводов, тепло и электросетей;
• графики доставки почты.

И именно Эйлер явился основателем теории графов. И именно с помощью графа учёный сформулировал правила решения задач на росчерк!

  Рассмотрим две задачи

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

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

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

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.

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

Решение: Занумеруем последовательно клетки доски:

А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:

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

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

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

       С помощью  графов можно решать задачи:

1. Логические
2. Комбинаторные
3. Алгебраические: на движение, на совместную работу.

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

                         Задачи с  помощью графов

Задача 3.  Путешествие в Италию.  Мы планируем  вместе с родителями поездку в Италию. Туристическая фирма предлагает нам познакомиться с тремя городами: Венецией, Римом и Флоренцией. Сколько существует вариантов такого маршрута?

   Решение:  Построим дерево возможных вариантов. Путешествие можно начинать в любом из трех городов. Если первой посетить Венецию, то затем можно поехать в Рим или во Флоренцию. Если вторым посетить Флоренцию, то третьим городом будет Рим. Это первые два варианта, а всего их шесть.

                                                                                 *

1 город                                                В                  Р                Ф

2 город                                            Р    Ф            В    Ф          В    Р

 3 город                                           Ф    Р            Ф     В         Р     В

   Ответ: 6 маршрутов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вывод:

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

Список используемой литературы:

1. Пестунова Т.М. Введение в комбинаторику: Учебное пособие/ -Красноярск – КГТУ  2001 г.
2. Ежов И.И. Элементы комбинаторики . М: Наука – 2000 г
3.  Г. И. Просветов . Теория вероятностей и статистика для школьников. М: Альфа-пресс 2009г

Интернет- ресурсы

1. http://shkolapifagora.my1.ru/
2. http://www.zaba.ru Математические олимпиады и олимпиадные задачи