Практикум по дискретной математике (стр. 4 )

2. Может ли матрица быть матрицей смежности неориентированного графа?

3. Какие из следующих утверждений являются правильными: а) если матрица смежности несимметричная, то граф ориентированный; б) если граф неориентированный, то матрица смежности симметричная; в) если диагональные элементы матрицы смежности – нули, то граф неориентированный?

4. Записать матрицы смежности и инцидентности для ориентированного графа (рис. 9в).

5. Изобразить все попарно неизоморфные ориентированные псевдографы, содержащие: а) 2 вершины и 2 дуги; б) 3 вершины и 4 дуги; в) 4 вершины и 3 дуги.

6. Изобразить ассоциированный граф для заданного графа (рис. 9в).

7. Чему равны степени вершин для ориентированного и неориентированного графов?

8. Определить степени вершин орграфа (рис. 3а). Есть ли в заданном графе изолированные и висячие вершины?

9. Определить степени вершин в заданных графах (рис. 9).

10. Даны реализации графов (рис. 9). Какие это графы? Привести примеры смежных вершин и смежных ребер.

Литература

1.  Новиков, математика для программистов: учебник для вузов / . – СПб.: Питер, 2001. – 304 с.

2.  Нефедов, дискретной математики: учеб. пособие / , . – М.: Изд-во МАИ, 1992. – 264 с.

3.  Акимов, математика. Логика, группы, графы. – 2-е изд., доп. / . – М.: Лаборатория базовых знаний, 2001. – 367 с.

6. Практическое занятие № 6

Тема: «Путь в графе. Поиск путей (маршрутов)»

Цель занятия:

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

Пояснение к работе

Время выполнения практического задания – 2 часа.

Последовательность выполнения

1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:

В чем состоит алгоритм поиска путей с минимальным числом дуг?

Какой цикл называется эйлеровым?

Каков критерий существования эйлерова цикла в графе?

Каков критерий существования эйлеровой цепи в графе?

2. Дать определение следующих понятий:

– маршрут в графе (привести пример);

– цепь и простая цепь в графе;

– цикл и простой цикл в графе;

– эйлеровой цепь;

– матрица смежности графа;

– степень вершины графа.

3. Выполнить задания для аудиторных занятий.

4. Выполнить задания для самостоятельной работы.

6.1. Маршруты, цепи, циклы

Маршрутом в графе G = (V, E) (путем в графе D = (V, E)) называется последовательность вершин и рёбер (дуг) вида v0, e1, v1, e2, ..., vn-1, en, vn, где vi Î V, i Î [0, n], ei Î E, (vi-1, ei), (vi, ei) Î I, i Î [1, n]. Вершины v0, vn называются связанными данным маршрутом (или просто связанными). Вершину v0 называют началом, а vn – концом маршрута. Если v0 = vn, то маршрут называют замкнутым. Число n называется длиной маршрута.

Маршрут, в котором все рёбра попарно различны, называется цепью. Замкнутый маршрут, являющийся цепью, называется циклом (контуром). Цепь, в которой все вершины попарно различны, называется простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.

Примеры: 1. Последовательность v1, e1, v2, e3, v4, e4, v3 – маршрут длины 3, соединяющий вершины v1, v3 в графе G (рис. 11); это простая цепь, так как все ребра и вершины попарно различны.

2. v2, e3, v2 – простой контур длины 1 в ориентированном псевдографе D (рис. 10).

3. v1, e2, v2, e4, v3 – путь из v1 в v3 длины 2 в ориентированном псевдографе D (рис. 10); это простая цепь, так как все дуги и вершины попарно различны.

Рис. 10 Рис. 11

6.2. Поиск путей (маршрутов) с минимальным числом дуг

При решении некоторых прикладных задач нередко возникает необходимость найти минимальный маршрут, соединяющий заданные вершины в графе. Приведем алгоритм решения этой задачи. Путь в орграфе D из вершины v в вершину w (v ¹ w) называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из вершины v в вершину w. Аналогично определяется минимальный маршрут в графе G. Алгоритм нахождения минимального маршрута состоит из следующих шагов:

Шаг 1. Помечаем вершину v индексом 0. Затем помечаем вершины, принадлежащие образу вершины v, индексом 1. Множество вершин с индексом 1 обозначаем FW1(v). Полагаем k = 1.

