Федоров В.Н. - Введение в теорию графов, страница 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. Контрольные вопросы

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

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

3. Чем отличаются матричные представления неорграфа и орграфа?

4. В чем заключается достоинство и недостаток матрицы смежности?

5. Как задаются веса вершин и ребер (дуг) при матричной форме задания графа?

6. Какие векторные формы представления используются в теории графов? Как при такой форме можно задать веса вершин и ребер (дуг) графа?

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

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

3 .1. Дополнение графа

Дополнение графа G(V,E) до полного графа

(рис. 3.1).

Обратите внимание на стрелки !!!

3.2. Объединение

G₁ G₂ = G(V₁ V₂, E₁ E₂) (рис. 3.2).

Обратите внимание – ребра е₆ и е₁₀ – это разные связи вершин 2 и 4 (разные дороги между населенными пунктами 2 и 4).

Р
исунок 3.2

Примечание.

В следующих двух операциях участвуют графы G₁(V₁,E₁) и G₂(V₂,E₂), показанные на рис. 3.2.

3.3. Пересечение

G₁ G₂ = G(V₁ V₂, E₁ E₂) (рис. 3.3)

при условии

3.4. Кольцевая сумма

G₁ G₂ = G(V = V₁ V₂, E = E₁ E₂ = E₁\E₂ E₂\E₁) (рис. 3.4).

Замечание. Операции 3.2 – 3.4 коммутативные бинарные операции, но могут быть расширены на большее число графов.

Р
исунок 3.3 Рисунок 3.4

3.5. Соединение

G
₁ + G₂ = G(V=V₁ V₂, E=E₁ E₂ ) рис. 3.5.

3.6. Произведение

В произведении графов вершины обозначаются парами ab, где символы a и b – обозначения вершин в G₁ и G₂ соответственно.

П
ример (рис. 3.6). Ребро (1x,1y) E, так как первые символы совпадают (1 = 1), а в G₂ есть ребро (x,y). Аналогично и для других ребер.

Рисунок 3.6

Неформально: Произведение G₁ G₂ означает, что каждая вершина G₁ заменяется на копию Ga = G₂, а каждая вершина G₂ заменяется на копию Gb = G₁.

3.7. Композиция

В композиции графов, как и в произведении графов, вершины обозначаются парами ab, где символы a и b – обозначения вершин в G₁ и G₂ соответственно.

Пример (рис. 3.7).

Н
еформально: Композиция G₁[G₂] означает, что каждая вершина G₁ заменяется на копию Ga = G₂, а затем, если (a₁,a₂) E₁, то между любыми вершинами b₁ из Ga₁ и b₂ из Ga₂ проводится ребро (дуга) (b₁,b₂).

Рисунок 3.7

3.8. Разность

G₁(V₁,E₁)\G₂(V₂,E₂) = G(V₁\V₂, E),

где E = {[x¹,x²]| x¹,x² V₁\V₂ [x¹,x²] E₁ [x¹,x²] E₂}

Задание. Приведите пример самостоятельно.

3.9. Удаление вершины

G(V,E)\{x_i}.

Из графа удаляется вершина вместе с инцидентными ребрами.

В результате получается подграф, содержащий все ребра инцидентные множеству V\{x_i}.

3.10. Удаление ребра

G\{e_i}

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

3.11. Добавление вершины

К заданному множеству вершин {х₁, x₂, ... , x_k} добавляется новая вершина x, смежная с х₁, x₂, ... , x_k.

G(V₁,E₁) + {x} = G(V₁ {x}, E = E₁ (x,x_i), x_i V₁), {x} V₁.

3.12. Добавление ребра

Для заданной пары вершин х, у добавляется ребро e.

G(V₁, E₁) + {e} = G(V₁, E = E₁ {e}), {e} E₁.

3.13. Стягивание подграфа A в вершину

В результате выполнения этой операции получается граф

G(V₁, E₁) = G(V, E)/A, A V_,

V₁ = V\A {x},

E₁ = E\{e = [x₁,x₂]| x₁, x₂ A} {e = [x,u]| u Г(A)\A}.

Г(А) – множество вершин, смежных с вершинами А.

