ДМ_МУ_САМ РАБ

тема 7 «Задача комівояжера»;

тема 8 «Дерева»;

тема 9 «Розфарбування графів»;

тема 10 «Двудольні та k-дольні графи»;

тема 11 «Транспортні мережі та течії. Їх властивості. Найкоротші відстані та шляхи у мережах.»;

тема 12 «Алгоритми Флойда і Данцига пошуку найкоротших шляхів між всіма парами вершин графа»;

тема 13 «Течії у мережах».

4.8.2 Тема 1 «Зародження теорії графів як математичної дисципліни»

Вивчення теми 1 «Зародження теорії графів як математичної дисципліни» пов’язане із розглядом таких питань [1, 4, 14, 20, 22]: постановка задачі про кенігсберські мости та її розв’язання; вивчення Кірхгофом електричних ланцюгів та розробка алгоритму знаходження максимального підграфу без циклів (дерева); формулювання задачі комівояжера В. Гамільтоном на прикладі графа додекаедру; задача про три хати та три колодці; проблема чотирьох фарб.

4.8.3 Контрольні запитання

1.З роботою якого вченого прийнято пов’язувати зародження теорії графів як математичної дисципліни?

2.Проілюструйте задачу про кенігсберські мости.

3.Поясніть задачу про три хати та три колодці. Надайте ілюстрацію цієї

задачі.

4.Яка комбінаторно-топологічна структура називається графом ланцюга?

Який вчений і коли проводив аналіз цієї структури?

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

6.Поясніть сутність проблеми чотирьох фарб.

7.Яку задачу сформулював В. Гамільтоном на прикладі графа додекаедру?

51

4.8.4 Тема 2 «Походження графів. Визначення графів»

Вивчення теми 2 «Походження графів. Визначення графів» пов’язане із розглядом таких питань [1-5, 7, 9-11, 13-16, 19-23]: основне визначення графа, елементи графа; неорієнтовані графи і термінологія; орієнтовані графи і термінологія; абстрактні графи та геометричні реалізації; зв’язок графів з відношеннями; «лема про рукостискання»; способи задання графів; матриці суміжності та інциденцій графа.

Основними поняттями і визначеннями теми «Походження графів.

Визначення графів», які надаються в [1-5, 7, 9-10, 14-16, 19-20, 22], є: граф; елементи графа; вершина графа; ребро графа; порядок графа; розмір графа;

порядок графа; неорієнтований граф; орієнтований граф; геометричний граф; суміжні вершини; суміжні ребра; інциденті вершина і ребро; ізольована вершина; петля; паралельні (кратні) ребра; маршрут; довжина маршруту; замкнений маршрут; ланцюг; простий ланцюг; цикл; дуга; орієнтований маршрут; шлях; контур; абстрактний граф; зв’язний граф; сильно зв’язний граф; скінченний граф; підграф; компонента зв’язності; степінь вершини;

додатний степінь вершини; від’ємний степінь вершини; півстепені «виходу і заходу»; порожній граф; простий граф; повний граф; регулярний (однорідний)

граф; суграф; дерево; мультиграф; псевдограф; доповнення простого графа; матриця суміжності графа; матриця інциденцій графа.

4.8.5 Контрольні запитання

1.Надайте визначення графа.

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

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

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

5.Дайте визначення повного графа. Приведіть приклади.

6.Які вершини є суміжними в графі?

7.Які вершини й ребра інцидентні в графі. Приведіть приклади.

8.Дайте визначення абстрактного орієнтованого графа.

9.Перелічить способи задання графів.

10.Як можна побудувати матрицю суміжності графа? Приведіть приклад.

11.Що таке матриця інциденцій графа? Приведіть приклад матриці інциденцій для неорієнтованого та орієнтованого графа.

12.Поясніть геометричний спосіб задання графа.

52

13.Чому дорівнює для орієнтованого графа сума «виходу і заходу»?

14.Поясніть поняття маршруту в графі.

15.Дайте визначення шляху в графі.

