Проект "ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ К РЕШЕНИЮ ЛОГИЧЕСКИХ ЗАДАЧ"
проект по информатике и икт (11 класс)

Моисеенко Александр  (11 класс)

Васильев Алексей (11 класс)

МОУ «Средняя общеобразовательная школа №9» г. Канаш

Краткая аннотация  проекта

«ПРИМЕНЕНЕИЕ ТЕОРИИ ГРАФОВ

К РЕШЕНИЕЮ ЛОГИЧЕСКИХ ЗАДАЧ»

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

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

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

В результате работы над проектом была  разработана методичка «Применение теории графов к решению логических и некоторых прикладных задач».

Городская проектная неделя

«Обучение, вдохновение, творчество»

Секция: ПРОГРАММИРОВАНИЕ

ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ

К РЕШЕНИЮ ЛОГИЧЕСКИХ ЗАДАЧ

Моисеенко Александр, Васильев Алексей

МОУ «Средняя общеобразовательная школа №9» г. Канаш, 11 класс

Научный руководитель:  

Кузьмин Вячеслав Алексеевич,

учитель информатики

СОШ № 9 г. Канаш

Канаш

ОГЛАВЛЕНИЕ

Введение                                                                                                 2

Цели и задачи проекта                                                                                 2

Основная часть

• Общие подходы к решению логических задач                                                 3
• Закономерности теории графов                                                                 3
• Применение элементов теории графов к решению задач в заданиях единого государственного экзамена по информатике                                                 5
• Заключение                                                                                 8
• Библиографический список                                                                 8

Приложения                                                                                                 9

ВВЕДЕНИЕ

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

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

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

ЦЕЛЬ И ЗАДАЧИ ИССЛЕДОВАНИЯ

Цель исследования: применить графовый аппарат для решения логических задач.

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

Задачи исследования:

• рассмотреть решение задач при помощи графов;
• научиться переводить задачи на язык графов;
• сравнить традиционные методы решения задач с методами теории графов.

Результаты опроса учащихся 11 класса.

Результат опроса учащихся 11 класса  показал, что только 2 ученика знакомы с понятием «граф» как математическим и 27 как – титул.

ОСНОВНАЯ ЧАСТЬ

Общие подходы к решению логических задач

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

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

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

                        Граф называется ориентированным, если на    

 ребрах задана ориентация, т. е. указан порядок прохождения вершин.

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

На рисунке изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А. На рисунке: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0. Вершина называется нечетной – если степень этой вершины нечетная, четной – если степень этой вершины четная

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

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2

В теории графов выделяются следующие закономерности

Закономерность1.

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

Закономерность 2.

Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

Закономерность 3

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

Закономерность 4

Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 5

 Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине
Закономерность 6

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

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

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

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

Ход решения задачи будем представлять в виде графа, где вершины – острова и берега, а ребра – мосты

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

То есть нам нужно определить степень каждой вершины и узнать какие вершины четные, а какие нечетные. Подпишем степени вершин в кружочках. И посчитаем количество нечетных вершин. Нечетные вершины: А, B, C, D. Но, поскольку граф на этом рисунке имеет четыре нечетные вершины, то, согласно закономерности 7. такой граф начертить «одним росчерком» невозможно. Значит, и пройти по кенигсбергским мостам, соблюдая заданные условия, нельзя.

Следующим типом задач являются задачи нахождения наилучших вариантов развозки товаров по магазинам, материалов по стройкам, т.е. нахождения оптимального маршрута. Например, имеется k городов, расстояния между которыми известны. Коммивояжер отправляется в путь из одного из них с тем, чтобы обойти все остальные (k-1) города по одному разу и вернуться в исходный город. Найти кратчайший маршрут.

Для решения данной задачи строится исходный граф (Рис.1), на котором указывается обозначения городов и расстояние между ними, затем строится дополнительное граф – дерево (Рис.2) со всевозможными маршрутами, число которых можно вычислить, используя соотношение n(n-1)/2, где n – число вершин данного графа. Как видно из граф-дерева, кратчайшим является маршрут длиной 33.

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

Такой метод называется методом ветвей и границ.  (Приложение 1).

Применение элементов теории графов

к решению задач в заданиях единого государственного экзамена по информатике

Задание из демоверсии ЕГЭ  по информатике.

А10.  Между четырьмя крупными аэропортами, обозначенными кодами DLU, IGT, OPK и QLO, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между этими аэропортами:

Путешественник находится в аэропорту DLU в полночь (0:00). Определите самое раннее время, когда он может оказаться в аэропорту QLO.

1)15:40         2)16:35         3)17:15         4)17:25

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

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

На новом графе (рис.4) видно, что до аэропорта QLO можно добраться по трем путям: 1)DLU – OPK – QLO,  2)DLU – IGT – QLO  и 3)DLU – QLO. Рассматривая каждый из путей в отдельности, будем отмечать время вылета и прилета из соответствующих аэропортов.  На графе видно, что по двум путям путешественник, прилетая в промежуточный аэропорт, не успевает на следующий самолет, вылетающий в конечную точку. Последовательно отбрасывая варианты, находим решение задачи.

Ответ: Путешественник может оказаться в аэропорту QLO 17:15

Задание А12 из демоверсии ЕГЭ 2007 г. по информатике

Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними.

Укажите таблицу, для которой выполняется условие: “Минимальная стоимость проезда  из А в B не больше 6”.

Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими  соседними станциями.

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

Как видно из анализа для 4 случая выполняется условие  “Минимальная стоимость проезда  из А в B не больше 6”.

Ответ: 4

ЗАКЛЮЧЕНИЕ

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

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

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

ЛИТЕРАТУРА

1. Касаткин В.Н. Необычные задачи математики. - Киев: Рад. шк. 1987.
2. Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л, Штайн, Клиффорд. Алгоритмы: построение и анализ, 2-е издание. Издательский дом "Вильямс".2005.
3. Самуйлов К.Е., Чукарин А.В. О применении теории графов к решению задачи маршрутизации сигнальных сообщений в цифровых сетях связи.:М,  2005.
4. Оре О. Теория графов. М.: Наука, 1968. 336с. http://eqworld.ipmnet.ru/ru/library/books/Ore1965ru.djvu
5. Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997.