lign="justify"> 7 .
Хорди: e 8 , e 9 .
Базисні цикли: 125471, 2452.
Базисні розрізи: e 2 ; e 3 ; e 7 ; e 1 e 8 ; e 6 e 8 ; e < span align = "justify"> 4 e 8 e 9 ; e 5 e 8 e 9 .
Ранг графа G k = 7, цикломатичне число графа l = 2.
Матриця Кірхгофа графа G:
K =.
Щоб знайти кількість можливих кістяків для графа G, необхідно знайти яке-небудь алгебраїчне доповнення матриці Кірхгофа. Обчисливши алгебраїчне доповнення K22, отримали можливу кількість кістяків рівне 11. p> Один з можливих кістяків ми вказали на початку завдання. Вкажемо ще 4 можливих остова. br/>В
Малюнок 4.5 - Приклади можливих кістяків
5 Завдання № 5
Формулювання завдання.
Дана матриця суміжності графа. Побудувати двочастковий граф і його реберний граф. Для дводольного графа знайти максимальні паросполучення і мінімальні реберні покриття. Для реберного графа визначити всі максимальні вершинні незалежні множини і всі мінімальні вершинні покриття. Для цього використовувати бульову функцію реберного графа, записавши її в КНФ, потім перетворити її в ДНФ і зробити перевірку знайдених виразів з допомогою принципу подвійності. p align="justify"> Матриця суміжності:
A (G) =.
Рішення
Зобразимо двочастковий граф G.
В
Малюнок 5.1 - дводольні граф
Зобразимо реберний граф Gр .
В
Малюнок 5.2 - Реберний граф
Максимальні паросполучення для дводольного графа G:
1) e 1 , e 3 ;
) e 1 , e
