Дискретная математика - файл

приобрести
скачать (357.1 kb.)


Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное


образовательное учреждение высшего образования

«Уфимский государственный авиационный технический университет»


Кафедра ВВТиС
Расчетно-графическая работа

по дисциплине

ДИСКРЕТНАЯ МАТЕМАТИКА

Вариант № 7


Выполнил: студ. гр. ИКТ-228

Диалло М.С.

Проверил: доц. каф. ВВТиС

Поречный С.С.

Уфа – 2021



Задание 1. Найти компоненты сильной связности орграфа



Решение

, где A(D) – матрица смежности, E – единичная матрица.















0

1

0

0



1

0

0

0



1

1

0

0



1

0

1

0














1

0

0

0



0

1

0

0



1

1

0

0



1

1

0

0

A(D) = аааа  =
















0

1

0

0



1

0

0

0



1

1

0

0



1

1

0

0




1

0

0

0

0

1

0

0

0

0

1

0

0

0

0

1


 = аааааааппE =

Тогда:
















1




1

0



1

1

0

0



1

1

1

0



1

0

1

1

T(D) =


, где  – транспонированная матрица T(D).















1

1

1

1



1

1

1

0



0

0

1

1



0

0

0

1














1

1

1

1



1

1

1

0



0

0

1

1



0

0

0

1

 = иииииии  =















1

1

1

1



1

1

1

0



0

0

1

1



0

0

0

1



p = 1,
 =

Присваиваем P=1   и составляем множество вершин первой компоненты сильной связности D1: это те вершины, которым соответствуют единицы в первой строке матрицы S(D). Таким образом, первая компонента сильной связности состоит из одной вершины  .



Вычеркиваем из матрицы S1(D) строку и столбец, соответствующие вершине V1, чтобы получить матрицу S2(D)













1

1

1



1

1

1



0

0

1
P=2 , S2(D)

S2(D)=



рисваиваем P=2. Множество вершин второй компоненты связности составят те вершины, которым соответствуют единицы в первой строке матрицы S2(D), то есть V1={V1,V2,V3} . Составляем матрицу смежности для компоненты сильной связности   исходного графа D − в ее качестве возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V1










1

1



1

1

A(D2) =



Таким образом, выделены сильной связности ориентированного графа D:

V1



V4


V3

V2

Задание 2. С помощью алгоритма фронта волны найти минимальный путь из вершины __ в __ в орграфе. Найти диаметр, радиус и центры с помощью матрицы минимальных расстояний.


Решение

Пусть A(D) – матрица смежности, тогда






















0

1

0

0

0

0

0



0

0

0

1

0

0

0



1

0

0

1

0

0

0



1

1

0

0

1

1

1



0

1

0

0

0

0

0



0

0

1

0

0

0

0



0

0

0

0

1

1

0



A(D) =
M(D) – матрица минимальных расстояний.




















0

1

4

3

3

3

3



2

0

3

1

2

2

2



1

2

0

1

2

2

2



1

1

2

0

2

1

1



3

1

4

2

0

3

3



2

3

1

2

3

0

3



3

2

2

3

1

1

0



M(D) =
d(D) – диаметр (наибольшее расстояние между вершинами), d(D) = 4;

r( ) = 4; r( ) = 3; r( ) = 2; r( ) = 2; r( ) = 4; r( ) = 3; r( ) = 3.

R – радиус (наименьший r( )), R = 2.

Центры – вершины, в которых r = R, то есть граф имеет центра: __2__.

Поиск минимального пути из V1 в V3.

(V0)

(V1)

W

(V2)

(V3)

(V7)

(V4)

Фронту волны первого уровня принадлежит V1 .По такому же принципу определяются вершины, входящие во фронт второго,V4. Из вершины V4 можно попасть только в V6, поэтому V6 принадлежит фронту волны V3=W уровня. ……



FW1(V1)={V2}r

FW2(V1)={V4}

.FW3(V1)={V6},



FW4(V1)={V3=W}

Соответственно, минимальный путь из V1 в V3: V1, V2, V4,V6,V3.


Задание 3. Найти минимальный путь в нагруженном орграфе из вершины V1 в V7 с помощью алгоритма Дейкстры


Решение





















∞

2

9

12

∞

∞

∞



∞

∞

∞

∞

∞

3

∞



4

∞

∞

4

∞

∞