3.14. Замыкание или отождествление вершин

В
ершины x_i и x_j отождествляются (рис. 3.8), т.е. они заменяются одной новой вершиной, при этом все ребра, инцидентные x_i и x_j, становятся инцидентны новой вершине.

Рисунок 3.8

3.15. Подразбиение ребра

Удаляется заданное ребро u=[х, у] и добавляется вершина z и цепь (x, u₁, z, u₂, у).

3.16. Контрольные вопросы

1. Что такое дополнение графа и как оно определяется? Приведите математическое представление и графический пример дополнения графа.

2. Как выполняются операции объединения и пересечения графов? Приведите примеры.

3. Приведите примеры определения результата выполнения кольцевой суммы и разности над графами.

4. Выполните операции 3.2 – 3.8 над двумя графами на двух вершинах, в одном из которых вершины соединены ребром, а в другом дугой. Для операций, у которых результат зависит от местоположения графа в формуле, приведите два варианта решения.

5. Поясните, как выполняется операция стягивания подмножества вершин в одну вершину.

6. Поясните, как выполняется подразбиение ребра.

4. Маршруты и циклы

Довольно часто на графах возникают такие задачи:

1. Есть ли в графе маршруты длины k?

2. Сколько маршрутов длины k имеется в графе?

3. Каковы эти маршруты?

Аналогичные задачи возникают и для циклов.

Рассмотрим решение этих задач.

4.1. Есть ли в графе маршруты длины k?

а) Составить матрицу смежности графа А.

б) Возвести А в степень k, используя бинарные операции, ,:

А¹  А,

А²  А*А,

А³  А²*А, но не А*А²,

А^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, то элемент матрицы a_ij будет равен x.

б) возвести матрицу смежности А в степень k, производя умножение и сложение по правилам:

Умножение – a & b = ab ba,

Сложение – 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,3 = 0, следовательно, маршрута (1,3) длины 1 в графе нет.

Возводим А в степень 2 (умножение и сложение элементов булевские)

А² = * = .

Элемент = 0. Маршрута (1,3) длины 2 в графе нет.

Возводим А в степень 3.

А³ = A² * A = * = .

Элемент = 1, следовательно, маршрут (1,3) длины 3 в графе есть.

Сам маршрут находится так:

= а_2,3 .

Так как = а_1,4 а_4,2 , то

= а_1,4 а_4,2 а_2,3

и маршрут будет таким 1–4–2–3 (читаем индексы).

Для получения всех кратчайших маршрутов воспользуемся методом, изложенным в п. 4.3.

Присвоим всем ребрам и дугам имена в виде букв (см. рис. 4.2) и составим матрицу смежности

A = .

Для получения всех кратчайших маршрутов длины k возведем A в k–ю степень, выполняя умножение и сложение по правилам п. 4.3.

анализ элементов позволяет определить маршруты длины k.

Маршруты здесь задаются последовательностью ребер и дуг.

Возводим матрицу смежности во вторую степень

A² = * = .

Получили все маршруты длины 2.

Возводим матрицу смежности в третью степень (у графа число вершин n = 4, поэтому 3 – это предельный показатель степени, если ищем кратчайшие маршруты)

A³ = * = .

Элементы содержат маршруты длины 3.

4.4. Контрольные вопросы

1. Как определить – есть ли в графе маршруты длины k? Сколько таких маршрутов в графе? Какие они?

2. Как определить – есть ли в графе цикла длины k? Сколько таких циклов в графе? Какие они?

3. Как определить – есть ли в графе маршруты длины k с началом в заданной вершине? Сколько таких маршрутов в графе? Какие они?

4. Как определить – есть ли в графе циклы длины k с началом в заданной вершине? Сколько таких циклов в графе? Какие они?

5. Чем отличаются операции над графами п. 4.3 от аналогичных операций над логическими переменными и почему?

5. Кратчайший маршрут во взвешенном связном графе

Предварительное замечание.

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

В неорграфе можно исключить висячие вершины.

Рисунок 5.1

5.1. Волновой алгоритм

Вариант 1:

Вес ребра – 1 (нет ребра – 0).

s – начало маршрута,