2, 8, 18, 6, 12, 4, 16 , 5, 14};
G 3 (1) = {1, 2, 8, 18, 6, 12, 4, 16 , 5, 14, 3, 15, 10, 13, 17};
G 4 (1) = {1, 2, 8, 18, 6, 12, 4, 16 , 5, 14, 3, 15, 10, 13, 17, 11, 7}.
Решта ступеня оператора G знаходити не потрібно, так як це не призводить до появи в безлічі G k (1) нових вершин. Отже, пряме Транзитивне замикання
G+ (1) == {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18}.
Ступені оператора зворотного транзитивного замикання для першої вершини:
G-1 (1) = {1, 11, 12};
G-2 (1) = {1, 11, 12, 3, 13, 2, 4, 7, 14, 15};
G-3 (1) = {1, 11, 12, 3, 13, 2, 4, 7, 14, 15, 6, 17, 8, 5, 9, 16, 18, 10}.
Решта ступеня оператора не знаходимо з тієї ж причини. Отже, зворотне Транзитивне замикання
G-(1) == {1,2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}.
Таким чином, компонента зв'язності для вершини 1
C1 = G+ (1)? G-(1) = {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18 }.
Після цих обчислень залишається вершина 9, яка не увійшла в компоненту. Не вважаючи G+ (9) і G-(9), можна зробити висновок, що C2 = {9}. p> Перевіримо знайдені компоненти зв'язності шляхом безпосередніх перетворень матриці суміжності. Зліва від матриці приписуємо стовпець, i-й елемент якого є довжиною шляху з першої вершини в i-ю. Знизу приписуємо рядок, i-й елемент якої є довжиною шляху з i-й вершини в першу. Отримана матриця з приписаними стовпцем і рядком представлена ​​на малюнку 1.3. <В
Малюнок 1.3 - Перетворення матриці суміжності
За приписаним колонку і рядку записуємо пряме і зворотне транзитивні замикання вершини 1:
G+ (1) = {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18};
G-(1) = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}.
Отже, компонента зв'язності вершини 1
C1 = G+ (1)? G-(1) = {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18 }.
Компонента зв'язності вершини 9
C9 = {9}.
На малюнку 1.4 представлений граф, розкладений на сильно пов'язані підграфи.
В
Малюнок 1.4 - Граф, розкладений на сильно пов'язані підграфи
Завдання № 2
Формулювання завдання.
Задано орієнтований граф з 18 вершинами без контурів. Необхідно зробити розбивку графа на класи порядку. Потім знайти два шляхи, максимального і мінімального ваги. Шляхи починаються у вершині нижнього рівня, а закінчуються в вершині верхнього рівня. p> Матриці суміжності і ваг представлені на малюнках 2.1 і 2.2.
В
Малюнок 2.1 - Матриця су...