∞



∞

3

∞

∞

5

4

4



∞

3

∞

∞

∞

∞

∞



∞

∞

2

∞

∞

∞

9



∞

∞

∞

∞

2

∞

∞
Пусть С(D) – матрица длин дуг исходного графа, тогда
С(D) =

Пусть С(D) – матрица длин дуг исходного графа, тогда
















∞

0

0

0

0

0

0



∞

2

2

2

2

2

2



∞

9

9

7

7

7

7



∞

12

12

12

11

11

11



∞

∞

17

17

17

16

16



∞

∞

5

5

5

5

5



∞

∞

16

14

14

14

14


найдем искомый путь за 3 шага минимальной длины из вершины V1 в V7: V1 V2 V6 V7 .

Задание 4. Найти Эйлерову цепь в графе

Решение

Для начала необходимо проверить граф на наличие Эйлеровой цепи. Для существования Эйлеровой цепи необходимо и достаточно, чтобы вершинами нечетные степени .В данном графе такими вершинами V1 и V4, значит, Эйлерова цепь существует.

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

:……...

После удаления вершин, задействованных в цикле , получаем граф в следующем виде:




: ……….

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



Остаются …. вершины, будет состоять из V1,V5,V4. После удаления оставшихся ребер, в графе не останется ни одного ребра. Склеиваем , , и получаем следующий цикл: …. Для получения Эйлеровой цепи необходимо из цикла удалить фиктивное ребро между двумя последними вершинами.


V4,V6,V7,V5,V2,V1,V4,V5,V8,V7,V2,V3,V5,V1.– искомая Эйлерова цепь.

Задание 5. Найти минимальное остовное дерево в нагруженном графе


Решение

Пусть С(G) – матрица длин ребер для данного графа.
















0

4

8

1

∞

∞

∞



4

0

∞

2

6

∞

9



8

∞

0

6

∞

5

∞



1

2

6

0

5

6

7



∞

6

∞

5

0

∞

4



∞

∞

5

6

∞

0

8



∞

9

∞

7

4

8

0


С(G) =
Находим в матрице минимальный элемент, это C14 Вычеркиваем V1 и V4 строки, и помечаем V1 и V4 столбцы, получаем:

Таким образом, . Длина дерева G2 будет равна l(G2) = c41 = 1. Поскольку , то продолжаем работу алгоритма.

……

Теперь по данным таблицы строим искомое минимальное остовное дерево.



l(G3) = l(G2)+ c24 = 1 + 2=3

l(G4) = l(G3)+ c45 = 3 + 5=8



l(G5) = l(G4)+ c46=8+6=14



l(G6) = l(G5)+ c63 = 14+5=19



l(G7) = l(G6)+ c75 = 19+4=23

Суммарный вес минимального остовного дерева равен 23.




V2
Таким образом, искомое минимальное остовное дерево графа G − граф G7, изображенный на рис., длина которого равна 23.


2

V1



5

4

5

6

1

V6

V4

V3

V7

V5


Задание 6. Решить задачу коммивояжера для нагруженного графа, заданного матрицей длин дуг


















∞

4

1

6

7

4



2

∞

7

8

5

4



3

9

∞

5

1

3



5

2

3

∞

6

6



9

2

3

4

∞

1



7

3

2

2

3

∞


С(D) =
Решение

Найдем константу привидения в каждой строке и выпишем ее в отдельный столбец min r.












min r



∞

4

1

6

7

4

1



2

∞

7

8

5

4

2



3

9

∞

5

1

3

1



5

2

3

∞

6

6

2



9

2

3

4

∞

1

1



7

3

2

2

2

∞

2

Из каждого элемента в строке вычитаем константу привидения, которая соответствует этой строке.












min r



∞

3

0

5

6

3

1



0

∞

5

6

3

2

2



2

8

∞

4

0

2

1



3

0

1

∞

4

4

2



8

1

2

3

∞

0

1



5

1

0

0

0

∞

2

Теперь необходимо выписать константу приведения каждого столбца в отдельную строку min c.












min r



∞

3

0

5

6

3

1



0

∞

5

6

3

2

2



2

8

∞

4

0

2

1



3

0

1

∞

4

4

2



8

1

2

3

∞

0

1



5

1

0

0

0

∞


Лекции
Лабораторные
Справочники
Эссе
Вопросы
Стандарты
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации