Теоретичні питання. ТЕОРІЯ ГРАФІВ.

⇐ ПредыдущаяСтр 3 из 4Следующая ⇒

Теоретичні питання

ТЕОРІЯ ГРАФІВ.

1. Неформальне означення графа.

2. Ізоморфізм графів.

3. Математичне означення графів.

4. Поняття суміжності вершин та ребер.

5. Побудова матриці суміжності для орієнтованого та неорієнтованого графів.

6. Який граф називається простим?

7. Означення степені вершини, яка вершина називається висячою, ізольованою?

8. Чому дорівнює сума степеней вершин для графа з m-ребер?

9. Чому дорівнює кількість вершин непарного степеня?

10. Означення під графа.

11. Означення суграфа.

12. Який граф називається доповненням до графу G?

13. Який граф називається доповненням до підграфу G’ в графі G?

14. Надайте означення орієнтованого графа, псевдографа, мультіграфа.

15. Маршрутом з вершини у вершину. називається ... . Довжиною маршруту називають … .

16. Означення ланцюгу, простого ланцюгу, простого шляху, простого циклу.

17. Означення відстані між вершинами.

18. Діаметр графа.

19. Який граф називається зв’язним?

20. Означення мосту графа.

21. Операціі над графами (9 шт.).

22. Означення повного графа.

23. Чому дорівнює кількість ребер у повному графі?

24. Дводольний та повний дводольний графи.

25. Напівстепень виходження та заходження.

26. Теорема о кількості вхідних та вихідних дуг.

27. Який орграф називається сильнозв’язним, мінімальнозв’язним?

28. Означення дерева, лісу, остову, кодерева.

29. Теорема про дерево.

30. Означення n-дерева, остового n-дерева.

31. Яка вершина називається коренем в орграфі?

32. Означення орієнтованого дерева, орієнтованого остову.

33. Який граф називається квазісильно-зв’язним?

34. Загальна постановка екстремальної задачі на графі.

35. Постановка задачі про найкоротше остове дерево.

36. Постановка задачі про найкоротший ланцюг.

37. Який ланцюг називається ейлеровим, відкритим ейлеровим?

38. Який граф називається ейлеровим?

39. Теорема про ейлеровий граф.

40. Що таке оріентований ейлерів цикл?

41. Означення орієнтованого ейлерового графа.

42. Постановка задачі комівояжера.

43. Що таке гамільтонів цикл?

44. Який граф називається гамільтоновим?

45. Який граф називається сіткою?

46. Що таке дівергенція функції у вершині ?

47. Дайте означення потоку в сітці.

48. Що таке розмір потоку?

49. Яка дуга називається насиченою?

50. Поток називається повним, якщо ... .

51. Який поток називається максимальним?

52. Що таке розріз в сітці D відносно множини вершин ?

53. Що таке пропускна здібність розрізу?

54. Теорема Форда-Фалкерсона про максимальний потік.

55. Означення паросполучення графа.

56. Яке паросполучення називається найбільшим, досконалим, оптимальним?

57. Постановка задачі про призначення.

58. Математична постановка задачі про призначення.

59. Яка вершина називається точкою зчленування?

60. Теорема про існування досконалого паросполучення.

61. Що таке розфарбування графу?

62. Який граф називається плоским, планарним?

63. Теорема Ейлера (о плоских графах)

64. Які графи непланарні (слідство з т. Ейлера)?

65. Теорема Понтрягіна-Куратовського о планарності графа.

Напишить алгоритм:

66. Прима знаходження найменьшого остову.

67. Краскала знаходження найменьшого остову.

68. Дійкстра знаходження найкоротшого ланцюга між парою вершин.

69. «Їди в найближчий» для розв’язання задачі комівояжера.

70. -розкладки планарного графа на площині.

71. Флері та елементарних циклів знаходження ейлерового ланцюга в ейлеровому графі.

72. Знаходження повного та найбільшого потоку.

⇐ Предыдущая 1 234 Следующая ⇒