Тема 6. Запитання по темі “Основи теорії графів”

Запитання по темі “Основи теорії графів”

1.     Що називається графом? З яких елементів він складається?

2.     Поясніть такі поняття: інцидентність, суміжність, петля, нуль-граф. Наведіть приклади.

3.     Які графи називаються повними, плоскими, просторовими? Наведіть приклади.

4.     Як визначається степінь вершини?

5.     Коли можна стверджувати, що існує шлях між двома заданими вершинами? Як визначається довжина шляху?

6.     Які вершини називаються зв'язними? Який граф називається зв'язним? Наведіть приклади.

7.     Який шлях називається циклом? Який цикл називається простим? Наведіть приклади.

8.     Який граф називається деревом, а який лісом? Наведіть приклади.

9.     Які графи називаються орієнтованими, зваженими? Наведіть приклади.

10.  Які графи називаються ейлеровими, гамільтоновими? Наведіть приклади.

11.  Які є способи представлення графів? Наведіть приклади різних графів та їх представлення. Порівняйте ці способи.

12.   Вміти реалізувати ці способи представлення графів.

13.  Який пошуковий метод називається пошуком у ширину в графі? Поясніть покроково роботу цього методу на конкретному прикладі.

14.   Які структури даних необхідно використати під час реалізації у вигляді програми алгоритму пошуку в ширину?

15.  Опишіть алгоритм пошуку в ширину у словесній формі.

16.  Чим відрізняється стратегія організації пошуку в глибину від по­шуку в ширину?

17.  Прокоментуйте роботу алгоритму пошуку в глибину в покроковому режимі виконання на конкретному прикладі.

18.  Якими є ознаки існування і відсутності шляху між двома верши­нами заданого графа в алгоритмі пошуку в глибину?

19.  Сформулюйте словесний алгоритм пошуку в глибину.

20.     Які структури даних потрібно використати для пошуку в глибину.

21.  Порівняйте два пошукових методи на графах, відзначивши пози­тивні і негативні сторони кожного з них.

22.  Які існують критерії наявності ейлерового шляху в заданому графі? Наведіть приклади ейлерових графів.

23.  Сформулюйте алгоритм пошуку ейлерового шляху в заданому графі і обґрунтуйте його основні моменти.

24.  Покроково виконайте алгоритм пошуку ейлерового шляху або циклу в графі на власному прикладі.

25.  Які структури даних необхідно використати для реалізації алго­ритму пошуку ейлерового шляху в заданому графі у вигляді Pascal-програми?

26.  Яким є алгоритм пошуку гамільтонового шляху в заданому графі?