Задача 1.
Разглеждаме граф, върховете, на който съответстват на числата от 1 до 9: Ребро от връх x към връх y съществува ако x + y е точен квадрат.
За този граф напишете представянето му като списък на съседи. Определете дали така дефинирания граф е ориентиран.
Задача 2.
Следващият програмен фрагмент реализира алгоритъмът на Флойд за намиране на най-кратките пътища между всяка двойка върхове в зададен граф. Матрицата М съвпада с матрицата на съседство, но липсата на ребро между два върха в нея се отбелязва с безкрайност. Добавете в програмния фрагмент оператори, с помощта на които ще намираме и броя на ребрата, съставящи най-кратките пътища.
int i, j, k, **M;
.......................
for (k=0;k
for (i=0;i
for (j=0;j
if (M[i][k]+M[k][j]
Задача 3.
Напишете функция, която прочита от клавиатурата ориентиран граф, представен като списък от съседи и го представя в паметта като списък от ребра. Опишете използваната за представянето структура.
Задача 4.
Зададен е ориентиран граф с 10 върха и 14 ребра по следния начин:
10 14
1 0
1 3
2 0
2 5
3 0
3 2
3 5
4 1
4 3
4 5
4 6
4 7
6 5
7 6
-
Постройте матрица на съседство на този граф.
-
Пресметнете входните и изходните степени на всеки връх.
-
Напишете реда на обхождане на графа в дълбочина с начало връх 3.
Задача 5.
Зададен е нериентиран граф посредством матрица на съседство:
-
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
1
|
0
|
9
|
10
|
1
|
0
|
0
|
0
|
0
|
2
|
9
|
0
|
5
|
0
|
0
|
18
|
0
|
0
|
3
|
10
|
5
|
0
|
16
|
0
|
2
|
0
|
0
|
4
|
0
|
0
|
16
|
0
|
14
|
0
|
0
|
21
|
5
|
0
|
0
|
17
|
14
|
0
|
0
|
1
|
13
|
6
|
1
|
18
|
2
|
0
|
0
|
0
|
20
|
0
|
7
|
0
|
0
|
10
|
0
|
1
|
20
|
0
|
11
|
8
|
0
|
0
|
0
|
21
|
13
|
0
|
11
|
0
|
-
За него намерете едно минимално покриващо дърво.
-
Обяснете използвания алгоритъм.
-
Колко ребра включва минималното покриващо дърво?
-
Защо, ако графът има за всяко ребро тегло със стойност, различна от стойностите на теглата на останалите ребра, минималното покриващо дърво е единствено.
Задача 6.
Напишете функция, която определя броя на върховете в най-голямата свързана компонента на даден неориентиран, непретеглен граф. Ако е необходимо, напишете помощни функции. Опишете какво представяне на графа използвате и защо.