A) построить кратчайшие маршруты от произвольной вершины ко всем остальным при помощи алгоритма Дейкстры;

b) построить кратчайшие маршруты при помощи алгоритма Флойда. При построении вести две матрицы – матрицу маршрутов и матрицу расстояний.

Построим кратчайшие маршруты от вершины 5 ко всем остальным с помощью алгоритма Дейкстры.

Матрица весов:

C
			¥		¥	¥	¥
						¥	¥
	¥			¥
			¥		¥
	¥			¥
	¥	¥
	¥	¥

1) l(5)=0; (1)=¥; (2)=¥; (3)=¥;

(4)=¥; (6)=¥; (7)=¥; p=5.

2) l(5)=0;

(1)=min( (1), l(5)+c(5,1))=min(¥, 0+¥)=¥;

(2)=min( (2), l(5)+c(5,2))=min(¥, 0+9)=9;

(3)=min( (3), l(5)+c(5,3))=min(¥, 0+12)=12;

(4)=min( (4), l(5)+c(5,4))=min(¥, 0+¥)=¥;

(6)=min( (6), l(5)+c(5,6))=min(¥, 0+2)=2;

(7)=min( (7), l(5)+c(5,7))=min(¥, 0+20)=20;

p=6.

3) l(6)=2; (1)=¥; (2)=9; (3)=12;

(4)=¥; (7)=20;

(1)=min( (1), l(6)+c(6,1))=min(¥, 2+¥)=¥;

(2)=min( (2), l(6)+c(6,2))=min(9, 2+¥)=9;

(3)=min( (3), l(6)+c(6,3))=min(12, 2+14)=12;

(4)=min( (4), l(6)+c(6,4))=min(¥, 2+9)=11;

(7)=min( (7), l(6)+c(6,7))=min(20, 2+18)=20;

p=2.

4) l(2)=9; (1)=¥; (3)=12; (4)=11;

(7)=20;

(1)=min( (1), l(2)+c(2,1))=min(¥, 9+10)=19;

(3)=min( (3), l(2)+c(2,3))=min(12, 9+21)=12;

(4)=min( (4), l(2)+c(2,4))=min(11, 9+16)=11;

(7)=min( (7), l(2)+c(2,7))=min(20, 9+¥)=20;

p=4.

5) l(4)=11; (1)=19; (3)=12; (7)=20;

(1)=min( (1), l(4)+c(4,1))=min(19, 11+26)=19;

(3)=min( (3), l(4)+c(4,3))=min(12, 11+¥)=12;

(7)=min( (7), l(4)+c(4,7))=min(20, 11+27)=20;

p=3.

6) l(3)=12; (1)=19; (7)=20;

(1)=min( (1), l(3)+c(3,1))=min(19, 12+¥)=19;

(7)=min( (7), l(3)+c(3,7))=min(20, 12+32)=20;

p=1.

7) l(1)=19; (7)=min( (7), l(1)+c(1,7))=min(20, 19+¥)=20; p=7.

Итак, кратчайшие маршруты:

M_5,1={5,2,1}=19;

M_5,2={5,2}=9;

M_5,3={5,3}=12;

M_5,4={5,6,4}=11;

M_5,6={5,6}=2;

M_5,7={5,7}={5,6,7}=20.

Построим кратчайшие маршруты при помощи алгоритма Флойда.

k=0

k=1

k=2

k=3

k=4

5) k=5

6) k=6

7) k=7

Итак, кратчайшие маршруты между всеми парами вершин:

M_1,2={1,2}; M_1,3={1,2,3}; M_1,4={1,4};

M_1,5={1,2,5}; M_1,6={1,2,5,6}; M_1,7={1,2,5,7};

M_2,3={2,3}; M_2,4={2,4}; M_2,5={2,5};

M_2,6={2,5,6}; M_2,7={2,5 ,7}; M_3,4={3,6,4};

M_3,5={3,5}; M_3,6={3,6}; M_3,7={3,7};

M_4,5={4,6,5}; M_4,6={4,6}; M_4,7={4,7};

M_5,6={5,6}; M_5,7={5,7}; M_6,7={6,7};

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

ЛАБОРАТОРНАЯ РАБОТА №3

Тема 1: «Деревья и остовы».

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

1. Используя алгоритм генерации варианта GV, построить неориентированный граф G1:GV(5,{2,3}) и граф G2: GV(13,{6,7}). Ребра графа G2 взвешены соответствующими элементами матрицы Y.

Построим граф G1, используя алгоритм генерации варианта GV(5,{2,3}).

S=<юфаеленаяковлевна>;

S=<ю,ф,а,е,л,н,я,к,о,в>;

n(S_i)={32,22,1,6,13}.

