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

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

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

deg v1=2

deg v2=4

deg v3=4

deg v4=2

deg v5=2

deg v6=2

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

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

V3 V4

V1 V5

V2 V6

Матрица смежности В ориентированного графа имеет вид:

Сравним полустепени захода и полустепени исхода всех вершин орграфа:

Г(х1)=Г ˉ¹(х1)=1

Г(х2)=Г ˉ¹(х2)=2

Г(х3)=Г ˉ¹(х3)=2

Г(х4)=Г ˉ¹(х4)=1

Г(х5)=Г ˉ¹(х5)=1

Г(х6)=Г ˉ¹(х6)=1

Поскольку полустепени захода и полустепени исхода всех вершин

орграфа равны, данный орграф является эйлеровым.

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

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

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

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

Фундаментальные циклы и разрезы графа

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

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

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

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

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

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

Остов графа

Остов – минимальное множество ребер, которые связывают все вершины связного графа.

Остов это дерево.

Подграф G' графа G называется остовом (каркасом, скелетом), если V = V’. Остов обычно обозначают буквой T.

Для орграфов остов – часть G, которая является остовом в неорграфе, полученном из G удалением ориентации дуг.

Остов получается из графа разрушением циклов.

Число удаляемых при этом ребер: V(G) = m – n + ρ – называется цикломатическим числом или цикломатическим рангом графа. ρ – количество компонент связности графа.

V*(G) = n – ρ – коциклический ранг – это количество ребер в остове графа.

Для дерева цикломатическое число равно 0.

Нахождение остова минимальной длины (веса)

Имеется граф G (V, E).

1. Строим начальный остов T_i , который состоит из всех вершин и одного ребра с минимальным весом.

2. Имеем T_i, среди всех ребер находим ребро с минимальным весом такое, которое смежно с одним из ребер из T_i и которое не образует циклов.

3. Добавляем его к T_i .

4. Повторяем п.2, пока находятся нужные ребра.

Фундаментальные циклы

Фундаментальным циклом графа G(V,E) с остовным деревом T(V,E') называется простой цикл, получаемый в результате добавления к T одного из ребер G, не принадлежащего E'. Количество фундаментальных циклов графа G = (V,E) при любом остовном дереве T равно цикломатическому числу V(G).

Пусть G(V, E) связный неорграф с n вершинами и m ребрами, T – остов графа, имеющий n – 1 ребро, которые называются ветвями T (ведь остов – это дерево) и обозначаются b_j. Не входящие в остов m – n + 1 ребер называют хордами и обозначают h_i.

Если к дереву T добавить произвольную хорду h_i, то образуется точно один цикл C_i. Этот цикл состоит из хорды h_i и некоторых ветвей остова, образующих простую цепь и соединяющих вершины хорды h_i.

Цикл C_i называется фундаментальным циклом графа G относительно хорды h_i остова T (в общем случае остовов в графе может быть много). Таким образом, фундаментальный цикл содержит точно одну хорду остова графа.

Множество всех фундаментальных циклов {C₁, C₂, …, C_i, …, C_m–n+1} относительно хорд остова T называется фундаментальным множеством циклов графа G. Мощность этого множества равна цикломатическому числу V(G) = m – n +1 или рангу графа G.

фундаментальное множество циклов графа можно задать с помощью матрицы, строки которой имеют вид

h₁, h₂, …, h_m–n+1, b₁, b₂, …, b_n–1,

где h_i, b_j – хорды и ветви соответственно.

В каждом цикле имеется одна хорда h_i и некоторое множество ветвей остова T. Этой хорде h_i и ветвям, входящим в цикл C_i, присвоим значение 1, остальным ребрам графа присвоим значение 0. Повторяя процедуру для всех хорд, получим матрицу строк из 0 и 1.

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

,

где 1, 2, 3 – хорды, 4, 5, 6, 7, 8 – ветви остова T, E – единичная матрица порядка V(G) = m – n + 1, B – матрица остова T.

Фундаментальные разрезы

Разрезом неорграфа G(V,E) по разбиению множества вершин V на два подмножества V₁ и V₂ называется множество ребер, соединяющих вершины из подмножества V₁ с вершинами подмножества V₂. В связном графе любой разрез не пуст.

Непустой разрез K неорграфа G называется простым или коциклом, если множество ребер K не содержит разрезов G ни по какому разбиению (любой разрез разбивает граф на две части – увеличивает число компонент связности).

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

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

Пусть имеем связный неорграф G с остовом T. И пусть b₁, b₂, …, b_i,…, b_n–1 – ветви остова T.

Удаляя произвольную ветвь b_i из T, получаем лес с двумя компонентами. Т. е. каждое ребро b_i есть разрез T по некоторому разбиению V₁, V₂.

В графе могут найтись еще какие–то ребра h_i1, h_i2,…h_ij, которые соединяют V₁ и V₂.

Множество ребер K_i = {b_i, h_i1, …, h_ij} образует разрез G относительно ветви b_i, который называют фундаментальным разрезом относительно b_i остова T. Таким образом, фундаментальный разрез содержит точно одну ветвь остова графа.

Множество {K₁, K₂, …, K_n–1} всех фундаментальных разрезов графа G называется фундаментальным множеством разрезов графа G относительно остова T.

Мощность этого множества равна V*(G) = n–1. (В общем случае n–

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

По аналогии с фундаментальными циклами, каждому фундаментальному разрезу можно поставить в соответствие вектор

(a_i1, a_i2, …, a_im),

где

Из этих векторов можно составить матрицу фундаментальных разрезов. Поскольку каждый фундаментальный разрез содержит точно одну ветвь T, то матрица K имеет вид

		hi,j – хорды			bi – ветви T
	K1	h1,1	.	h1,V*	1	0	0	.	0
K=	.	h2,1	.	h2,V*	0	1	0	.	0
	.	.	.	.	.	.	.	.	.
	KV*	hV*,1	.	hV*,V*	0	0	0	.	1

где V* это V*(G) = n – 1.

Таким образом ,

где H – матрица хорд графа, E – единичная матрица порядка V*(G) = n – 1.

Матрицы фундаментальных циклов C и фундаментальных разрезов K взаимосвязаны. Если

, то ,

где – транспонированная матрица B.

Следовательно, для анализа графа достаточно найти одну матрицу (C или K), а другую можно найти транспонированием.

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

.

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

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

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

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

Радиус и диаметр графа

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

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

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

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

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