Шаг 2. Если FWk(v) = Æ или выполняется k = n – 1, w Ï FWk(v), то вершина w не достижима из v и работа алгоритма на этом заканчивается. В противном случае переходим к шагу 3.

Шаг 3. Если w Ï FWk(v), то переходим к шагу 4. В противном случае существует путь из v в w длины k, и этот путь является минимальным. Последовательность вершин

v w1w2 …wk-1w, где wk-1 Î FWk-1(v) Ç D-1(w); wk-2 Î FWk-2(v) Ç D-1(wл-1); … w1 Î FW1(v) Ç D-1(w2) и есть искомый минимальный путь из v в w. На этом работа алгоритма заканчивается.

Шаг 4. Помечаем индексом k + 1 все непомеченные вершины, которые принадлежат образу множества вершин с индексом k. Множество вершин с индексом k + 1 обозначаем FWk+1(v). Присваиваем k := k + 1 и переходим к шагу 2.

Пример. Используя предложенный алгоритм, определим минимальный путь из v1 в v6 в орграфе D, заданном матрицей смежности, представленной в табл. 1.

Таблица 1

	v1	v2	v3	v4	v5	v6
v1	0	0	0	1	1	0
v2	1	0	0	1	1	1
v3	1	1	0	1	1	1
v4	0	1	1	0	1	0
v5	1	1	1	1	0	0
v6	1	1	1	1	1	0

Действуя согласно алгоритму, последовательно определяем FW1(v1) = {v4, v5}; FW2(v1) = D(FW1(v1))\{v1, v4, v5} ={ v2, v3};

FW3(v1) = D(FW2(v1))\{v1, v2, v3, v4, v5 } = {v6}. Таким образом, v6Î FW3(v1), а значит (см. шаг 3) существует путь из v1 в v6 длины 3 и этот путь является минимальным. Найдем теперь минимальный путь из v1 в v6. Определим множество

FW2(v1) Ç D-1(v6) = {v2, v3} Ç {v2, v3} = {v2, v3}.

Выберем любую вершину из найденного множества, например вершину v3. Определим далее множество FW1(v1) Ç D-1(v3) = { v4, v5} Ç {v4, v5, v6 = {v4, v5}. Выберем любую вершину из найденного множества, например, вершину v5. Тогда v1 v5 v3 v6 – искомый минимальный путь из v1 в v6 длины 3 в орграфе D.

6.3. Эйлеровы графы

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

Рис. 12

Задача состоит в следующем: найти эйлеров цикл в мультиграфе G (рис. 12). Прежде чем решать задачу о выделении эйлеровой цепи или эйлерова цикла в псевдографе, надо выяснить, существуют ли они. Простейшее необходимое условие их существования, очевидно, заключается в связности G. Ответ на этот вопрос дают приводимые ниже теоремы. Эйлеровым называется цикл, проходящий по каждому ребру графа ровно один раз. Граф, имею-

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

Пусть по некоторой вершине v цикл проходит k раз. Но так как перед этой вершиной и после неё цикл должен проходить по инцидентным ей рёбрам, то количество рёбер, инцидентных данной вершине, по которым проходит цикл – 2 k. Так как цикл эйлеров – рёбер, по которым цикл не проходит, нет, значит 2 k – степень вершины v.

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

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

Задания

Для аудиторных занятий

1.  Задан граф G (рис. 13а). Найти путь с минимальным числом ребер из вершины v1 в вершину v6 графа G.

 

а б в

а б в

Рис. 13

2. Для графа G (рис. 13б) записать матрицу смежности и найти путь с минимальным числом ребер из вершины v2 в вершину v9.

3. Для орграфа D (рис. 13в) записать матрицу смежности и найти путь с минимальным числом ребер из вершины v1 в вершину v7.

4. Определить, содержит ли граф на рис. 13а эйлеров цикл или эйлерову цепь.

5. Может ли вершина, входящая в цикл графа, иметь степень, меньшую двух?

6. Как называется путь, у которого начало первой дуги совпадает с концом последней?

7. Как называется маршрут, у которого первая вершина совпадает с последней?

8. Показать, что в любом графе количество вершин нечетной степени четно.

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

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

Для самостоятельной работы

1. Задан граф G (рис. 13а). Найти путь с минимальным числом ребер из вершины v1 в вершину v7 графа G.

2. Для графа G (рис. 13б) записать матрицу смежности и найти путь с минимальным числом ребер из вершины v1 в вершину v8.

3. Для графа G (рис. 13б) записать матрицу инцидентности.

4. Для орграфа D (рис. 13в) записать матрицу смежности и найти путь с минимальным числом ребер из вершины v1 в вершину v6.

5. Показать, что любая вершина, входящая в цикл, не является висячей.

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

7. Доказать, что удаление из орграфа вершины v с d+(v) ≤ 1 (d-(v) ≤ 1) приводит к орграфу, контуры которого совпадают с контурами исходного орграфа.

8. Привести определение простой цепи:

а)  цепь, в которой вершины и ребра повторяются;