Y1

Матрица смежности

A1

Так как вершина 2 доминирующая, то ребро (2,3) удалено.

Построим неориентированный граф G1, используя способ перечисления.

G1=(V1,E1): V1={1,2,3,4,5} – множество вершин графа;

E1={(1,2),(1,4),(2,4),(2,5),(3,5)} – множество ребер графа.

Построим графическое изображение графа G1.

Построим граф G2, используя алгоритм генерации варианта GV(13,{6,7}).

S=<юфаеленаяковлевна>;

S=<ю,ф,а,е,л,н,я,к,о,в>;

n(S_i)={32,22,1,6,13,15,33,12,16,3,29,18,14}.

Y2

Матрица смежности

A2

Построим неориентированный граф G2, используя способ перечисления.

G2=(V2,E2):

V2={1,2,3,4,5,6,7,8,9,10,11,12,13} – множество вершин графа;

E2={(1,12),(1,13),(2,3),(2,6),(2,9),(2,11),(3,5),(3,6),(3,11),(4,5),

(4,8),(4,12),(6,7),(6,10),(6,11),(7,8),(7,10),(8,12)} – множество ребер графа.

Построим графическое изображение графа G2.

2. Для графа G1 составить матрицу Кирхгофа и посчитать количество помеченных остовов.

Матрица Кирхгофа

M
		-1		-1
	-1			-1	-1
					-1
	-1	-1
		-1	-1

Количество помеченных остовов k графа G равно алгебраическому дополнению любого элемента матрицы Кирхгофа.

Итак, в графе G1 содержится 3 помеченных остова:

3. Для графа G2 построить дерево обхода вершин графа в ширину и в глубину.

Построим остов графа G2.

Обход в глубину:

1)

Обход в ширину:

-1 ярус

-2 ярус

-3 ярус

-4 ярус

-5 ярус

Для графа G2 решить задачу построения остовов кратчайших маршрутов, используя алгоритмы Прима и Краскала (в качестве весов ребер использовать элементы матрицы Y).

Алгоритм Краскала

Ребра графа G упорядочиваются в порядке не убывания их весов. На каждом шаге к пустому графу O_p добавляется ребро с минимальным весом из списка ребер. Добавляемое ребро не должно приводить к образованию цикла. Алгоритм заканчивает работу, если количество ребер в графе станет равным p-1.

Матрица весов

С2

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

¥

Ребра	Вес
(2,9)1, (4,8)2, (8,12)3
(2,6)4, (2,11)5, (4,5)6
(3,5)7, (4,12), (6,10)8
(1,12)9, (3,6)10, (6,11)
(1,13)11, (6,7)12
(2,3), (7,8)
(3,11)
(7,10)

Хорды:

(4,12);

(6,11);

(2,3);

(7,8);

(3,11);

(7,10).

Алгоритм Прима

Алгоритм Прима отличается от алгоритма Краскала тем, что на каждом шаге строится не просто ацикличный граф, а дерево.

Ребра	Вес
(2,9)1, (4,8)8, (8,12)9
(2,6)2, (2,11)3, (4,5)7
(3,5)6, (4,12), (6,10)4
(1,12)10, (3,6)5, (6,11)
(1,13)11, (6,7)12
(2,3), (7,8)
(3,11)
(7,10)

Хорды:

(4,12);

(6,11);

(2,3);

(7,8);

(3,11);

(7,10).

4. Сгенерировать все различные абстрактные не изоморфные друг другу деревья порядка 4 и 7.

Не изоморфные деревья 4-го порядка:

Не изоморфные деревья 7-го порядка:

Разделить множество деревьев на 2 подмножества: с одной и с двумя центральными вершинами.

1) Деревья с одной центральной вершиной:

2) Деревья с двумя центральными вершинами:

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

Тема 2: «Циклы и обходы».

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

1. Используя алгоритм генерации варианта GV, построить неориентированный граф G1:GV(5,{2,3}) и граф G2: GV(13,{6,7}).

Построим граф G1, используя алгоритм генерации варианта GV(5,{2,3}).

S=<юфаеленаяковлевна>;

S=<ю,ф,а,е,л,н,я,к,о,в>;

n(S_i)={32,22,1,6,13}.

Y1

Матрица смежности

A1						deg(vi)

Построим неориентированный граф G1, используя способ перечисления.

G1=(V1,E1): V1={1,2,3,4,5} – множество вершин графа;

E1={(1,2),(1,4),(2,3),(2,4),(2,5),(3,5)} – множество ребер графа.

Построим графическое изображение графа G1.

G1,или

Построим граф G2, используя алгоритм генерации варианта GV(13,{6,7}).