16.Дайте визначення циклу в графі.

17.Прокоментуйте використання «леми про рукостискання».

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

19.Як визначити степінь вершини графа?

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

4.8.6 Тема 3 «Операції над графами»

Вивчення теми 3 «Операції над графами» пов’язане із розглядом таких питань [1-5, 7, 9-11, 13-16, 19-23]: операції вилучення вершин і ребер; операції введення вершини в ребро і операції введення ребра в граф; теоретикомножинні операції над графами.; властивості операцій об’єднання і перетину графів.

Основними поняттями і визначеннями теми «Операції над графами», які надаються в [1-5, 7, 9-10, 14-16, 19-20, 22], є: вилучення вершини; вилучення ребра; введення вершини в ребро; введення ребра в граф; доповнення графа;

об’єднання (сума) графів; диз’юнктивне об’єднання (сума) графів; перетин (добуток) графів; з’єднання (сильний добуток) графів; композиція графів;

декартів добуток графів.

4.8.7 Контрольні запитання

1.Перелічить групи операцій, які виконуються над графами.

2.Надайте характеристику та приклад виконання операції вилучення ребер графа.

3.Надайте характеристику та приклад виконання операції вилучення вершини графа.

4.Який граф називається доповненням графа G (V,X1)?

5.У якій формі може бути виконана операція об’єднання (сума) графів?

6.Що являє собою операція перетин графів і які властивості вона має?

7.Як визначити композицію G1(G2 ) графів G1 и G2 . Наведіть приклад.

5. Дайте характеристику операції з’єднання графів.

4.8.8 Тема 4 «Ізоморфізм графів. Плоскі та планарні графи»

53

Вивчення теми 4 «Ізоморфізм графів. Плоскі та планарні графи» пов’язане із розглядом таких питань [1-5, 7, 9-11, 13-16, 19-23]: ізоморфізм графів (поняття еквівалентності графів); автоморфізм графа; гомеоморфні графи; приклади ізоморфних графів; геометрична реалізація графа у просторі

Rn ; алгоритмічна складність перевірки ізоморфізма графів; поняття плоского і планарного графа; топологічний критерій планарності графа; теорема Понтрягіна-Куратовського; теорема Жордана; побудова плоского зображення графа (плоске укладання графа); використання гамма-алгоритма для плоского укладання графа та перевірки його планарності.

Основними поняттями і визначеннями теми «Ізоморфізм графів. Плоскі та планарні графи», які надаються в [1-5, 7, 9-10, 14-16, 19-20, 22], є: ізоморфізм графів; автоморфізм графа; гомеоморфізм графів; плоский граф; планарний граф; топологічний критерій планарності графа; жорданова крива; гаммаалгоритм.

4.8.9 Контрольні запитання

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

2.Які графи називаються ізоморфними графами?

3.Поясніть зв’язок понять «ізоморфізм графів» і «відношення еквівалентності».

4.Наведіть приклади ізоморфних графів.

5.Поясніть використання теореми Понтрягіна-Куратовського для визначення ізоморфізму графів.

6.Дайте визначення плоского графа, планарного графа.

7.Для розв’язання яких задач використовується теорема Жордана?

8.Для плоского укладання графа і перевірки його планарності можна використати гамма-алгоритм?

9.Наведіть гамма-алгоритм в загальному вигляді.

4.8.10 Тема 5 «Зв'язність графів. Ейлерові та гамільтонові графи»

Вивчення теми 5 «Зв'язність графів. Ейлерові та гамільтонові графи» пов’язане із розглядом таких питань [1-5, 7, 9-11, 13-16, 19-23]: поняття зв'язності графів, властивості зв'язних графів; метричні характеристики зв'язних

54

графів; ейлереві графи; теорема Ейлера про наявність ейлерева циклу; алгоритм знаходження ейлерева циклу (теорема Флері); гамільтонові графи; ознаки існування гамільтонових циклів, шляхів і контурів.