б)  чередование вершин и ребер;

в)  цепь, в которой все вершины попарно различны.

9. В чем заключается понятие смежности?

а)  сежными являются вершины, инцидентные одному ребру;

б)  смежными являются два ребра, не имеющие общих вершин;

в)  смежными являются вершины, соединенные некоторым маршрутом.

10. Задан псевдограф G. Цепь в G называется эйлеровой, если…

а)  она проходит по одному разу через каждую точку псевдографа;

б)  она проходит по одному разу через каждое ребро псевдографа;

в)  она проходит по одному разу через вершины и ребра.

Литература

1.  Новиков, математика для программистов: учебник для вузов / . – СПб.: Питер, 2001. – 304 с.

2.  Акимов, математика. Логика, группы, графы. – 2-е изд., доп. / . – М.: Лаборатория базовых знаний, 2001. – 367 с.

7. Практическое занятие № 7

Тема: «Связность, компоненты связности»

Цель занятия:

усвоение таких понятий, как связность, компоненты связности, односторонняя связность, сильная связность, матрица связности.

Пояснение к работе

Время выполнения практического задания – 2 часа.

Последовательность выполнения

1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:

Когда одна вершина достижима из другой?

Какой граф называется связным?

Какой граф называется сильно связным?

Какой граф называется односторонне связным?

Какой псевдограф называется ассоциированным с ориентированным псевдографом?

Какой граф называется слабо связным?

Что называется компонентой связности графа G (орграфа D)?

Что называется компонентой сильной связности графа G (орграфа D)?

Что понимают под операцией удаления вершины из графа (орграфа)?

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

2. Выполнить задания для аудиторных занятий.

3. Выполнить задания для самостоятельной работы.

7.1. Связность, компоненты связности

Говорят, что вершина w орграфа D (графа G) достижима из вершины v, если существует путь из v в w (маршрут, соединяющий v, w).

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

Псевдографом ассоциированным с ориентированным псевдографом D = (V, E), называется псевдограф G = (V, E0), в котором E0 получается из Е заменой всех упорядоченных пар (v, w) на неупорядоченные {v, w} (рис. 14).

а б Рис. 14: а – ориентированный псевдограф, б – ассоциированный с ним псевдограф

Орграф называется слабо связным, если связным является ассоциированный с ним псевдограф. Если граф (орграф) не является связным (слабо связным), то он называется несвязным.

Компонентой связности (сильной связности) графа G (орграфа D) называется его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (орграфа D).

Примеры: 1. У графа, изображенного на рис. 15, три компоненты связности.

2. У графа, изображенного на рис. 16, три компоненты сильной связности, показанные на рис. 17а, 17б.

а б

Рис. 15 Рис. 16 Рис. 17

3. На рис. 18 показаны диаграммы сильно, односторонне и слабо связных графов.

Рис. 18

Утверждение 1. Пусть G = (V, E) – псевдограф с p компонентами связности: G1 = (V1, E1), … , Gp = (Vp, Ep), тогда

1) V = V1È … È Vp, E = E1È … È Ep, то есть G = G1 È … È Gp;

2) Vi Ç Vj = Æ, Ei Ç Ej = Æ при i ¹ j.

Утверждение 2. Пусть D = (V, E) – ориентированный псевдограф с p компонентами сильной связности: D1 = (V1, E1), … , Dp = (Vp, Ep), тогда

1) V = V1È … È Vp, E = E1È … È Ep, то есть D = D1È … È Dp;

2) Vi ÇVj = Æ, Ei Ç Ej = Æ при i ¹ j.

