по рівнях класу порядку.
Малюнок 2.4 - Топологічно сортований граф
Завдання № 3
Формулювання завдання.
Дана матриця суміжності графа. Знайти центр графа і відхилення від центру для кожної вершини. Використовуючи матрицю суміжності, розрахувати загальна кількість шляхів довжиною 1, 2, 3, 4, 5, 6, а також за допомогою пойменованої матриці суміжності отримати і всі елементарні шляху, зазначеної довжини (у кожній наступній пойменованої матриці всі неелементарні шляху слід опускати). Матриця суміжності:
A (G) =.
Рішення.
Зобразимо даний граф.
В
Малюнок 3.1 - Початковий граф
Складемо матрицю R, елементи якої r (v i , v j ) є відстанями (довжинами шляхів) від вершини i до вершини j. Отримаємо:
R =.
Відхилення вершин від центру графа:
D (1) = (0 +3 +1 +2 +2 +1) =;
D (2) = (3 +0 +2 +2 +1 +1) =;
D (3) = (1 +4 +1 +3 +3 +2) =;
D (4) = (1 +1 +2 +0 +1 +2) =;
D (5) = (2 +1 +1 +2 +0 +1) =;
D (6) = (2 +2 +1 +1 +1 +1) =.
У даному графі мінімальне відхилення від центру у вершин 4 і 5. Отже, безліч вершин {4, 5} - центр графа. p> Підсумувавши всі елементи даної матриці суміжності A (G), отримаємо кількість шляхів довжиною 1, рівне 16.
Щоб отримати кількість шляхів довжиною 2, 3, 4, 5 і 6, зведемо матрицю A (G) у відповідні ступені:
A2 (G) =; 3 (G) =; 4 (G) =; 5 (G) =; 6 (G) =.
Тепер підсумуємо всі елементи кожної з вийшов матриць і отримаємо відповідно: кількість шляхів довжиною 2, рівне 44; кількість шляхів довжиною 3, рівне 121; кількість шляхів довжиною 4, рівне 326; кількість шляхів довжиною 5, рівне 876; кількість шляхів довжиною 6, рівне 2357.
Далі знайдемо всі елементарні шляху заданої довжини. Для цього складемо пойменовану матрицю суміжності і допоміжну матрицю:
A (G) =;
A (G) =.
За допомогою допоміжної матриці обчислимо ступеня матриці A (G). Так як в даному графі є 6 вершин, то максимальна ступінь пойменованої матриці для визначення всіх елементарних шляхів буде дорівнює 5. p> Обчисливши за формулою A2 (G) = A (G)? A (G), отримаємо наступні елементарні шляху довжиною 2: 1, 6, 3; 1, 6, 4; 1, 6, 5; 2, 5, 3; 2, 6, 3; 2, 6, 4; 2, 6, 5; 2, 5, 6; 3, 1, 6; 4, 5, 2; 4, 1, 3; 4, 5, 3; 4, 2, 5; 4, 1, 6; 4, 2, 6; 4, 5, 6; 5, 3, 1; 5, 6, 3, 5, 6, 4; 5, 2, 6; 6, 3, 1; 6, 4, 1; 6, 4, 2; 6, 5, 2; 6, 5, 3; 6, 4, 5.
Аналогічно обчислимо елементарні шляху довжиною 3: 1, 6, 4, 2; 1, 6, 5, 2; 1, 6, 5, 3; 1, 6, 4, 5; 2, 5, 3, 1; 2, 6, 3, 1, ...
