Теория на графите Изпит – ки и кит, 11. 06. 2012



Дата30.11.2018
Размер51.5 Kb.
#106786
ТипЗадача
Теория на графите

Изпит – КИ и КИТ, 11.06.2012


Задача 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.

Напишете функция, която определя броя на върховете в най-голямата свързана компонента на даден неориентиран, непретеглен граф. Ако е необходимо, напишете помощни функции. Опишете какво представяне на графа използвате и защо.




Каталог: tadmin -> upload -> storage
storage -> Литература на факта. Аналитизъм. Интерпретативни стратегии. Въпроси и задачи
storage -> Лекция №2 Същност на цифровите изображения Въпрос. Основни положения от теория на сигналите
storage -> Лекция 5 система за вторична радиолокация
storage -> Толерантност и етничност в медийния дискурс
storage -> Ethnicity and tolerance in media discourse revisited Desislava St. Cheshmedzhieva-Stoycheva abstract
storage -> Тест №1 Отбележете невярното твърдение за подчертаните думи
storage -> Лекции по Въведение в статистиката
storage -> Търсене на живот във вселената увод
storage -> Еп. Константинови четения – 2010 г някои аспекти на концептуализация на богатството в руски и турски език


Сподели с приятели:




©obuch.info 2024
отнасят до администрацията

    Начална страница