Утверждение 3. Пусть r – отношение достижимости на множестве V вершин псевдографа G, то есть vrw тогда и только тогда, когда либо v = w, либо существует маршрут, соединяющий v, w, тогда:

1)  r – эквивалентность на V;

2)  vrw тогда и только тогда, когда вершины v, w принадлежат одной компоненте связности псевдографа G;

3)  для любого класса эквивалентности Vi Î V/r псевдограф Gi, порожденный множеством Vi, является компонентой связности псевдографа G;

4)  для любой компоненты связности псевдографа Gi = (Vi, Еi) псевдографа G выполняется Vi Î V/r.

Утверждение 4. Пусть r1 – отношение достижимости на множестве V вершин ориентированного псевдографа D, то есть vr1w тогда и только тогда, когда вершина w достижима из вершины v. Пусть r2 – отношение двусторонней достижимости на множестве V, то есть r2 = r1 ∩ r1-1, тогда:

1)  r1 рефлексивно, транзитивно;

2)  r2 – эквивалентность на V;

3)  vr2w только тогда, когда вершины v, w принадлежат одной компоненте сильной связности ориентированного псевдографа D;

4)  для любого класса эквивалентности Vi Î V/r2 ориентированный псевдограф Di, порожденный множеством Vi, является компонентой сильной связности ориентированного псевдографа D;

5)  для любой компоненты сильной связности Di = (Vi, Еi) ориентированного псевдографа D выполняется Vi Î V/r2.

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

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

7.2. Матрица связности

Пусть D = (V, E) – орграф, где V = { v1, …, vn}. Матрицей достижимости орграфа D называется квадратная матрица Т(D) = [ti, j] порядка n, у которой ti, j =1, если вершина vj достижима из vi и ti, j = 0 – в противном случае. Матрицей сильной связности орграфа D называется квадратная матрица S(D) = [si, j] порядка n, у которой si, j =1, если вершина vi достижима из vj и одновременно вершина vj достижима из vi и si, j = 0 – в противном случае, то есть si, j = 1 тогда и только тогда, когда вершины vi, vj принадлежат одной компоненте сильной связности орграфа D.

Пусть G = (V, E) – орграф, где V = { v1, …, vn}. Матрицей связности графа G называется квадратная матрица S(D) = [si, j] порядка n, у которой si, j = 1, если i = j или существует маршрут, соединяющий вершину vi, vj и si, j = 0 – в противном случае (то есть si, j = 1 тогда и только тогда, когда вершины vi , vj принадлежат одной компоненте связности орграфа G).

Задания

Для аудиторных занятий

1. Для графов, изображенных на рис. 4, записать последовательности, состоящие из вершин и ребер, являющиеся маршрутами длины 5, 4, 3 и 2 соответственно.

2. Для графов, изображенных на рис. 9а, 9б, 9в, записать последовательности, состоящие из вершин и ребер, являющиеся цепью, простой цепью.

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

4. Для орграфа D, представленного на рис. 19, записать матрицу достижимости и матрицу сильной связности.

 

Рис. 19 Рис. 20

5. Для графа G (рис. 20) записать матрицу связности.

6. Можно ли утверждать, что сильно связный граф всегда содержит контур?

7. Сколько компонент связности содержит граф G (рис. 20)?

8. Какие вершины графа (рис. 21) являются точками сочленения?

 

Рис. 21

9. Задано отношение достижимости r на множестве V. Какими свойствами обладает отношение r (рефлексивность, симметричность, транзитивность)?

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

Для самостоятельной работы

1. Сколько компонент связности содержит граф D (рис. 19)?

2. Какие вершины графа (рис. 20) являются точками сочленения?

3. Сколько компонент связности содержит граф G (рис. 21)?

4. Для графа G, изображенного на рис. 21, записать матрицу связности.

5. Какие из следующих графов являются полно связными (рис. 22)?

а) б) в)

Рис. 22

6. Сколько компонент связности у заданного графа?

7. Определить матрицы достижимости для орграфов с матрицами смежности.

8. Определить матрицы сильной связности для орграфов с матрицами смежности.

9. Сколько компонент связности у орграфов из заданий 7 и 8?

10. Какими свойствами обладают графы из заданий 7 и 8 (рефлексивность, симметричность, транзитивность)?