Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате 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

7. Применение графов в жизни

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

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

· В информатике и программировании (граф - схема алгоритма).

· В коммуникационных и транспортных системах. В частности, для маршрутизации данных в интернете.

· В экономике.

· В логистике.

· В физике или схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф).

· В биологии.

· стереохимии

· В строительстве.

· В менеджменте.

· В географии.

· В социологии.

· В автоматизации технологических процессов и производств.

Графы в биологии.

Графы в биологии большую роль в биологический теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся процессов - размножение бактерий. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево. Нас будет интересовать лишь один вопрос: в скольких случаях n - е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под название процесса Гальтона - Ватсона. Его можно рассматривать как частный случай многих общих формул.

Графы в теории массового обслуживания.

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

Графы в математике.

В математике графы применяются для решения логических задач и головоломок. Основной применения графов для решения логических задач служит выявление и последовательное исключение возможностей, заданных в условии. Это выявление логических возможностей часто может быть истолковано с помощью построения и рассмотрения соответствующих графов. Возьмем, к примеру, такую задачу: «Беседуют трое: Белокуров, Чернов и Рыжов. Брюнет сказал Белокурову: «Любопытство, что один из нас русый, другой - брюнет, а третий - рыжий, но ни кого цвет волос не соответствует фамилии». Какой цвет волос имеет из беседующих?» Решение данной задачи можно изобразить с помощью графа.

Графы в физике.

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

Теория графов в психологии.

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

Теория графов в логистике.

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

Графы

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

Математические методы, применяемые в теории систем массового обслуживания

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых...

Метод Дейкстры нахождения кратчайшей цепи в связном графе

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

Орграфы, теория и применение

Матрица инцидентности A. По вертикали указываются вершины, по горизонтали - ребра. Aij=1 если вершина i инцидентна ребру j, в противном случае aij=0. Для орграфа aij=-1 если из вершины i исходит ребро j, aij=1 если в вершину i входит ребро j. Если ребро - петля...

Орграфы, теория и применение

Орграфы и матрицы. Матрицей сложностей A (D) орграфа D называется (рхр)-матрица аи> У которой ai}=, если vfl,-- дуга орграфа D, и atj~Q в противном случае. Сумма по столбцу легко проверить...

Особенности применения теории графов при решении задач и в практической деятельности

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

Построение фигур без отрыва карандаша от бумаги

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

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

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

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

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

Это по сути граф. Пять компьютеров являются вершинами, а соединения (пути передачи сигналов) между ними – ребрами. Заменив компьютеры вершинами, мы получим математический объект – граф, который имеет 10 ребер и 5 вершин. Пронумеровать вершины можно произвольным образом, а не обязательно так, как это сделано на рисунке. Стоит отметить, что в данном примере не используется ни одной петли, то есть такого ребра, которое выходит из вершины и сразу же входит в нее, но петли могут встречаться в задачах.

Вот некоторые важные обозначения, используемые в теории графов:

• G=(V, E), здесь G – граф, V – его вершины, а E – ребра;
• |V| – порядок (число вершин);
• |E| – размер графа (число рёбер).

В нашем случае (рис. 1) |V|=5, |E|=10;

Когда из любой вершины доступна любая другая вершина, то такой граф называется неориентированным связным графом (рис. 1). Если же граф связный, но это условие не выполняется, тогда такой граф называется ориентированным или орграфом (рис. 2).

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

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

Ориентированные графы имеют следующую форму записи:

G=(V, A), где V – вершины, A – направленные ребра.

Третий тип графов – смешанные графы (рис. 3). Они имеют как направленные ребра, так и ненаправленные. Формально смешанный граф записывается так: G=(V, E, A), где каждая из букв в скобках обозначает тоже, что ей приписывалось ранее.

В графе на рисунке 3 одни дуги направленные [(e, a), (e, c), (a, b), (c, a), (d, b)], другие – ненаправленные [(e, d), (e, b), (d, c)…].

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

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

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

В любом из рассмотренных нами графов имеется возможность выделить путь и, причем не один. Путь – это последовательность вершин, каждая из которых соединена с последующей посредством ребра. Если первая и последняя вершины совпадают, то такой путь называется циклом. Длина пути определяется количеством составляющих его ребер. Например, на рисунке 4.а путем служит последовательность [(e), (a), (b), (c)]. Этот путь является подграфом, так как к нему применимо определение последнего, а именно: граф G’=(V’, E’) является подграфом графа G=(V, E), только тогда когда V’ и E’ принадлежат V, E.

Что такое метод графов?

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

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

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.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 – мосты, соединяющие соответствующие части города. Ребра зачастую оказываются удобнее изображать удобнее не прямолинейными отрезками, а криволинейными – «дугами».

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

Учебное издание

Ююкин Николай Алексеевич

ЛР № . Подписано в печать

Уч. Изд. л.. , .

Воронежский государственный технический университет

394026 Воронеж, Московский просп. 14

СПРАВОЧНИК МАГНИТНОГО ДИСКА

Кафедра высшей математики и физико-математического моделирования

Н.А. Ююкин

ДИСКРЕТНАЯ МАТЕМАТИКА Часть 1. Элементы теории графов

Учебное пособие

Н.А. Ююкин

ДИСКРЕТНАЯ МАТЕМАТИКА Часть 1. Элементы теории графов

Учебное пособие

Воронеж 2004

