Шептунов М. В.етодичка по лабораторным работам по дискретке (1023560), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

Краткие теоретические сведения

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

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

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

.

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

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

G ₁

G₂=G(X₁ X₂,E₁ E₂).

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

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

G₁ G₂=G(X₁ X₂,E₁ E₂)

при условии

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

G₁ G₂=G(X=X₁ X₂, E=E₁ E₂=E₁\E₂ E₂\E₁).

Замечание: Операции 2-4 коммутативные бинарные операции, но могут быть расширены на большее число графов.

5. Соединение

G₁ + G₂ = G(X=X₁ X₂, E=E₁ E₂ ) .

Задание 3: Составьте самостоятельно пример соединения графов G₁ и G₂.

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

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

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

Неформально: Произведение G₁ G₂ означает, что каждая вершина G₁

заменяется на копию Ga = G₂, а каждая вершина G₂ заменяется на копию Gb = G₁.

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

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

Пример:

Неформально: Композиция G₁[G₂] означает, что каждая вершина G₁

заменяется на копию Ga = G₂, а затем, если (a₁,a₂) E₁, то между любыми

вершинами b₁ из Ga₁ и b₂ из Ga₂ проводится ребро (дуга) (b₁,b₂).

8. Разность

G1\G2 = G(X1\X2, E),

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

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

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

G(X,E)\{x_i}.

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

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

G\{e_i}

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

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

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

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

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

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

G(X₁, E₁) = G(X, E)/A, A X_,

X₁ = X\A {x},

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

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

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

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

Содержание отчёта

1. Текст программы на C₊₊ либо Delphi (допускается в среде Visual Basic);

2. Результаты выполнения программы для заданного графа.

Лабораторная работа №7

Маршруты и циклы в графе

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

Содержание работы:

1. Разработка алгоритмов определения наличия в графе маршрутов и циклов заданной длины.

2. Разработка и отладка программы для определения наличия в графе маршрутов и циклов заданной длины.

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

Краткие теоретические сведения

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

1. Имеются ли в графе маршруты длины k с началом в заданной вершине (k – количество ребер (дуг))?

2. Имеются ли в графе циклы длины k с началом в заданной вершине?

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

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

5. Какие имеются маршруты длины k с началом в заданной вершине?

6. Какие имеются циклы длины k с началом в заданной вершине?

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

Общий подход к решению подобных задач таков:

Пусть необходимо ответить на следующие вопросы:

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

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

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

Решение:

Задача 1

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

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

А¹ А,

А² А*А,

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

А^k = А^k–1 А , но не А А^k–1.

• – символ умножения.

в) Анализ элементов а^k_ij позволяет оценить наличие маршрутов длины k между вершинами i и j:

если а^k_ij = 1 , то маршруты длины k в графе имеются;

если а^k_ij = 0 , то маршрутов длины k между вершинами i и j нет.

Задача 2

а) составить А,

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

в) анализ элементов а^k_ij позволяет оценить количество маршрутов длины k:

а^k_ij = число – количество маршрутов длины k.

Задача 3

а) Составить матрицу смежности, в которой каждое ребро имеет имя,

б) возвести А в степень k по правилам:

a b = аb,

а + b = а + b (или так а + b = а b),

aa = bb = cc = и т. д. = 0, так как везде ищем кратчайшие маршруты,

a0 = 0.

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

Для маршрутов - предельный показатель степени k = n – 1, так как ищем кратчайшие маршруты. Кратчайшие маршруты – в них каждая вершина повторяется не более одного раза.

Для циклов:

- Предельный показатель степени k = n,

- анализировать элементы а_ii^k .

П ример: Дан граф (см. рисунок).

Требуется ответить на вопрос: Есть маршрут (1,3)?

Составим матрицу смежности

А¹ = .

В А¹ элемент а_1,3 = 0. Маршрута (1,3) длины 1 нет.

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

А² = * = .

Замечание. Умножение как И, а сложение по ИЛИ.

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

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

А³ = * = .

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

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

а³_1,3 = а²_1,2 * а_2,3 .

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

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

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

Существует и такой метод получения всех кратчайших маршрутов:

П рисвоим всем ребрам и дугам имена, например, в виде букв с индексами или без них (см. рисунок.)

Составим матрицу смежности графа так, что если вершины i и j соединены ребром (дугой) с именем x, то элемент матрицы a_ij равен x.

Для графа примера имеем

A = .

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

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

Сложение – a v b,

При этом c(a v b) = ca v cb ac v bc,

aab = 0 – так как ищем кратчайшие маршруты и повторение ребер (дуг) недопустимо,

ab0 = 0.

A² = * = .

A³ = * = .

Содержание отчёта

1. Текст программы на C₊₊ либо Delphi (допускается в среде Visual Basic);

2. Результаты выполнения программы для заданного графа.

Лабораторная работа №8

Исследование графа на нахождение эйлерова цикла

Цель работы:

1. Разработка алгоритма проверки четности степеней вершин графа.

2. Разработка алгоритма проверки равенства полустепени захода и

полустепени исхода всех вершин орграфа.

Теоретические основы

Эйлеров граф – граф, который содержит Эйлеров цикл, включающий все ребра, каждое из которых проходится один раз.

Степенью вершины v называется число ребер, инцидентных этой вершине. Степень вершины v обозначается deg v.

(i,i)-элемент матрицы A² равен степени вершины vi.

Теорема 1.

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

В ориентированном графе множество номеров столбцов, для которых элемент i-ой строки равен 1, определяют множество Г (хi). Множество номеров строк, для которых элемент i-го столбца матрицы смежности равен 1,

определяют множество Г ˉ¹(хi).

Теорема 2.

Связный орграф содержит эйлеров контур тогда и только тогда, когда

хiХ Г(хi)=Г ˉ¹(хi), т.е. равны полустепени захода и полустепени исхода всех вершин орграфа.

Пример.

1. Дан неориентированный граф:

V3 V4

V1 V5

V2 V6

Построим матрицу смежности:

Построим матрицу A²:

Определим степени вершин данного графа:

Характеристики

Список файлов книги