Учебно-методический комплекс по дисциплине «Теория конечных графов и ее приложения» Алексеев В. Е, Захарова Д. В - umotnas.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
Учебно-методический комплекс по учебным дисциплинам «Теория измерений» 5 1372.5kb.
Учебно-методический комплекс дисциплины "информатика" Ростов-на-Дону... 2 952.2kb.
Учебно-методический комплекс по дисциплине «Теория массового обслуживания» 3 423.08kb.
Учебно-методический комплекс дисциплины Теория организации Для студентов... 1 273.91kb.
Учебно-методический комплекс дисциплины Теория организации Для студентов... 1 273.67kb.
Учебно-методический комплекс по дисциплине Информационная безопасность... 3 975.61kb.
Учебно-методический комплекс по дисциплине "Теория языков и автоматов"... 2 406.38kb.
Учебно-методический комплекс по дисциплине Б2 «Теория алгоритмов»... 4 1207.67kb.
Учебно-методический комплекс по дисциплине «теория и практика коммуникации»... 1 190.86kb.
Учебно-методический комплекс по дисциплине теория систем и системный... 1 215.11kb.
Учебно-методический комплекс по дисциплине «Основы туризмологии»... 1 407.18kb.
Поиск в глубину 1 16.37kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Учебно-методический комплекс по дисциплине «Теория конечных графов и ее приложения» - страница №1/8




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


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

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



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

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



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

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




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

ТЕОРИЯ ГРАФОВ
Электронное учебно-методическое пособие

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

Нижний Новгород

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

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

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

Оглавление



Предисловие 4

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

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

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

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

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

Изоморфизм 6

Подграфы 7

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

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

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

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

Задачи 10

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

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

Задачи 15

Деревья 17

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

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

Задачи 22

Поиск в ширину 25

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

Задачи 29

Эйлеровы циклы 31

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

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

Задачи 38

Задачи 43

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

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

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

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

Задачи 48

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

Раскраска ребер 50

Задачи 51

Алгоритм Прима 52

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

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

Задачи 55

Задачи 59


Предисловие

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

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

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

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

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

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


Граф состоит из двух множеств – множества V, элементы которого называются вершинами, и множества Е, состоящего из пар вершин, эти пары называются ребрами графа. Это записывают так: G = (V, E), где G – имя графа.

Один момент в этом определении требует уточнения: считаем ли мы ребра и различными. Если да (и это распространяется на все ребра), то граф называется ориентированным (сокращенно орграф), в противном случае ­– неориентированным.

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

Говорят, что ребро инцидентно каждой из вершин а и b, а каждая из этих вершин инцидентна ребру е.

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

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

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


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

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

3. Матрица смежности. Пусть G – граф с n вершинами, пронумерованными числами от 1 до n. Матрица смежности – это таблица с n строками и n столбцами, в которой элемент, стоящий на пересечении строки с номером i и столбца с номером j, равен 1, если вершины с номерами i и j смежны, и 0, если они не смежны.

4. Матрица инцидентности. Пусть G – граф, вершины которого пронумерованы числами от 1 до n, а ребра – числами от 1 до m. В матрице инцидентности строки соответствуют вершинам, а столбцы – ребрам. На пересечении строки с номером i и столбца с номером j стоит 1, если вершина с номерами i инцидентна ребру с номером j смежны, и 0 в противном случае.

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

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


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

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



.

Это утверждение называют теоремой о рукопожатиях.



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

.

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


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

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

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

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

Полный двудольный граф . Множество вершин состоит из двух частей, в одной из них p вершин, в другой q. Любые две вершины из одной части не смежны, любые две вершины из разных частей смежны.

Изоморфизм


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

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

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

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

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

Подграфы


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

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



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

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


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

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

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

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

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



Рис. 2.
Другой пример – k-мерный куб , определяемый следующим образом. Вершинами его являются всевозможные упорядоченные двоичные наборы длины k. Всего, таким образом, в этом графе вершин. Вершины и смежны в нем тогда и только тогда, когда наборы x и y различаются точно в одной координате. С помощью операции произведения граф можно определить рекурсивно:



