теория конечных графов и ее приложения

Теория конечных графов и ее приложения

Учебное пособие для студентов направления подготовки бакалавров

010300.62 «Фундаментальная информатика и информационные технологии»

Б р я н с к Издательство «Курсив»

Учебное пособие издано на средства внутривузовского гранта №

Рекомендовано к изданию кафедрой алгебры и геометрии Брянского государственного университета имени академика И.Г. Петровского.

Теория конечных графов и ее приложения. Учебное пособие для студентов направления подготовки бакалавров 010300.62 «Фундаментальная информатика и информационные технологии». – Брянск: Издательство «Курсив», 2013. – 180 с.

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

Учебник предназначен для студентов вузов направления подготовки бакалавров 010300.62 «Фундаментальная информатика и информационные технологии».

УДК 519.17 ББК 22.18

© ФГБОУ ВПО «Брянский государственный университет имени академика И.Г. Петровского», 2013 © Сорокина М.М., 2013 © Издательство «Курсив», 2013

§ 5. Операции над графами.

§ 9. Связные графы и их простейшие свойства. Критерий связ-

§ 11. Оценка числа ребер графа через число вершин и число

§ 13. Гамильтоновы графы.

§ 14. Вершинно непересекающиеся и реберно непересекаю-

§ 15. Метрические характеристики связных графов.

§ 16. Взвешенные связные неорграфы.

§ 18. Устойчивые множества и покрытия.

Глава III. Деревья и их приложения.

§ 19. Деревья и их простейшие свойства.

§ 22. Фундаментальные циклы и фундаментальные разрезы

§ 23. Плоские и планарные графы.

§ 25. Раскраска графов.

Тема 6. Сильные компоненты графа.

Тема 8. Нахождение в графах путей минимального и макси-

Тема 9. Фундаментальные циклы и фундаментальные разрезы

Тема 10. Нахождение остовов графа минимального и макси-

Примерный перечень вопросов к зачету по учебной дисципли-

Учебное пособие «Теория конечных графов и ее приложения» предназначено для студентов вузов направления подготовки бакалавров 010300.62 «Фундаментальная информатика и информационные технологии». Материал учебного пособия охватывает основные разделы теории конечных графов.

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

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

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

Долгое время эти результаты оставались единственными в теории графов, и лишь в середине XIX века были получены новые результаты. А именно, Г. Кирхгофом в 1847 году была использована теория графов в теории электрических цепей (законы Кирхгофа). В 1857 году А. Келли разработал теорию де-

ревьев и применил ее к теории химических изомеров.

Хотя теория графов существует уже более 200 лет, ее интенсивное развитие приходится лишь на последние 50-60 лет. Это было вызвано широким использованием графов в экономике, химии, биологии, социологии, теории проектирования и мн. др. Для понятия «граф» в современной научной литературе нет единого определения. Разные авторы, исходя из поставленных целей, называют графом очень похожие, но все-таки различные объекты. Сам термин « граф» введен в употребление в 1936 году венгерским математиком Д. Кенигом. Терминология теории графов в настоящее время еще не устоялась, и понятийный аппарат в различных учебниках имеет существенные расхождения.

Глава I. Введение в теорию графов

§ 1. Основные понятия теории графов

 мультиграф, вершины и ребра мультиграфа, отображение инцидентности;

 смежные вершины (ребра) мультиграфа;

 кратные ребра мультиграфа; граф;

 ориентированное (неориентированное) ребро, ориентированный (неориентированный) мультиграф, ориентированный (неориентированный) граф;

 петля, псевдограф, простой граф;

 конечный (бесконечный) граф, граф n-го порядка;

 тривиальный граф, пустой граф, полный граф, число ребер полного графа n-го порядка;

 граф как алгебраическая система;

 часть графа, подграф графа.

– некоторое множество. Напомним, что

V – непустое множество объектов, называемых вершинами мультиграфа G и обозначаемых на плоскости и в пространстве точками,

R – множество (возможно пустое) объектов, называемых ребрами мультиграфа G и обозначаемых на плоскости и в пространстве линиями,

Источник

Теория конечных графов и ее приложения

Харари Ф. Теория графов. – М.: Мир, 1973.

Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990.

Берж К. Теория графов и ее применения. – М.: Изд. иностр. лит., 1962.

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

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

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

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

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

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

Источник