Основними поняттями і визначеннями теми «Зв'язність графів. Ейлерові та гамільтонові графи», які надаються в [1-5, 7, 9-10, 14-16, 19-20, 22], є:

зв'язний граф; незв'язний граф; компонента зв'язності; n-зв'язний граф; степінь зв'язності графа; число вершинної зв'язності; число реберної зв'язності; точка зчленування графа; відстань між вершинами графа; діаметр графа; ексцентриситет вершини; радіус графа; центральна вершина графа; центр графа; грань (комірка) геометричного графа; необмежена грань (зовнішня грань); внутрішня грань; границя грані; ейлерів ланцюг; ейлерів цикл; ейлерів граф; гамільтонів шлях (гамільтонів ланцюг); гамільтонів граф.

4.8.11 Контрольні запитання

1.Дайте визначення зв'язного і незв'язного графів.

2.Що являє собою компонента зв'язності графа? Наведіть приклади компонент зв'язності.

3.Що називається степенем зв'язності графа?

4.Перелічить властивості зв'язних графів.

5.Наведіть приклади метричних характеристик зв'язних графів.

6.Якщо граф зв'язний і n – число його вершин, то яка нижня оцінка для числа його ребер?

7.Дайте визначення ейлерева циклу (ейлерева ланцюга, замкненого ейлерева ланцюга).

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

9.Для розв’язання яких практичних задач використовується теорема

Ейлера?

10.Поясніть використання алгоритму знаходження ейлерева циклу

(теорема Флері).

11. Надайте визначення гамільтонова шляху (гамільтонова ланцюга),

гамільтонова циклу.

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

13.Надайте характеристику алгоритма Робертса-Флореса. Для яких цілей він використовується?

14.Назвіть основні ознаки існування гамільтонових циклів, шляхів і

контурів.

55

15. Охарактеризуйте теорему (умову Дирака) для визначення гамільтонова графа.

4.8.12 Тема 6 «Цикломатика графів»

Вивчення теми 6 «Цикломатика графів» пов’язане із розглядом таких питань [1-5, 7, 9-11, 13-16, 19-23]: цикломатичне число та його властивості;

цикломатична матриця; базис циклів; алгоритм побудови базису циклів; фундаментальна система циклів і перерізів; алгоритм побудови фундаментальної системи циклів.

Основними поняттями і визначеннями теми «Цикломатика графів», які надаються в [1-5, 7, 9-10, 14-16, 19-20, 22], є: каркас (остов) графа;

цикломатичне число графа; цикломатичне число остова графа; цикломатична матриця; простір циклів графа; базис циклів; переріз (розріз) графа; кодерево; фундаментальний переріз; фундаментальний цикл графа; фундаментальна матриця циклу.

4.8.13 Контрольні запитання

1.Дайте визначення маршруту, шляху, ланцюга, циклу в графі. Наведіть практичні приклади цих визначень.

2.Дайте визначення цикломатичного числа. Охарактеризуйте його властивості.

3.Як задається цикломатична матриця графа?

4.Чому дорівнює цикломатичне число остова графа?

5.Що являє собою простір циклів графа?

6.Поясніть використання фундаментальна система циклів і перерізів.

7.Наведіть алгоритм побудови фундаментальної системи циклів.

4.8.14 Тема 7 «Задача комівояжера»

Вивчення теми 7 «Задача комівояжера» пов’язане із розглядом таких питань [1, 14, 20, 22]: визначення гамільтонова циклу, гамільтонова графа,

гамільтонова шляху, гамільтонова ланцюга; загальна постановка задачі комівояжера; додаткові обмеження використання задачі комівояжера; «гамільтонова» задача комівояжера; існування розв’язку задачі комівояжера; задача пошуку загального орієнтованого маршруту комівояжера; практичні

56

методи і алгоритми розв’язання задачі комівояжера; обчислювальна складність задачі комівояжера; алгебраїчний алгоритм Йоу, Даніельсона, Дхавана; приклади практичних задач, що зводяться до задачі комівояжера.

