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

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

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

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

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

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

Так как вершина 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}.

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

Построим неориентированный граф 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 составить матрицу Кирхгофа и посчитать количество помеченных остовов.

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

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

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

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

 

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

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

1)

 

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

-1 ярус

 

-2 ярус

-3 ярус

-4 ярус

-5 ярус

Не изоморфные деревья 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.

| 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).

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

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

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

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

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

С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). Получим граф, все вершины которого будут иметь четную степень. Это является достаточным условием для того, чтобы граф стал эйлеровым.

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

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

С={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}.