Учебно-методический комплекс по дисциплине «Теория конечных графов и ее приложения» Алексеев В. Е, Захарова Д. В

Главная > Учебно-методический комплекс

Нижегородский государственный университет им. Н.И. Лобачевского

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

Учебно-научный и инновационный комплекс

«Модели, методы и программные средства»

Основная образовательная программа

010300 «Фундаментальная информатика и информационные технологии», общий профиль, квалификация (степень) бакалавр

Учебно-методический комплекс по дисциплине

«Теория конечных графов и ее приложения»

Алексеев В.Е, Захарова Д.В.

Электронное учебно-методическое пособие

Мероприятие 1.2. Совершенствование образовательных технологий, укрепление материально-технической базы учебного процесса

ТЕОРИЯ ГРАФОВ. Алексеев В.Е., Захарова Д.В. Электронное учебно-методическое пособие. – Нижний Новгород: Нижегородский госуниверситет, 2012. – 57 с.

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

Электронное учебно-методическое пособие предназначено для студентов ННГУ, обучающихся по направлению подготовки 010300 «Фундаментальная информатика и информационные технологии», изучающих курс «Теория конечных графов и ее приложения».

1. Начальные понятия 5

Определение графа 5

Способы задания графов 5

Окрестности и степени 6

Некоторые специальные графы 6

Операции над графами 7

Пути, циклы, связность 8

Расстояния и метрические характеристики 9

Графы пересечений 9

Помеченные графы 12

Непомеченные графы 13

Двудольные графы 19

Планарные графы 19

Поиск в глубину 25

Гамильтоновы циклы 32

Пространство циклов 34

Паросочетания и реберные покрытия 44

Метод увеличивающих путей 45

Паросочетания в двудольных графах 45

Независимые множества в двудольных графах 46

Раскраска вершин 48

Раскраска ребер 49

Алгоритм Краскала 52

Кратчайшие пути 53

Предисловие

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

Пособие является комбинацией конспекта лекций и сборника задач. В нем излагаются все необходимые теоретические сведения – определения и математические факты. При этом доказательства теорем, как правило, не приводятся. Отсутствующие доказательства могут быть найдены либо в [1] или [2], либо в источнике, указанном в заголовке теоремы, либо достаточно просты и студенты могут их восстановить самостоятельно.

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

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

1. Начальные понятия

Определение графа

Способы задания графов

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

1. Перечисление элементов. Исходя из определения, для того, чтобы задать граф, достаточно перечислить его вершины и ребра (т.е. пары вершин).

2. Изображение. Если граф невелик, его можно нарисовать. В неориентированном графе ребра изображаются линиями, в ориентированном – стрелками.

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

Окрестности и степени

Множество вершин, смежных с данной вершиной х в некотором графе, называется окрестностью этой вершины и обозначается через N ( x ). Число вершин в N ( x ) называется степенью вершины х и обозначается через deg( x ).

Если сложить степени всех вершин графа, то каждое ребро внесет в эту сумму вклад, равный 2. Следовательно, сумма степеней всех вершин равна удвоенному числу ребер графа:

.

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

.

Некоторые специальные графы

Пустой граф – граф, не содержащий ни одного ребра. Пустой граф с множеством вершин обозначается .

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

Путь имеет множество вершин , ребрами его являются пары , .

Цикл получается из графа добавлением ребра .

Изоморфизм

Тот факт, что графы и изоморфны, записывается так: .

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

Подграфы

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

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

Операции над графами

Для графов и их объединение определяется как граф , а пересечение – как граф .

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

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

, .

На рисунке 3 показано, как получается из .

Пути, циклы, связность

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

Цикл ­– путь, у которого .

Шарнир ( точка сочленения ) в графе – вершина, при удалении которой увеличивается число компонент связности.

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

В ориентированном графе можно определить два типа путей.

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

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

Расстояния и метрические характеристики

Расстоянием между вершинами в графе называется наименьшая длина соединяющего их пути. Расстояние между вершинами x и y обозначается через .

Эксцентриситет вершины – расстояние от нее до самой удаленной вершины:

.

Диаметр графа – максимальное расстояние между вершинами, то есть наибольший эксцентриситет:

.

Радиус графа – наименьший эксцентриситет:

.

Центральная вершина – вершина, эксцентриситет которой равен радиусу графа.

Центр – множество всех центральных вершин.

Диаметр и радиус графа связаны соотношениями:

.

Графы пересечений

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

Источник