Основними поняттями і визначеннями теми «Задача комівояжера», які надаються в [1, 14, 20, 22], є: зважений граф; гамільтонів цикл, гамільтонів граф, гамільтонів шлях, гамільтонів ланцюг; орієнтований шлях комівояжера; орієнтований контур комівояжера.

4.8.15 Контрольні запитання

1.Надайте постановку загальної задачі комівояжера.

2.Сформулюйте загальну задачу комівояжера на мові графів.

3.Надайте постановку «гамільтонової» задачі комівояжера.

4.Надайте постановку задачі пошуку загального орієнтованого маршруту комівояжера.

5.Показати, що множина оптимальних розв’язків задачі комівояжера не залежить від того, яка з вершин обирається як почваткова при обході.

6.Проаналізуйте класи алгоритмів розв’язання задачі комівояжера.

7.Поясніть використання алгебраїчного алгоритму Йоу, Даніельсона,

Дхавана для розв’язання задачі комівояжера.

4.8.16 Тема 8 «Дерева»

Вивчення теми 8 «Дерева» пов’язане із розглядом таких питань [1-5, 7, 9- 11, 13-16, 19-23]: визначення дерева; властивості дерев; перелічення графів і дерев (неізоморфних, кореневих, позначених); використання формули А. Келі для підрахування числа позначених дерев з n вершинами; остови графа;

перелічення остовів для повного (простого) графа; перелічення остовів графа у загальному випадку (теорема Кірхгофа); алгоритм побудови остовного дерева

(пошук у глибину); алгоритм побудови остовного дерева шляхом довільного перегляду ребер; алгоритми побудови остова мінімальної ваги (алгоритм Дж.

Краскала, алгоритм Р. Прима); орієнтовані та бінарні дерева; правила обходу бінарних дерев; правило побудови бінарного дерева з будь-якого дерева.

Основними поняттями і визначеннями теми «Дерева», які надаються в [1- 5, 7, 9-10, 14-16, 19-20, 22], є: дерево; центр дерева; ліс; позначений граф;

однакові позначені графи; кількість неорієнтованих, простих, позначених графів; число неізоморфних (простих, неорієнтованих) графів без позначок;

57

число позначених дерев; число звичайних (неізоморфних) дерев з n

вершинами; корінь дерева; кореневе дерево; остовний підграф (остов, каркас графа); матриця Кірхгофа простого графа; зважений граф; остів мінімальної ваги; вага під графа; орієнтоване дерево; нащадок вершини; предок вершини; «батько» для вершини; «син» для вершини; лист; глибина вершини; висота вершини; висота дерева; рівень вершини; упорядковане дерево; бінарне (двійкове) дерево; ліве піддерево; праве піддерево; еквівалентне бінарне дерево.

4.8.17 Контрольні запитання

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

2.Що називається лісом у теорії графів?

3.Перелічить основні властивості дерев.

4.Якою формулою можна скористатися для визначення кількості неорієнтованих позначених простих графів з n вершинами і m ребрами?

5.Якою формулою можна скористатися для визначення кількості не ізоморфних позначених дерев?

6.Як визначити число неізоморфних графів без позначок?

7.У яких випадках використовується формула А. Кэли? Наведіть цю формулу.

8.Дайте визначення остова (каркаса) графа.

9.Приведіть приклад складання матриці Кірхгофа простого графа.

10.Для розв’язання яких задач використовується теорема Кірхгофа?

11.Перелічить основні алгоритми побудови остовів графа.

12.Наведіть алгоритм Дж. Краскала для побудови остова мінімальної

ваги.

13.Дайте визначення орієнтованих і бінарних дерев.

14.Охарактеризуйте способи обходу бінарного дерева.

15.Поясніть правило побудови бінарного дерева з будь-якого дерева.

4.8.18Тема 9 «Розфарбування графів»

Вивчення теми 9 «Розфарбування графів» пов’язане із розглядом таких питань [1-5, 7, 9-11, 13-16, 19-23]: проблема чотирьох фарб; задача розфарбування країн географічної карти (областей плоского графа);

