- Гідрологія і Гідрометрія
- Господарське право
- Економіка будівництва
- Економіка природокористування
- Економічна теорія
- Земельне право
- Історія України
- Кримінально виконавче право
- Медична радіологія
- Методи аналізу
- Міжнародне приватне право
- Міжнародний маркетинг
- Основи екології
- Предмет Політологія
- Соціальне страхування
- Технічні засоби організації дорожнього руху
- Товарознавство продовольчих товарів
Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция
ТЕОРІЯ ГРАФІВ.
ІНДИВіДУАЛЬНі ЗАВДАННЯ
За ІV навчальний модуль з дисципліни
“ДИСКРЕТНА МАТЕМАТИКА”
для студентів факультету ІОТ
денної форми навчання
Теоретичні питання
ТЕОРІЯ ГРАФІВ.
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. Знаходження повного та найбільшого потоку.
Переглядів: 1596