ВВЕДЕНИЕ

Данное пособие может быть использовано в курсе “Дискретная математика” студентами ВГТУ, обучающимися по специальностям:

090102 – Компьютерная безопасность;

090105 – Комплексное обеспечение информационной безопасности автоматизированных систем;

090106 - Информационная безопасность телекоммуникационных систем.

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

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

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

в орграфах; анализ графа цепи Маркова; алгоритмы поиска кратчайших путей в графах; задача поиска гамильтонова цикла

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

Целью курса является формирование у студентов теоретических знаний, практических умений и навыков в области моделирования процессов и явлений в естествознании и техни-

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

Достижению данной цели служат следующие задачи:

изучить максимально широкий круг понятий теории графов;

получить навыки решения учебных и практических задач;

овладеть методами оптимизации;

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

Дисциплина “Дискретная математика” относится к числу прикладных математических дисциплин. Она основывается на знаниях, приобретенных студентами при изучении дисциплин “Алгебра” и “Математическая логика и теория алгоритмов”. Знания и навыки, полученные при изучении дисциплины “Дискретная математика” используются при изучении общепрофессиональных и специальных дисциплин.

1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ.

1.1. Задачи теории графов.

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

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

Первая задача . Задача о Кенигсбергских мостах была поставлена и решена Эйлером в 1786 году. Город располагался на берегах и двух островах реки Преголи. Острова между собой и берегами были связаны семью мостами, как показано на рисунке.

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

Вторая задача . Задача о трех домах и трех колодцах. Имеется три дома и три колодца.

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

решена Понтрягиным и независимо от него Куратовским в

Третья задача . О четырех красках. Любую карту на плоскости раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одним цветом.

Многие результаты теории графов используются для решения практических задач науки и техники. Так, в середине 19 века Кирхгоф применил теорию графов для расчета сложных электрических цепей. Однако, как математическая дисциплина, теория графов сформировалась только в 30-ых годах 20го века. При этом графы рассматриваются как некоторые абстрактные математические объекты. Они применяются при анализе и синтезе цепей и систем, в сетевом планировании и управлении, исследовании операций, программировании, моделировании жизнедеятельности организма и других областях.

1.2. Основные определения.

Графом G= (V,E ) называется совокупность двух множеств - непустого множества вершин V и множества неупорядоченных и упорядоченных пар вершин E . В дальнейшем будут рассматриваться конечные графы , т.е. графы с конечным множеством вершин и конечным семейством пар. Неупорядоченная пара вершин называется ребром , а упорядоченная - дугой .

Обычно граф изображается диаграммой : вершины - точками (или кружками), ребра – линиями произвольной конфигурации. На дуге дополнительно стрелкой указывается её направление. Отметим, что при изображении графа несуще-

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

Вершины, которые не принадлежат ни одному ребру (дуге) называются изолированными. Вершины, соединенные ребром или дугой называются смежными . Ребро (дуга) и любая из его двух вершин называются инцидентными .

Говорят, что ребро (u,v ) соединяет вершины u и v , а дуга (u,v) начинается в вершине u и заканчивается в вершине v , при этом u называется началом , а v – концом этой дуги.

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

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

Граф, состоящий из одной изолированной вершины (K 1 ), называется тривиальным .

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

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

1.3. Степени вершин графа.

Степенью (валентностью) (обозначение d (v ) или deg (v )) вершины v простого графа G называется число ребер или дуг инцидентных данной вершине v . При подсчете валентности вершин псевдографа следует учитывать каждую петлю дважды.

Если степени всех вершин н-графа равны k , то граф называется регулярным (однородным) степени k . Если степень вершины равна 0 , то она является изолированной . Если степень вершины равна 1 , то вершина называется концевой (висячей, тупиковой).

Для орграфа число дуг исходящих из вершины v назы-

вается полустепенью исхода										(v ), а входящих – полустепе-
нью захода d							(v ), При этом справедливо соотношение d (v )=
		(v )+			(v ).

Теорема Эйлера : Сумма степеней вершин графа равна

удвоенному количеству ребер, т.е.

d (vi )

			(v )

Где n – число вершин; m – число

ребер (дуг). Данное утверждение доказывается тем, что при подсчете суммы степеней вершин каждое ребро учитывается два раза - для одного конца ребра и для другого.

1.4. Изоморфизм графов.

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

метками (номерами). Граф считается полностью заданным в строгом смысле , если нумерация его вершин и ребер фиксирована. При этом графы G 1 и G 2 называются равными (обозначение G 1 = G 2 ) , , если их множества вершин и ребер совпадают. Два графа или псевдографа G 1 = (V 1 ,E 1 ) и G 2 = (V 2 ,E 2 ) называют-

	изоморфными (обозначение G				если существуют
	взаимно однозначных отображения: 1)				: V 1 V 2
: E 1 E 2 такие, что для любых двух вершин u , v в графе
	справедливо соотношение ((u , v )) ((u ), (v )) .
	Два простых графа (без петель и кратных ребер) G 1					и G 2

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

значное отображение

: V 1 V 2

Такое что

(u , v ) ((u ), (v )) .

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

Рефлексивности -

G 1 ,

причем биекция

ставляет собой тождественную функцию.

Симметричности.

с биекцией

с биекцией

Транзитивности.

G 1 G 2

биекцией

1 ,а

с биекцией

то G G

с биекцией

2 (1 ) .