розфарбування вершин та ребер графа; правильне розфарбування графа; розфарбування довільного (не обов’язкого плоского і зв’язного) графа; теорема

58

про біхроматичний граф (теорема Кеніга); теорема Брукса; теорема про п'ять фарб; прикладні задачі, що зв’язані з розфарбуванням графів.

Основними поняттями і визначеннями теми «Розфарбування графів», які надаються в [1-5, 7, 9-10, 14-16, 19-20, 22], є: геометрично двоїстий граф; k - розфарбований граф (k -хроматичний граф); хроматичне число; хроматичний клас графа (індекс); дуальний (реберний граф); біхроматичний граф; n- хроматичний граф; кліка; клікове число (щільність); незалежна множина; число незалежності.

4.8.19 Контрольні запитання

1.Поясніть існування проблеми чотирьох фарб для плоских карт.

2.Поясніть задачу розфарбування країн географічної карти (областей плоского графа).

3.Що називається розфарбуванням вершин графа.

4.Який граф називається k -розфарбованим? Наведіть приклади k - розфарбованих графів.

5.Що називається хроматичним числом?

6.Поясніть визначення хроматичного класу графа.

7.Який граф є біхроматичним графом?

8.Наведіть теорему Кеніга про біхроматичий граф.

9.Сформулюйте гіпотезу чотирьох фарб для карт.

4.8.20 Тема 10 «Двудольні та k-дольні графи»

Вивчення теми 10 «Двудольні та k-дольні графи» пов’язане із розглядом таких питань [1, 2, 11, 13, 17, 20, 22]: поняття двудольного графа (біографа,

парного графа); теорема про двудольність; приклади дводольних графів; поняття k-дольного графа.

Основними поняттями і визначеннями теми «Двудольні та k-дольні графи», які надаються в [1, 2, 17, 20, 22], є: неорієнтований двудольний граф;

орієнтований двудольний граф; долі дводольного графа; повний дводольний граф; k-дольний граф.

59

4.8.21 Контрольні запитання

1.Надайте поняття двудольного графа.

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

3.Наведіть декілька прикладів двудольних графів.

4.У яких випадках граф може бути двудольним?

5.Надайте визначення долей графа.

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

4.8.22 Теми 11-12 «Транспортні мережі та течії. Їх властивості. Найкоротші відстані та шляхи у мережах. Алгоритми Флойда і Данцига»

Вивчення тем 11-12 «Транспортні мережі та течії. Їх властивості.

Найкоротші відстані та шляхи у мережах. Алгоритми Флойда і Данцига» пов’язане із розглядом таких питань [1-5, 7, 9-11, 13-16, 19-23]: поняття транспортної мережі; властивості транспортної мережі; поняття переміщення з точки А у точку В графа «найкращим способом»; приклади мереж; алгоритм Дейкстри (алгоритм пошуку найкоротшого шляху з мінімальною сумою додатних ваг дуг); складність алгоритму Дейкстри; задача пошуку найкоротших шляхів між всіма парами вершин графа; алгоритм Дейкстри (Форда) визначення відстані між вершинами на графі з довільними довжинами ребер; алгоритм Флойда і пошуку найкоротших шляхів у графі; алгоритм Данцига пошуку найкоротших шляхів у графі; особливості застосування алгоритмів Дейкстри, Флойда, Данцига.

Основними поняттями і визначеннями теми «Транспортні мережі та течії.

Їх властивості. Найкоротші відстані та шляхи у мережах. Алгоритми Флойда і Данцига», які надаються в [1-5, 7, 9-10, 14-16, 19-20, 22], є: відстані між вершинами графа; зважений граф; транспортна мережа; шлях у мережі; пропускна здатність (місткість) дуги; вхід мережі; вихід мережі; течія в транспортній мережі.

4.8.23Контрольні запитання

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

2.Поясніть на прикладах відповідь на питання: «Як здійснити переміщення з точки А у точку В графа «найкращим способом?»

3.Надайте визначення транспортної мережі.

60