S=<юфаеленаяковлевна>;

S=<ю,ф,а,е,л,н,я,к,о,в>;

n(S_i)={32,22,1,6,13,15,33,12,16,3,29,18,14}.

Y2

Матрица смежности

A2

deg(vi)

Построим неориентированный граф G2, используя способ перечисления.

G2=(V2,E2):

V2={1,2,3,4,5,6,7,8,9,10,11,12,13} – множество вершин графа;

E2={(1,12),(1,13),(2,3),(2,6),(2,9),(2,11),(3,5),(3,6),(3,11),(4,5),

(4,8),(4,12),(6,7),(6,10),(6,11),(7,8),(7,10),(8,12)} – множество ребер графа.

Построим графическое изображение графа G2.

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

| V | = p = 5, | E | = q = 6, k =1.

ν=q-p+k=6-5+1=2 – циклический ранг (хорды);

ν*=p-k=5-1=4 – коциклический ранг (ветви).

Выпишем все циклы в графе G1:

C1={1,2,4,1};

C2={2,5,3,2};

C3={2,1,4,2,5,3,2}.

Каждому циклу в графе G1 ставится в соответствие вектор длиной q.

Обозначим этот вектор: z=(z₁,z₂,z₃,…,z_q):

z₁=(1,1,0,1,0,0);

z₂=(0,0,1,0,1,1);

z₃=(1,1,1,1,1,1).

В графе G1 все имеется только один непростой цикл C3.

Выразим цикл С3 через базисные циклы С1 и С2:

С3=С1ÅС2=(1,1,0,1,0,0)Å(0,0,1,0,1,1)=(1,1,1,1,1,1).

Матрица фундаментальных циклов:

Т	(1,2)	(1,4)	(2,3)	(2,4)	(2,5)	(3,5)
C1
C2
C3

3. Определить, являются ли графы G1 и G2 эйлеровыми, построить эйлеровы циклы по алгоритму Флёри, эйлеровы цепи. Если граф не эйлеров, добавить минимальное число ребер, делающих его эйлеровым.

1)Рассмотрим граф G1: в нем все вершины имеют четную степень, следовательно, граф G1 имеет эйлеров цикл, то есть является эйлеровым графом.

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

V	(1,2)	(1,4)	(2,3)	(2,4)	(2,5)	(3,5)
№
№

Эйлеровы циклы:

С1={2,1,4,2,3,5,2};

C2={2,5,3,2,1,4,2}.

Построим в графе эйлеровы цепи. Для этого удалим ребро (2,3), тогда только две вершины – 2 и 3 – будут иметь нечетную степень, а это является необходимым и достаточным условием того, что граф G1 покрывается эйлеровой цепью.

Эйлеровы цепи:

P1={2,1,4,2,5,3};

P2={3,5,2,4,1,2}.

2) Рассмотрим граф G2: так как в нем вершины 4, 6, 7, 8, 10, 11, 12, 13 имеют нечетную степень, то граф G2 не имеет эйлерова цикла и, следовательно, не является эйлеровым графом.

Добавим ребра (6,9), (6,12),.(6,8), (4,7), (11,13). Получим граф, все вершины которого будут иметь четную степень. Это является достаточным условием для того, чтобы граф стал эйлеровым.

Построим в графе эйлеров цикл с помощью алгоритма Флери.

V	(1,12)	(1,13)	(2,3)	(2,6)	(2,9)	(2,11)	(3,5)	(3,6)
№
V	(3,11)	(4,5)	(4,7)	(4,8)	(4,12)	(6,7)	(6,8)	(6,9)
№
V	(6,11)	(6,12)	(7,8)	(7,10)	(8,12)	(11,13)	(6,10)
№

Эйлеров цикл:

С={2,9,6,11,2,3,11,13,1,12,4,5,3,6,12,8,4,7,6,10,7,8,6,2}.

Построим в графе эйлерову цепь. Добавим ребра (1,6), (3,2), тогда только две вершины – 7 и 13 – будут иметь нечетную степень, а это является необходимым и достаточным условием того, чтобы граф G2 покрывался эйлеровой цепью.

Эйлерова цепь:

P2={13,1,12,11,2,9,7,8,12,4,3,11,6,7,10,6,8,4,6,2,3,6}.

Определить, является ли граф G2 гамильтоновым, построить гамильтонов цикл, используя алгоритм Робертса-Флореса. Если граф не является гамильтоновым, добавить минимальное число ребер, делающих его гамильтоновым.

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

Добавив ребро (9,13), можно выделить гамильтонов цикл:

C_g = {9,2,3,11,6,10,7,8,4,5,12,1,13,9}.

Следовательно, полученный граф - гамильтонов.