Федоров В.Н. - Введение в теорию графов, страница 4
Описание файла
Документ из архива "Федоров В.Н. - Введение в теорию графов", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 4 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "дискретная математика" в общих файлах.
Онлайн просмотр документа "Федоров В.Н. - Введение в теорию графов"
Текст 4 страницы из документа "Федоров В.Н. - Введение в теорию графов"
Рисунок 2.1
2.2. Векторная форма представления графов
2.2.1. Задание графа массивом преемников вершин
Матрица смежности отображается по строкам одномерным массивом FO, в котором для каждой вершины, начиная с первой, указываются вершины преемники. Списки преемников отдельных вершин разделяются символом Ø
2 | 5 | Ø | 1 | 3 | 6 | Ø | … |
Для неорграфа и мультиграфа массив имеет длину 2m+n, для орграфа m+n.
Если на вершинах и/или ребрах (дугах) заданы веса, то используются дополнительные массивы, в которых элементы содержат значения весов для вершин и/или ребер.
2.2.2. Задание графа массивом предшественников вершин
Здесь матрица смежности отображается по столбцам. Форма массива FI такая же, что и у FO.
Для неорграфов и мультиграфов FO и FI совпадают.
2.3. Контрольные вопросы
-
Какие формы представления графов вы знаете? Приведите примеры.
-
Какие матричные представления графов вы знаете?
-
Чем отличаются матричные представления неорграфа и орграфа?
-
В чем заключается достоинство и недостаток матрицы смежности?
-
Как задаются веса вершин и ребер (дуг) при матричной форме задания графа?
-
Какие векторные формы представления используются в теории графов? Как при такой форме можно задать веса вершин и ребер (дуг) графа?
-
Опишите алгоритмы перехода от одной формы представления графа к другой (от матрицы смежности к матрице инцидентности и обратно, от матричной формы к векторной форме и обратно).
3. Операции над графами
3
.1. Дополнение графа
Дополнение графа G(V,E) до полного графа
Обратите внимание на стрелки !!!
3.2. Объединение
G1 G2 = G(V1
V2, E1
E2) (рис. 3.2).
Обратите внимание – ребра е6 и е10 – это разные связи вершин 2 и 4 (разные дороги между населенными пунктами 2 и 4).
Р
исунок 3.2
Примечание.
В следующих двух операциях участвуют графы G1(V1,E1) и G2(V2,E2), показанные на рис. 3.2.
3.3. Пересечение
G1 G2 = G(V1
V2, E1
E2) (рис. 3.3)
3.4. Кольцевая сумма
G1 G2 = G(V = V1
V2, E = E1
E2 = E1\E2
E2\E1) (рис. 3.4).
Замечание. Операции 3.2 – 3.4 коммутативные бинарные операции, но могут быть расширены на большее число графов.
Р
исунок 3.3 Рисунок 3.4
3.5. Соединение
G
1 + G2 = G(V=V1 V2, E=E1
E2
) рис. 3.5.
3.6. Произведение
В произведении графов вершины обозначаются парами ab, где символы a и b – обозначения вершин в G1 и G2 соответственно.
П
ример (рис. 3.6). Ребро (1x,1y) E, так как первые символы совпадают (1 = 1), а в G2 есть ребро (x,y). Аналогично и для других ребер.
Рисунок 3.6
Неформально: Произведение G1 G2 означает, что каждая вершина G1 заменяется на копию Ga = G2, а каждая вершина G2 заменяется на копию Gb = G1.
3.7. Композиция
В композиции графов, как и в произведении графов, вершины обозначаются парами ab, где символы a и b – обозначения вершин в G1 и G2 соответственно.
Пример (рис. 3.7).
Н
еформально: Композиция G1[G2] означает, что каждая вершина G1 заменяется на копию Ga = G2, а затем, если (a1,a2) E1, то между любыми вершинами b1 из Ga1 и b2 из Ga2 проводится ребро (дуга) (b1,b2).
Рисунок 3.7
3.8. Разность
G1(V1,E1)\G2(V2,E2) = G(V1\V2, E),
где E = {[x1,x2]| x1,x2 V1\V2
[x1,x2]
E1
[x1,x2]
E2}
Задание. Приведите пример самостоятельно.
3.9. Удаление вершины
G(V,E)\{xi}.
Из графа удаляется вершина вместе с инцидентными ребрами.
В результате получается подграф, содержащий все ребра инцидентные множеству V\{xi}.
3.10. Удаление ребра
G\{ei}
Удаляется ребро, но при этом сохраняются концевые вершины, получается часть графа.
3.11. Добавление вершины
К заданному множеству вершин {х1, x2, ... , xk} добавляется новая вершина x, смежная с х1, x2, ... , xk.
G(V1,E1) + {x} = G(V1 {x}, E = E1
(x,xi), xi
V1), {x}
V1.
3.12. Добавление ребра
Для заданной пары вершин х, у добавляется ребро e.
G(V1, E1) + {e} = G(V1, E = E1 {e}), {e}
E1.
3.13. Стягивание подграфа A в вершину
В результате выполнения этой операции получается граф
E1 = E\{e = [x1,x2]| x1, x2 A}
{e = [x,u]| u
Г(A)\A}.
Г(А) – множество вершин, смежных с вершинами А.
3.14. Замыкание или отождествление вершин
В
ершины xi и xj отождествляются (рис. 3.8), т.е. они заменяются одной новой вершиной, при этом все ребра, инцидентные xi и xj, становятся инцидентны новой вершине.
Рисунок 3.8
3.15. Подразбиение ребра
Удаляется заданное ребро u=[х, у] и добавляется вершина z и цепь (x, u1, z, u2, у).
3.16. Контрольные вопросы
-
Что такое дополнение графа и как оно определяется? Приведите математическое представление и графический пример дополнения графа.
-
Как выполняются операции объединения и пересечения графов? Приведите примеры.
-
Приведите примеры определения результата выполнения кольцевой суммы и разности над графами.
-
Выполните операции 3.2 – 3.8 над двумя графами на двух вершинах, в одном из которых вершины соединены ребром, а в другом дугой. Для операций, у которых результат зависит от местоположения графа в формуле, приведите два варианта решения.
-
Поясните, как выполняется операция стягивания подмножества вершин в одну вершину.
-
Поясните, как выполняется подразбиение ребра.
4. Маршруты и циклы
Довольно часто на графах возникают такие задачи:
-
Есть ли в графе маршруты длины k?
-
Сколько маршрутов длины k имеется в графе?
-
Каковы эти маршруты?
Аналогичные задачи возникают и для циклов.
Рассмотрим решение этих задач.
4.1. Есть ли в графе маршруты длины k?
а) Составить матрицу смежности графа А.
б) Возвести А в степень k, используя бинарные операции, ,:
А1 А,
А2 А*А,
А3 А2*А, но не А*А2,
Аk = Аk–1 А , но не А Аk–1.
* – символ умножения.
в) Анализ элементов позволяет оценить наличие маршрутов длины k между вершинами i и j:
если = 1 , то маршруты длины k в графе имеются;
если = 0 , то маршрутов длины k между вершинами i и j нет.
4.2. Сколько маршрутов длины k имеется в графе?
а) составить А,
б) возвести А в степень k, используя правила обычного умножения матриц,
в) анализ элементов позволяет оценить количество маршрутов длины k:
= число – количество маршрутов длины k.
4.3. Какие маршруты длины k имеются в графе?
а) Присвоить всем ребрам и дугам графа имена в виде букв с индексами или без них.
Составить матрицу смежности графа А так, что если вершины i и j соединены ребром (дугой) с именем x, то элемент матрицы aij будет равен x.
б) возвести матрицу смежности А в степень k, производя умножение и сложение по правилам:
Сложение – a v b = b v a,
При этом c(a v b) = ca v cb ac v bc,
aa = 0 – так как ищем кратчайшие маршруты и повторение ребер (дуг) недопустимо,
aab = 0,
0b = 0.
в) анализ элементов позволяет определить маршруты длины k.
При решении таких задач для маршрутов – предельный показатель степени k = n – 1, так как ищем кратчайшие маршруты.
Для циклов задачи решаются аналогично, только здесь:
– предельный показатель степени k = n,
– наличие циклов определяется по значениям элементов .
Если требуется определить кратчайшие маршруты или циклы с началом в заданной вершине, то в степень следует возводить строку матрицы смежности этой вершины.
Пример: Дан граф (см. рис. 4.1).
Требуется ответить на вопрос: В графе есть маршрут (1,3)?
С
оставим матрицу смежности
В А1 элемент а1,3 = 0, следовательно, маршрута (1,3) длины 1 в графе нет.
Возводим А в степень 2 (умножение и сложение элементов булевские)
Элемент = 0. Маршрута (1,3) длины 2 в графе нет.
Возводим А в степень 3.
Элемент = 1, следовательно, маршрут (1,3) длины 3 в графе есть.
Сам маршрут находится так:
и маршрут будет таким 1–4–2–3 (читаем индексы).
Для получения всех кратчайших маршрутов воспользуемся методом, изложенным в п. 4.3.
Присвоим всем ребрам и дугам имена в виде букв (см. рис. 4.2) и составим матрицу смежности
Для получения всех кратчайших маршрутов длины k возведем A в k–ю степень, выполняя умножение и сложение по правилам п. 4.3.
анализ элементов позволяет определить маршруты длины k.
Маршруты здесь задаются последовательностью ребер и дуг.
Возводим матрицу смежности во вторую степень
Получили все маршруты длины 2.
Возводим матрицу смежности в третью степень (у графа число вершин n = 4, поэтому 3 – это предельный показатель степени, если ищем кратчайшие маршруты)
Элементы содержат маршруты длины 3.
4.4. Контрольные вопросы
-
Как определить – есть ли в графе маршруты длины k? Сколько таких маршрутов в графе? Какие они?
-
Как определить – есть ли в графе цикла длины k? Сколько таких циклов в графе? Какие они?
-
Как определить – есть ли в графе маршруты длины k с началом в заданной вершине? Сколько таких маршрутов в графе? Какие они?
-
Как определить – есть ли в графе циклы длины k с началом в заданной вершине? Сколько таких циклов в графе? Какие они?
-
Чем отличаются операции над графами п. 4.3 от аналогичных операций над логическими переменными и почему?
5. Кратчайший маршрут во взвешенном связном графе
Предварительное замечание.
Е
сли имеем орграф, то можно удалить вершины источники и стоки, не являющиеся началом и концом искомого маршрута, и так как кратчайший путь не проходит дважды ни через дугу, ни через вершину, то дуги, входящие в вершину начала пути и выходящие из конца пути, можно также исключить (см. рис. 5.1). После их исключения могут образоваться вершины источники, изолированные и тупиковые вершины, и даже компоненты связности, не содержащие вершин начала и конца маршрута. Их также следует исключить.
В неорграфе можно исключить висячие вершины.
Рисунок 5.1
5.1. Волновой алгоритм
Вариант 1:
Вес ребра – 1 (нет ребра – 0).
s – начало маршрута,