Пошук точок сполучення в неорієнтованому графі засобами delphi

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

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

tochka_spoluchennja_grafa_delphi11

Головне вікно проекту "Пошук точок сполучення в зв'язному неорієнтованому графі"

Як видно з малюнку, головне вікно delphi-проекту складається з наступних елементів: панель інструментів (компонент типу TPanel — служить контейнером для чотирьох кнопок «Додати вершину», «Додати ребро», «Видалити граф», «Знайти точки сполучення»), графічний редактор (компонент типу TImage) та область виводу результатів (компонент типу TMemo). Перші два з них призначені для побудови та графічного представлення зв'язного неорієнтованого графа і третій — виводить номера вершин, які для заданого графа являються точками сполучення.

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

Далі, перейдемо до практики де, використовуючи розглядувану в параграфі delphi-програму, спробуємо знайти точки сполучення для зв'язного неорієнтований граф наступного вигляду.

tochka_spoluchennja_grafa_delphi2

Неорієнтований граф

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

tochka_spoluchennja_grafa_delphi3

Побудова неорієнтованого графа

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

Пошук точок сполучення в неорієнтованому графі

Скачати delphi-проект Пошук точок сполучення в зв'язному неорієнтованому графі.

Матеріал був корисним, поділись в соціальних мережах:
Якщо тобі сподобалась дана тема, залиш свій коментар