Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года [см. стр. 41-42]:
"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство… После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке [рис.1], на котором A обозначает остров, а B,CиD – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ".
(РИСУНОК 1.1)
По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал [см. стр. 102-104]:
"Это решение по своему характеру, по-видимому, имеет мало отношения к математике, и мне непонятно, почему следует скорее от математика ожидать этого решения, нежели от какого-нибудь другого человека, ибо это решение подкрепляется одним только рассуждением, и нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике. Итак, я не знаю, каким образом получается, что вопросы, имеющие совсем мало отношения к математике, скорее разрешается математиками, чем другими".
Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера к Маринони:
0"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A, B, C, D. Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".
Обоснование вышеприведенного правила можно найти в письме Л. Эйлера к своему другу Элеру от 3 апреля того же года. Мы перескажем ниже отрывок из этого письма.
Математик писал, что переход возможен, если на участке разветвления реки имеется не более двух областей, в которые ведет нечетное число мостов. Для того, чтобы проще представить себе это, будем стирать на рисунке уже пройденные мосты. Легко проверить, что если мы начнем двигаться в соответствии с правилами Эйлера, пересечем один мост и сотрем его, то на рисунке будет изображен участок, где опять имеется не более двух областей, в которые ведет нечетное число мостов, а при наличии областей с нечетным числом мостов мы будем располагаться в одной из них. Продолжая двигаться так далее, пройдем через все мосты по одному разу.
История с мостами города Кенигсберга имеет современное продолжение. Откроем, например, школьный учебник по математике под редакцией Н.Я. Виленкина для шестого класса. В нем на странице 98 в рубрике развития внимательности и сообразительности мы найдем задачу, имеющую непосредственное отношение к той, которую когда-то решал Эйлер.
Задача № 569 . На озере находится семь островов, которые соединены между собой так, как показано на рисунке 1.2. На какой остров должен доставить путешественников катер, чтобы они могли пройти по каждому мосту и только один раз? Почему нельзя доставить путешественников на остров A ?
Решение. Поскольку эта задача подобна задаче о Кенигсбергских мостах, то при ее решении мы также воспользуемся правилом Эйлера. В результате получим следующий ответ: катер должен доставить путешественников на остров E или F , чтобы они смогли пройти по каждому мосту один раз. Из того же правила Эйлера следует невозможность требуемого обхода, если он начнется с острова A.
В заключение отметим, что задача о Кенигсбергских мостах и подобные ей задачи вместе с совокупностью методов их исследования составляют очень важный в практическом отношении раздел математики, называемый теорией графов. Первая работа о графах принадлежала Л. Эйлеру и появилась в 1736 году. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков – К. Берж, О. Оре, А. Зыков.
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Наш мир полон не только букв и цифр, но и самых разнообразных изображений. Это и картины, и всевозможные фотографии, а также многочисленные схемы. Схемы встречаются на логотипах компаний и автомобилей, дорожных знаках и картах. Если посмотреть на схему метро или автобусного маршрута, это всего лишь линии с точками. Подобные схемы из линий (ребер) и точек (вершин) называются графами.
Теория графов появилась благодаря одной занимательной задаче, которую решил Леонард Эйлер. История гласит, что в 1736 году этот блестящий математик остановился в Кенигсберге. Город был разделен рекой на 4 части, соединенные семью мостами. Нужно было определить, можно ли обойти все мосты, пройдя по каждому ровно один раз. Эйлер определил, что решить задачу невозможно . Кенигсбергские мосты были разрушены во время Второй мировой войны, но эта история дала начало красивой математической теории - теории графов.
В XX веке теория графов получила невероятное развитие, она нашла многочисленные применения в задачах планирования, архитектуры, инженерии , а особенно в информатике и телекоммуникациях. Графы связаны с комбинаторикой, дискретной математикой, топологией, теорией алгоритмов и другими разделами математики.
Какие же возможности получает ученик, владеющий этой теорией? Сможет ли он достичь каких-то успехов в своей учебе или обычной жизни? Такому исследованию и посвящен данный проект.
Цель проекта: Показать, что методы теории графов дают школьнику инструмент, позволяющий решать сложные олимпиадные задачи, а в жизни - организовывать передачу срочной информации между людьми.
Гипотезы:
С помощью графов можно легко решать многие олимпиадные задачи
Теория графов помогает создать систему срочного оповещения коллектива
Задачи:
Разобраться с методами решения задач при помощи графов
Разработать сайт для тестирования олимпиадных задач
Спроектировать систему Срочного Оповещения Класса при помощи графа
Объекты исследования: олимпиадные задачи, системы оповещения
Предмет исследования: теория графов, web-программирование.
Методы исследований:
методы теории графов
методы web-программирования
План исследований:
Ознакомиться с историей возникновения теории графов
Изучить правила решения олимпиадных задач при помощи графов
Пройти курс «Web-программирование» Школы Информационных Технологий «REAL-IT»
Разработать сайт для тестирования олимпиадных задач по теории графов и опробовать его на друзьях
Спроектировать систему Срочного Оповещения Класса (СОК)
Провести эксперимент с целью тестирования системы СОК
Глава 1. Теория графов в нашей жизни
1.1. Применение теории графов в разных областях
Графы применяются в самых разных областях: при проектировании электрических цепей, телефонных сетей, при поиске маршрутов между населенными пунктами, в экономике .
В химии графы используются для представления различных соединений. С помощью графов можно изобразить как простые молекулы, так и довольно сложные органические соединения.
Теория графов играет ключевую роль в различных этапах архитектурных проектов. После того как определены части проекта и перед тем как перейти от эскизов к чертежам, будет полезно построить граф взаимосвязей элементов проекта. Анализ графов в общественных зданиях поможет определить степень доступности различных отделов, расположение помещений (буфета, библиотеки и др.), а также пожарных лестниц. Графы позволяют существенно упростить анализ сложных ситуаций .
В наше время благодаря интернету - «сети сетей», связывающей компьютеры по всему миру, стала возможной цифровая революция. Мощность компьютеров неуклонно возрастала, но совершить гигантский скачок к цифровому миру удалось именно благодаря сетям. Графы и телекоммуникации всегда шли рука об руку.
На рисунке 1.1 изображены различные схемы соединения компьютеров между собой. Чаще всего встречаются три способа объединения компьютеров в локальную сеть: "общая шина", "звезда", и "кольцо". Каждой схеме соответствует граф, поэтому применяется термин «Сетевая топология». Сетевая топология - это конфигурация графа, вершины которого: компьютеры и маршрутизаторы, а рёбра - линии связи (кабель) между ними . На рисунке 1.2 все топологии изображены в виде графов.
Дерево - это очень простой граф, в котором между любыми двумя вершинами существует единственный путь. Деревья используются в генетике для иллюстрации родственных связей (генеалогические деревья), а также при анализе вероятностей различных событий.
Рисунок.1.1. Варианты построения локальных компьютерных сетей
Рисунок 1.2. Варианты построения локальных компьютерных сетей
а - общая шина, б - звезда, в - кольцо
Существует множество игр, в которых нужно построить определенный граф (игры-лабиринты ) или с помощью графа определить, существует ли выигрышная стратегия.
GPS, карты и автомобильные маршруты, представленные в интернете, - еще один прекрасный пример использования графов. Ребрами в них являются улицы и автодороги, а вершинами - населенные пункты. Вершины таких графов имеют названия, а ребрам соответствуют числа, обозначающие расстояние в километрах. Таким образом, такой граф является помеченным и взвешенным. Графы помогают наглядно представить себе схемы общественного транспорта, что облегчает планирование поездки.
Графы также применяются в нефтегазовой отрасли в системах транспортировки нефти и газа. С помощью графоаналитических методов газотранспортных систем возможно выбрать из всех возможных путей обхода трубопровода наикратчайший вариант .
Развитие информатики привело к тому, что многие математические модели стали использоваться в автоматических процессах. Машина легко справляется с вычислениями, но выбрать наилучший вариант из множества в условиях неопределенности - задача намного более сложная. Появились новые алгоритмы, в которых используются механизмы, напоминающие биологическую революцию. Графы в них используют как способ визуализации процессов. Моделирование нейронов человеческого мозга и принципа их действия легло в основу новой теории - теории нейронных сетей.
1.2. Выводы по главе.
Теория графов нашла свое применение во многих областях науки, техники и повседневной жизни. Однако, несмотря на ее широкое применение в разных областях, в школьном курсе математики ей уделяется лишь поверхностное внимание. В то же время различные эксперименты в сфере образования показывают, что элементы теории графов имеют высокую образовательную ценность, поэтому должны быть включены в школьную программу.
Действительно, школьникам среднего звена весьма полезно будет изучить основы теории графов, поскольку они помогут им в освоении базового курса математики, и особенно - в решении олимпиадных задач по комбинаторике и теории вероятностей .
Глава 2. Теория графов в помощь школьнику
2.1. Теория графов в олимпиадных задачах
Различные математические олимпиады, такие как «Кенгуру», «Дино-олимпиада Учи.ру», Международная эвристическая олимпиада «Совёнок», также часто включают задачи по теории графов в разных формулировках .
Как известно, дети очень любят все, что связано с компьютерами и интернетом, и их не так просто усадить за стол с книжкой по математике. Для того, чтобы вызвать интерес у школьников к теории графов, авторами статьи на основе пройденных курсов по Web-программированию в Школе информационных технологий «REAL-IT» разработан онлайн-тренажер, включающий тестирование по теории графов, расположенный на странице Тюменской частной школы «Эвольвента»: evolventa-tmn.github.io . Школьникам предлагается решить шесть задач различного уровня сложности, он вводит ответы в окошки, а затем по нажатию кнопки «Готово» выдается результат: количество правильно решенных им задач (Рисунок 2.1).
Рисунок 2.1. Фрагмент экрана сайта с вариантами тестирования
Естественно, хитрый ребенок немедленно начнет искать ответы на поисковых серверах, но точно таких формулировок он не найдет, только подобные, например, на сайте научно-методического электронного журнала «Концепт» . Поэтому для получения вожделенного результата: 6 из 6 задач ученику придется разобраться в общих принципах решения задач с помощью теории графов. А в дальнейшем полученные знания помогут ему успешно решать как школьные, так и олимпиадные задачи.
Когда сайт был полностью готов, протестирован и выложен в Интернет, наши одноклассники получили ссылку на него. Интерес к сайту был велик: судя по счетчику посещений, за первую неделю его посетили больше 150 раз! Многие ребята пытались решить задачи, но они показались им сложными. Даже некоторых родителей, имеющих высшее техническое образование, ряд задач поставил в тупик, это говорит о том, что теория графов изучается даже не во всех высших учебных заведениях. Значит, подготовленное нами тестирование будет полезно не только школьникам, но и взрослым!
2.2. Теория графов при проектировании системы оповещения класса
В настоящее время сфере системы срочного управления персоналом в организациях уделяется большое внимание, в связи с тем, что такие системы играют существенную роль в организации всей деятельности сотрудников .
Первоначально системы оповещения и управления эвакуацией были задуманы для срочного информирования работников, персонала и гостей о возгорании в здании, предоставления информации и трансляции важных сведений для быстрой и успешной эвакуации людей . На сегодняшний день такие системы можно наблюдать не только в рамках одной организации или предприятия, но в масштабах всей нашей страны, применяемые в целях повышения безопасности людей.
Необходимо отметить, что большинство используемых систем оповещения ориентировано на взрослых людей. Но самый опасный возраст - это детский. Детям тоже нужны свои системы, позволяющие в кратчайшие сроки оповещать большую часть своих сверстников о надвигающейся опасности или об изменении обстановки.
В школе каждый ребенок проводит значительную часть своего времени: пять - шесть дней в неделю по несколько часов. Поэтому создание системы оповещения детей позволило бы организовать каждого ребенка на быструю и грамотную реакцию на изменившуюся обстановку.
Например, данная система была бы очень полезна при передаче сообщения об опасности, информации о срочном сборе или об изменении обстановки, когда они находятся в разных частях школы или вообще в лесу на отдыхе (Рисунок 2.2)
Рисунок 2.2. Наш класс на экскурсии в ГАУ ДО ТО "Региональный центр допризывной подготовки и патриотического воспитания "Аванпост"
В данной работе предпринята попытка создания Системы Оповещения Коллектива на примере одного класса образовательного учреждения: МАОУ СОШ № 89.
Поскольку дети должны сами распространять информацию, им следует пользоваться только доступными им всем видами связи - мобильной связью. Должен быть оповещен весь списочный состав класса, поэтому для анализа, кто из детей кого из своих друзей готов оповестить, было проведено анкетирование класса. В анкетах изначально было задано ограничение: каждый ребенок успевает позвонить максимум четырем друзьям, а если останется время - еще двоим.
Анкетирование показало довольно высокую активность ребят: в целом по классу будет сделано около 118 звонков. Проанализировать такой объем информации в уме практически невозможно, поэтому было решено воспользоваться информационными технологиями. Модель оповещения коллектива лучше всего представить в виде графа . Ребрами в нем являются звонки (или смс), а вершинами - дети. Поскольку вершины графа имеют названия, а ребрам соответствуют числа, обозначающие вероятность звонка (1 или 0,5), то такой граф является помеченным и взвешенным . Граф помогает наглядно представить себе схему оповещения коллектива, что облегчает моделирование.
Визуализацию графа было решено осуществлять с помощью CASE-средства RAMUS, поскольку он позволяет работать с цветом вершин и ребер, а также позволяет перемещать вершины графа с привязанными к ней ребрами для наглядности. На рисунке 2.3 показан граф системы СОК.
19 ноября 2017 года было проведено тестирование спроектированной системы СОК. Изначально мы планировали, что оповещение пройдет за три круга. Для первого круга (начала оповещения) мы выбрали двух детей, которым никто не хочет звонить, но они звонить готовы, а также самих авторов Проекта (Рис. 2.3, розовые блоки). Дальше информация передается ко второму кругу оповещения (Рис. 2.4, желтые блоки). И на третьем круге оповещения (Рис. 2.4, зеленые блоки) весь класс будет проинформирован. Но в ходе эксперимента мы увидели, что некоторые дети по 1,5-2 часа на тренировке и не смотрят на телефон, другие с отрицательным балансом, поэтому не могут звонить.
Рисунок 2.3. Граф системы оповещения класса
Рисунок 2.4. Круги оповещения системы СОК
Поэтому в реальности наш класс оказался оповещен только за 490 минут - это 8 часов 10 минут. Но зато это были все 100%. Здесь важно то, что наша система имеет структуру не дерева, а графа. А в нем из одной вершины в другую ведут несколько путей, поэтому в любом случае, оповещены будут все!
На рисунке 2.6 показан график оповещенности класса (количество оповещенных человек) в зависимости от времени (в минутах).
Рисунок 2.6. График оповещенности класса
Чтобы было легче следить за оповещенностью, в процессе тестирования дети должны были сообщить авторам Проекта свой любимый предмет, а они вели протокол, когда и кто сообщает информацию.
Еще один результат тестирования - опрос любимых предметов (Рисунок 2.7), показал, что дети нашего класса больше всего любят математику, информатику и подвижные игры! А это значит, что теория графов может им полюбиться так же, как и нам.
Рисунок 2.7. Круговая диаграмма любимых предметов класса
2.3. Выводы по главе.
Нами были проверены обе гипотезы. Разработанный нами сайт для тестирования олимпиадных задач по теории графов помог установить, что ряд олимпиадных задач просто невозможно решить без знаний теории графов, причем, даже взрослым-инженерам. Первая гипотеза получила подтверждение.
Вторая гипотеза также оказалась верной. Спроектированная и протестированная система оповещения коллектива на примере одного класса позволила за 8 часов 10 минут оповестить целый детский коллектив. Путем оптимизации графа можно добиться и более быстрых результатов.
Заключение.
Надеемся, что после знакомства с теорий графов и ее многочисленными применениями в разных областях, в школьниках пробудится интерес к теории графов, и они продолжат изучать этот раздел математики самостоятельно. Результатом изучения будут более высокие результаты на олимпиадах.
Что касается применения теории графов в реальной жизни, актуальность рассматриваемой темы подчеркивает то, что создание системы оповещения детей позволит увеличить скорость передачи срочной информации, охватить большую часть детского коллектива, для которого будет использоваться эта система, сократить время отклика детей, а также обеспечить максимальную безопасность для детского коллектива. Все это указывает на очевидные плюсы внедрения спроектированной системы.
Список литературы
Белобородова А.А. Развитие пространственного мышления при помощи игр-лабиринтов / А.А. Белобородова // «Студенческий научный форум»: материалы VIII Международной студенческой электронной научной конференции.- 2017. https://www.сайт/2017/7/26746
Белобородова, А.А. Разработка web-тренажера для изучения теории графов / А.А. Белобородова, С.В. Пахотин, А.А. Фролов // Новые информационные технологии в нефтегазовой отрасли и образовании: материалы VII Международной научно-технической конференции; отв. ред. О.Н. Кузяков. - Тюмень: ТИУ, 2017. - С. 156-159.
Белобородова А.А. С математикой не заблудишься! / А.А. Белобородова // XVIII Всероссийский детский конкурс научн.-иссл. и творческих работ «Первые шаги в науке»: сборник тезисов.- М.: НС Интеграция, Государственная Дума ФС РФ, Минобрнауки России.- 2016.- С. 110-111.
Генденштейн, Л.Э. Алиса в стране математики. Повесть-сказка / Для младш. и сред. школьного возраста.- Харьков: Изд.- коммер. предприятие "Паритет" ЛТД, 1994.-288 с., илл.
Давлетшин, М.И. Исследование эффективности методов удаления шумов на изображении / М. И. Давлетшин, К.В. Сызранцева // Энергосбережение и инновационные технологии в топливно-энергетическом комплексе: материалы Межд. науч.-практ. конф. студ., аспир., молодых ученых и спец. Т.1 / отв. редактор А.Н. Халин. - Тюмень: ТИУ, 2016. - С. 25- 29.
Карнаухова, А.А. Использование теории графов при решении задач в экономике / А.А. Карнаухова, А.Ф. Долгополова // Материалы VII Международной студенческой электронной научной конференции «Студенческий научный форум». http://www.scienceforum.ru/2015/991 .
Керн, Г. Лабиринты мира. СПб.: Изд-во "Азбука-классика", 2007, 448с.
Краузе, М.В. Применение информационных технологий для проектирования системы оповещения коллектива / М.В. Краузе, А.А. Белобородова, Е.И. Арбузова // Новые информационные технологии в нефтегазовой отрасли и образовании: материалы VII Международной научно-технической конференции; отв. ред. О.Н. Кузяков. - Тюмень: ТИУ, 2017. - С. 153-156.
Курс «Создание сайтов» Школы Информационных Технологий «REAL-IT» http://it-schools.org/faculties/web/
Мир математики: в 40 т. Т.11: Клауди Альсина. Карты метро и тейронные сети. Теория графов./ Пер. с исп.- М.: Де Агостини, 2014.- 144 с.
Москевич Л. В. Обучающая олимпиада - одна из форм внеурочных занятий математикой / Л.В. Москевич // Научно-методический электронный журнал «Концепт». - 2015. - Т. 6. - С. 166-170. - URL: http://e-koncept.ru/2015/65234.htm .
Памятка населению "Оповещение населения в случае угрозы и возникновении чрезвычайной ситуации" http://47.mchs.gov.ru/document/1306125
Румянцев, В.О. Математическое моделирование газотранспортной системы с помощью теории графов / В. О. Румянцев // Проблемы геологии и освоения недр: сб. науч. тр. / ТПУ. - Томск, 2017. - С. 340 - 342.
Сайт МЧС Российской Федерацииhttp://www.mchs.gov.ru/dop/Kompleksnaja_sistema_jekstrennogo_opoves
Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.
Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ” Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может“. Кенигсбергские мосты схематически можно изобразить так:
Правило Эйлера:
1. В графе, не имеющем вершин нечетных степеней, существует обход всех рёбер (причем каждое ребро проходится в точности один раз) с началом в любой вершине графа.
2. В графе, имеющем две и только две вершины с нечетными степенями, существует обход с началом в одной вершине с нечетной степенью и концом в другой.
3. В графе, имеющим более двух вершин с нечетной степенью, такого обхода не существует.
Существует еще один вид задач, связанных с путешествиями вдоль графов. Речь идёт о задачах, в которых требуется отыскать путь, проходящий через все вершины, причем не более одного раза через каждую. Цикл, проходящий через каждую вершину один и только один раз, носит название гамильтоновой линии(в честь Уильяма Роуэна Гамильтона, знаменитого ирландского математика прошлого века, который первым начал изучать такие линии). К сожалению, пока еще не найден общий критерий, с помощью которого можно было бы решить, является ли данный граф гамильтоновым, и если да, то найти на нём все гамильтоновы линии.
Сформулированная в середине 19 в. проблема четырех красок также выглядит как развлекательная задача, однако попытки ее решения привели к появлению некоторых исследований графов, имеющих теоретическое и прикладное значение. Проблема четырех красок формулируется так: ”Можно ли область любой плоской карты раскрасить четырьмя цветами так, чтобы любые две соседние области были раскрашены в различные цвета?”. Гипотеза о том, что ответ утвердительный, была сформулирована в середине 19в. В 1890 году было доказано более слабое утверждение, а именно, что любая плоская карта раскрашивается в пять цветов. Сопоставляя любой плоской карте двойственный ей плоский граф, получают эквивалентную формулировку задачи в терминах графов: Верно ли, что хроматическое число любого плоского графа меньше либо равно четырёх? Многочисленные попытки решения задачи оказали влияние на развитие ряда направлений теории графов. В 1976 году анонсировано положительное решение задачи с использованием ЭВМ.
Другая старая топологическая задача, которая особенно долго не поддавалась решению и будоражила умы любителей головоломок, известна как “задача об электро -, газо - и водоснабжении”. В 1917 году Генри Э.Дьюдени дал ей такую формулировку. В каждый из трёх домов, изображенных на рисунке, необходимо провести газ, свет и воду.
Тео́рия гра́фов. 1
История возникновения теории графов. 1
Правило Эйлера. 1
Литература
1. Белов Теория Графов, Москва, «Наука», 1968.
2. Новые педагогические и информационные технологии Е.С.Полат, Москва, «Akademia» 1999 г.
3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат , 1988.
4. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука , 1990.
5. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ , 1992.
6. Оре О. Теория графов. – М.: Наука , 1980.
7. Исмагилов Р.С., Калинкин А.В. Матеpиалы к пpактическим занятиям по куpсу: Дискpетная математика
Что такое метод графов?
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Прежде всего, стоит сказать о том, что графы, о которых пойдет речь, к аристократам былых времен никакого отношения не имеют. Наши «графы» имеют корнем греческое слово «графо», что значит «пишу». Тот же корень в словах «график», «биография».
В математике определение графа дается так: графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.
Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.2)
Графы, в которых не построены все возможные ребра, называются неполными графами. (рис.3)
Графы, в которых построены все возможные ребра, называются полными графами. (рис.4)
Граф, каждая вершина которого соединена с ребром любой другой вершины, называется полным .
Заметим, что если полный граф имеет n вершин, то количество ребер будет равно
n(n-1)/2
Действительно, количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из всех n точек-ребер графа, т. е. как число сочетаний из n элементов по 2:
Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.
Степени вершин и подсчет числа ребер.
Количество рёбер, выходящих из вершины графа, называется степенью вершины . Вершина графа, имеющая нечётную степень, называется нечетной , а чётную степень – чётной .
Если степени всех вершин графа равны, то граф называется однородным . Таким образом, любой полный граф - однородный.
рис.5
На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А.
На рисунке: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.
Сформулируем некоторые закономерности, присущие определенным графам.
Закономерность 1.
Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.
Доказательство:
Эта закономерность очевидна уже после рассмотрения любого полного графа. Каждая вершина соединена ребром с каждой вершиной, кроме самой себя, т. е. из каждой вершины графа, имеющего n вершин, исходит n-1 ребро, что и требовалось доказать.
Закономерность 2.
Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.
Эта закономерность справедлива не только для полного, но и для любого графа. Доказательство:
Действительно, каждое ребро графа связывает две вершины. Значит, если будем складывать число степеней всех вершин графа, то получим удвоенное число ребер 2R (R - число ребер графа), т. к. каждое ребро было подсчитано дважды, что и требовалось доказать
Число нечетных вершин любого графа четно. Доказательство:
Рассмотрим произвольный граф Г. Пусть в этом графе число вершин, степень которых 1, равна К1; число вершин, степень которых 2, равно K2; ...; число вершин, степень которых n, равно Кn. Тогда сумму степеней вершин этого графа можно записать как
K1 + 2К2 + ЗК3 + ...+ nКn.
С другой стороны: если число ребер графа R, то из закономерности 2 известно, что сумма степеней всех вершин графа равна 2R. Тогда можно записать равенство
K1 + 2К2 + ЗК3 + ... + nКn = 2R. (1)
Выделим в левой части равенства сумму, равную числу нечетных вершин графа (К1 + К3 + ...):
K1 + 2К2 + ЗК3 + 4К4 + 5К5 + ... + nК = 2R,
(К1 + К3 + К5 +...) + (2K2 + 2Х3 +4K4 + 4К5 + ...)=2R
Вторая скобка- четное число как сумма четных чисел. Полученная сумма (2R) четное число. Отсюда (К1 + К3 + К5 +...)-четное число.
Рассмотрим теперь задачи, решаемые с помощью графов:
Задача. Первенство класса . В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводится по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной и Еленой; Борис, как уже говорилось, с Андреем и еще с Галиной; Виктор – с Галиной, Дмитрием и Еленой; Галина с Андреем и Борисом; Дмитрий – с Виктором и Елена – с Андреем и Виктором. Сколько игр проведено к настоящему моменту и сколько еще осталось?
Обсуждение. Изобразим данные задачи в виде схемы. Участников будем изображать точками: Андрея – точкой А, Бориса – точкой Б и т.д. Если двое участников уже сыграли между собой, то будем соединять изображающие их точки отрезками. Получается схема, показанная на рисунке 1.
Точки А, Б, В, Г, Д, Е - вершины графа, соединяющие их отрезки – ребра графа.
Заметим, что точки пересечение ребер графа не являются его вершинами.
Число игр, проведенных к настоящему моменту, равно числу ребер, т.е. 7.
Во избежание путаницы вершины графа часто изображают не точками, а маленькими кружочками.
Чтобы найти число игр, которые надо провести, построим еще один граф с теми же вершинами, но ребрами будем соединять тех участников, которые еще не играли друг с другом (рис.2) Ребер у этого графа оказалось 8, значит, осталось провести 8 игр: Андрей – с Виктором и Дмитрием; Борис – С Виктором, Дмитрием и Еленой и т.д.
Попробуем построить граф для ситуации, описанной в следующей задаче:
Задача. Кто играет Ляпкина – Тяпкина? В школьном драмкружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Все началось с Ляпкина – Тяпкина.
Ляпкиным – Тяпкиным буду я! – решительно заявил Гена.
Нет, я буду Ляпкиным – Тяпкиным, возразил Дима.- С раннего детства мечтал воплотить этот образ на сцене.
Ну, хорошо, уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена.
- …А мне – Осипа, - не уступил ему в великодушии Дима.
Хочу быть Земляникой или Городничим,- сказал Вова.
Нет, Городничим буду я, - хором закричали Алик и Боря. – Или Хлестаковым, -
Удастся ли распределить роли так, чтобы исполнители были довольны?
Обсуждение.
Изобразим юных актеров кружками верхнего ряда: А – Алик, Б – Борис, В – Вова, Г – Гена, Д – Дима, а роли, которые они собираются играть, - кружками второго ряда (1 – Ляпкин – Тяпкин, 2 – Хлестаков, 3 – Осип, 4 – Земляника, 5 – Городничий). Затем от каждого участника проведем отрезки, т.е. ребра, к ролям, которые он хотел бы сыграть. У нас получиться граф с десятью вершинами и десятью ребрами (рис.3)
Чтобы решить задачу, нужно из десяти выбрать пять ребер, не имеющих общих вершин. Сделать это легко. Достаточно заметить, что в вершины 3 и 4 ведут по одному ребру, из вершин Д и В соответственно. Это означает, что Осипа (вершина 3) должен играть Дима (кто же еще?), а Земляничку – Вова. Вершина1 – Ляпкин – Тяпкин – соединена ребрами с Г и Д. Ребро 1 – Д отдает, так как Дима уже занят, остается 1 – Г, Ляпкина – Тяпкина должен играть Гена. Остается соединить вершины А и Б с вершинами 2 и 5, соответствующими ролям Хлестакова и Городничего. Это можно сделать двумя способами: либо выбрать ребро А -5 и Б – 2, либо ребро А -2 и Б -5. В первом случае Алик будет играть Городничего, а Боря – Хлестакова, во втором случае наоборот. Как показывает граф, других решений задача не имеет.
Тот же граф получится при решении следующей задачи:
Задача. Сварливые соседи. Жители пяти домов поссорились друг с другом и, чтобы не встречаться у колодцев, решили поделить их (колодцы) так, чтобы хозяин каждого дома ходил к «своему» колодцу по «своей» тропинке. Удастся ли им это сделать?
Возникает вопрос: так ли нужны были графы в разобранных задачах? Разве нельзя прийти к решению чисто логическим путем? Да, можно. Но графы придали условиям наглядность, упростили решение и выявили сходство задач, превратив две задачи в одну, а это уже не так уж мало. А теперь представьте себе задачи, графы которых имеют 100 или более вершин. А ведь именно такие задачи приходиться решать современным инженерам и экономистам. Тут без графов не обойтись.
III. Графы Эйлера.
Теория графов – наука сравнительно молодая: во времена Ньютона такой науки еще не существовало, хотя и были в ходу «генеалогические деревья», представ-ляющие собой разновидности графов. Первая работа по теории графов принадлежит Леонарду Эйлеру, и появилась она в 1736 году в публикациях петербургской Академии наук. Начиналась эта работа с рассмотрения следующей задачи:
а)Задача о кенигсбергских мостах.
Город Кенигсберг (ныне Калининград) расположен на берегах и двух островах реки Прегель (Преголи).Различные части города были соединены семью мостами, как показано на рисунке. В воскресные дни горожане совершают прогулки по городу. Можно ли выбрать такой маршрут, чтобы пройти один и только один раз по каждому мосту и потом вернуться в начальную точку пути?
Прежде чем рассмотреть решение данной задачи, мы введем понятие «Эйлеровы графы.
Попробуем граф, изображенную на рис.4, обвести одним росчерком , то есть, не отрывая карандаша от листа бумаги и не проходя по одной и той же части линии более одного раза.
Фигура эта, такая простая на вид, оказывается, имеет интересную особенность. Если мы начнем движение из вершины В, то у нас это обязательно получится. А что будет, если мы начнем движение из вершины А? Легко убедиться, что обвести линию в этом случае нам не удается: у нас всегда будет оставаться не пройденные ребра, добраться до которых уже невозможно.
На рис. 5 изображен граф, который вы, наверное, умеете рисовать одним росчерком. Это звезда. Оказывается, хотя она и выглядит значительно более сложной, чем предыдущий граф, обвести ее можно, начав с любой вершины.
Графы, начерченные на рис.6 также можно начертить одним росчерком пера.
Теперь попробуйте вычертить одним росчерком граф, изображенный на рис.7
Вам это сделать не удалось! Почему? Вы не можете найти нужную вершину? Нет! Дело не в этом. Этот граф вообще нельзя вычертить одним росчерком пера.
Проведем рассуждения, которые убедят нас в этом. Рассмотрим узел А. Из него выходят три вершины. Начнем вычерчивать граф с этой вершины. Чтобы пройти по каждому из этих ребер, мы должны выйти из вершины А по одному из них, в какой – то момент обязательно вернуться в него по второму и выйти по третьему. А вот снова войти уже не сможем! Значит, если мы начнем вычерчивание с вершины А, то закончить в нем не сможем.
Допустим теперь, что вершина А не является началом. Тогда в процессе вычерчивания мы должны войти в него по одному из ребер, выйти по другому и снова вернуться по третьему. А так как выйти из него мы не сможем, то вершина А в этом случае должен являться концом.
Итак, вершина А должен быть или началом, или конечным узлом вычерчивания.
Но про три другие вершины нашего графа можно сказать то же самое. Но ведь и начальной вершиной вычерчивания может быть только одна вершина, и конечной вершиной также может быть только одна вершина! А значит, вычерчивать этот граф одним росчерком невозможно.
Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым (рис.6).
Такими графы названы в честь учёного Леонарда Эйлера.
Закономерность1. (вытекает из рассмотренной нами теоремы).
Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 2.
Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Закономерность 3.
Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.
Закономерность 4.
Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».
Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной.
Граф называется связным, если любые две его вершины могут быть соединены путем, т. е. последовательностью ребер, каждое следующее из которых начинается в конце предыдущего.
Граф называется несвязным , если это условие не выполняется.
рис.7
рис.8
На рисунке 7, очевидно, изображен несвязный граф. Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным. (рис.8)
Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом .
Примерами мостов на рисунке 7 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа.(рис.8)
Несвязный граф состоит из нескольких «кусков». Эти «куски» называются компонентами связности графа. Каждая компонента связности является, конечно, связным графом. Отметим, что связный граф имеет одну компоненту связности.
ТЕОРЕМА.
Граф является эйлеровым тогда и только тогда, когда он связан и имеет не более двух нечетных вершин.
Доказательство:
Рисуя граф каждую вершину, за исключением начальной и конечной, мы войдём столько же раз, сколько выйдем из неё. Поэтому степени всех вершин должны быть чётными, кроме двух, а значит, эйлеров граф имеет не более двух нечётных вершин.
Вернемся теперь к задаче о кенигсбергских мостах.
Обсуждение задачи . Обозначим различные части города буквами А, В, С, Д, а мосты – буквами а, b, c, d, e, f, g – мосты, соединяющие соответствующие части города. В этой задаче существуют лишь переходы через мосты: переходя через любой мост, мы всегда из одной части города попадаем в другую, И, наоборот, переходя из одной части города в другую, мы непременно пройдем по мосту. Поэтому, изобразим план города в виде графа, вершины которого А, В, С, Д (рис.8) изображают отдельные части города, а ребра a, b, c, d, e, f, g – мосты, соединяющие соответствующие части города. Ребра зачастую оказываются удобнее изображать удобнее не прямолинейными отрезками, а криволинейными – «дугами».
Если бы существовал маршрут, удовлетворяющий условию задачи, то существовал бы замкнутый непрерывный обход этого графа, проходящий один раз по каждому ребру. Иными словами этот граф должен вычерчиваться одним росчерком. Но это невозможно – какую бы вершину мы ни выбрали за исходную, нам придется проходить через остальные вершины, и при этом каждому «входящему» ребру (мосту, по которому мы вошли в эту часть города) будет соответствовать «выходящее» ребро мост, которым мы и воспользуемся затем, чтобы покинуть эту часть города): число ребер, входящих в каждую вершину, будет равно числу ребер, выходящих из нее, т. е. общее число ребер, сходящихся в каждой вершине, должен быть четным. Наш граф этому условию не удовлетворяет, и поэтому требуемого маршрута не существует.
1736 год, г.Кёнигсберг. Через город протекает река Прегеля. В городе - семь мостов, расположенных так, как показано на рисунке выше. С давних времен жители Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз? Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках - проходя по этим самым мостам. Никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по мостам никто не мог.
Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач. При решении задачи о Кенигсбергских мостах Эйлер поступил следующим образом: он "сжал" сушу в точки, а мосты "вытянул" в линии. Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют ГРАФОМ .
Граф – это совокупность непустого множества вершин и связей между вершинами. Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами.
Виды графов:
1. Ориентированный граф (кратко орграф ) - рёбрам которого присвоено направление.
2. Неориентированный граф - это граф , в котором нет направления линий.
3. Взвешенный граф – дуги или ребра имеют вес (дополнительная информация).
Решение задач с помощью графов:
Задача 1.
Решение: Обозначим ученых вершинами графа и проведем от каждой вершины линии к четырем другим вершинам. Получаем 10 линий, которые и будут считаться рукопожатиями.
Задача 2.
На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.
Решение:
Вершины графа - это деревья, обозначенный первой буквой названия дерева. В данной задача два отношения: “быть ниже” и “быть выше”. Рассмотрим отношение “быть ниже” и проведем стрелки от более низкого дерева к более высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что самое низкое дерево – клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь.
Задача 3.
У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?
Решение:
Ниже представлен разбор задач.
Загрузка...