, .

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



Рис. 3.

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


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

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

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

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

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

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

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


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


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

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

.

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

.

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

.

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

Центр – множество всех центральных вершин.
Диаметр и радиус графа связаны соотношениями:
.

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


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

Задачи

1.1. Граф задан множеством вершин и множеством ребер



. Нарисуйте этот граф, постройте для него матрицы

смежности и инцидентности, списки смежности.


1.2. Постройте матрицу инцидентности для графа, заданного списками смежности:


1.3. В графе 30 вершин и 80 ребер, каждая вершина имеет степень 5 или 6. Сколько в нем

вершин степени 5?


1.4. В графе каждая вершина имеет степень 3, а число ребер заключено между 16 и 20.

Сколько вершин в этом графе?


1.5. Найдите все абстрактные графы с 4 вершинами.
1.6. Найдите все абстрактные графы с набором степеней а) (2,2,2,3,3,4);

б) (2,2,2,3,3,3).


1.7. Восстановите граф по его

а) порожденным подграфам, полученным удалением одной вершины:



б) остовным подграфам, полученным удалением одного ребра:



1.8. Граф имеет множество вершин . Число ребер в подграфе, полученном

удалением вершины , равно , . Сколько ребер в графе ?

1.9. Граф имеет n вершин и m ребер. Сколько у него различных а) остовных;

б) порожденных подграфов?
1.10. 1) Представьте граф как объединение трех графов с множествами вершин

{1,2,3,4}, {1,2,5,6}, {3,4,5,6}.

2) Верно ли, что любой граф с 6 вершинами можно представить как объединение трех

графов с такими множествами вершин?

3) Верно ли, что любой граф с 6 вершинами можно представить как объединение трех

графов с множествами вершин {1,2,3}, {3,4,5}, {5,6,1}?


1.11. Верно ли, что для любых графов и выполняется равенство

?

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



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

несвязны.

1.14. Изоморфны ли графы 1) и ; 2) и ; 3) и ?


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

или соединением меньших графов.


1.16. Граф задан матрицей смежности:

.

Постройте для него матрицу расстояний между вершинами, найдите

эксцентриситеты вершин, диаметр, радиус, центр. Изоморфны ли этот граф и

дополнительный к нему?


1.17. Каково расстояние между вершинами (0,0,..., 0) и (1,1,...,1) в графе ? Сколько

имеется кратчайших путей между этими вершинами?


1.18. Какой наибольший диаметр может быть у графа с вершинами? Сколько имеется

(абстрактных) графов с таким диаметром?


1.19. Найдите все (с точностью до изоморфизма) графы с 5 вершинами диаметра 3.
1.20. Может ли радиус графа в результате добавления одного нового ребра а) увеличиться;

б) уменьшиться; в) остаться прежним?

1.21. Найдите все (с точностью до изоморфизма) графы с 5 вершинами радиуса 1.
1.22. Найдите все (с точностью до изоморфизма) графы с 4 вершинами, имеющие точно

одну центральную вершину.


1.23. Найдите диаметр и радиус графа .
1.24. Постройте граф пересечений а) граней трехмерного куба; б) ребер графа .
1.25. Сколько ребер в графе пересечений ребер графа ?
1.26. Граф пересечений семейства интервалов на прямой называют графом интервалов.

Какие из следующих графов являются графами интервалов: , , , , ,



, ?
1.27. Граф пересечений семейства дуг окружности называют графом дуг. Какие из

графов предыдущей задачи являются графами дуг?


1.28*. Докажите, что самодополнительный граф (граф, изоморфный своему дополнению)

с вершинами существует тогда и только тогда, когда или



.
1.29*. Докажите, что если в графе нет порожденного подграфа, изоморфного , то

каждая его компонента связности является полным подграфом.


1.30*. Докажите, что если в графе нет порожденного подграфа, изоморфного , то один

из графов , несвязен.




следующая страница >>