Завдання 2 Зображення структур у матричному вигляді

Для графа, який зображено на рис. 2, побудувати матрицю суміжностей, знайти ізольовані, висячі вершини та тупики.

Визначити ці вершини, використовуючи лише інформацію, наявну в матриці суміжностей.

Рисунок 2 ‑ Граф для завдання

Методичні рекомендації щодо виконання завдання

Розглянемо структуру, подану у вигляді наступного графа (рис. 3) з орієнтованими та неорієнтованими дугами.

Рисунок 3 ‑ Граф структурної схеми

Неорієнтовані дуги можна замінити парою орієнтованих, скерованих у протилежних напрямках, і зобразити граф у вигляді матриці суміжностей вершин V= , у якій , якщо в графі є ребро (i, j) від і-ї до j-ї вершини, і , якщо немає. Отже, матричне зображення буде таким, як на рис. 4.

Рисунок 4 ‑ Матриця суміжностей

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

У наведеному прикладі (рис. 5 вершина 9 є ізольованою, 1 та 5 — висячі, 6 та 8 — тупики.

Рисунок 5 ‑ Граф для прикладу топологічного аналізу

Наявність ізольованих вершин свідчить про наявність помилок, які зроблені в процесі формування чи опису структури, оскільки система є цілісним об'єктом, елементи якого повинні бути взаємопов'язаними. Висячі та тупикові вершини повинні відповідати вхідним та вихідним елементам системи, через які здійснюється процес її взаємодії з зовнішнім середовищем.

Дата добавления: 2015-09-01