2, 6, 4, 1, 2, 6, 5, 3; 2, 5, 6, 3; 2, 5, 6, 4; 2, 6, 4, 5; 3, 1, 6, 4; 3, 1, 6, 5; 4, 5, 3, 1; 4, 2, 5, 3; 4, 1, 6, 3; 4, 2, 6, 3; 4, 5, 6, 3; 4, 1, 6, 5; 4, 2, 6, 5; 4, 5, 2, 6; 4, 2, 5, 6; 5, 6, 3, 1; 5, 6, 4, 1; 5, 6, 4, 2; 5, 2, 6, 3, 5, 2, 6, 4; 5, 3, 1, 6; 6, 5, 3, 1; 6, 4, 5, 2; 6, 4, 1, 3; 6, 4, 5, 3; 6, 4, 2, 5.
Елементарні шляху довжиною 4: 1, 6, 4, 5, 2; 1, 6, 4, 5, 3; 1, 6, 4, 2, 5; 2, 6, 5, 3, 1, 2, 5, 6, 3, 1, 2, 5, 6, 4, 1, 2, 6, 4, 1, 3; 2, 5, 3, 1, 6; 3, 1, 6, 4, 2; 3, 1, 6, 5, 2; 3, 1, 6, 4, 5; 4, 2, 5, 3, 1; 4, 2, 6, 3, 1; 4, 5, 6, 3, 1; 4, 1, 6, 5, 2; 4, 1, 6, 5, 3; 4, 2, 6, 5, 3; 4, 5, 2, 6, 3; 4, 2, 5, 6, 3; 4, 5, 3, 1, 6; 5, 2, 6, 3, 1; 5, 2, 6, 4, 1; 5, 6, 4, 1, 3, 5, 3, 1, 6, 4; 6, 4, 5, 3, 1; 6, 4, 2, 5, 3.
Елементарні шляху довжиною 5: 1, 6, 4, 2, 5, 3; 2, 5, 6, 4, 1, 3; 2, 5, 3, 1, 6, 4; 3, 1, 6, 4, 5, 2; 3, 1, 6, 4, 2, 5; 4, 2, 6, 5, 3, 1; 4, 5, 2, 6, 3, 1; 4, 2, 5, 6, 3, 1; 4, 2, 5, 3, 1, 6; 5, 3, 1, 6, 4, 2; 5, 2, 6, 4, 1, 3; 6, 4, 2, 5, 3, 1.
Завдання № 4
Формулювання завдання.
Дана матриця суміжності графа. Побудувати для даного графа додатковий і двоїстий. Вказати остови (не менше 5), базисні цикли, базисні розрізи, знайти ранг і цикломатичне число, підрахувати кількість можливих кістяків. Матриця суміжності:
A (G) =.
Рішення
Зобразимо даний граф у планарною укладанні.
Малюнок 4.1 - Початковий граф у планарною укладанні
Зобразимо окремо двоїстий і додатковий графи.
Малюнок 4.2 - Двоїстий граф G
Малюнок 4.3 - Додатковий граф
Зобразимо один з кістяків вихідного графа G.
e 3
e 2 e 1
e 4
e 8 e 9 e 5
e 7 e 6
Малюнок 4.4 - Один з кістяків вихідного графа G
остовно ребра для обраного остова: e 1 , e 2 , e 3 , e 4 , e 5 , e 6 , e
