Пошук компонент сильної зв'язності орієнтованого графа в середовищі програмування delphi

Delphi-програма, для заданого орієнтованого графа, виводить всі компоненти сильної зв'язності (нагадаємо, що компонентою сильної зв'язності орієнтованого графа, називається така підмножина його вершин, що будь-які дві вершини цієї підмножини, досяжні одна з одної). У програмі передбачено візуальне формування графа за допомогою миші. Для цього, на головній формі міститься графічний редактор (компонент типу TImage) та дві кнопки типу TSpeedButton («Додати вершину» і «Додати ребро»). Підготовка проекту до нового прикладу здійснюється з допомогою кнопки «Видалити граф» (компонент типу TButton). При натисканні на кнопку «Пошук компонент сильної зв'язності» (також компонент типу TButton) власне і запускається алгоритм пошуку сильно зв'язних компонент заданого графа. Результат виконання алгоритму відображається в області виводу результатів (компонент типу TStatusBar).

Зауваження: більш детальна інформація про призначенння кожного з елементів головної форми проекту та процес побудови орієнтованого графа міститься за посиланням Топологічне сортування вершин орієнтованого графа.

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

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

Для цього, запустивши проект та скориставшись графічним редактором і відповідними кнопками панелі задач («Додати вершину», «Додати ребро»), побудуємо вершини вищевказаного графа та поєднаємо їх відповідними орієнтованими ребрами.

Читати повністю

Топологічне сортування вершин орієнтованого графа в середовищі програмування delphi

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

Головна форма розглядуваного проекту складається з панелі інструментів та графічного редактора.

Головне вікно проекту "Топологічне сортування вершин орієнтованого графа"

Розглянемо призначення кожного з цих едементів більш детально.

Читати повністю

Перевірка орієнтованого графа на ациклічність в середовищі програмування delphi

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

Орієнтований граф в програмі задається у вигляді вершин (пронумеровані точки) та орієнтованих ребер (прямі лінії з заданим напрямком). Для цього на головній формі передбачено графічний редактор (компонент типу TImage) та дві кнопки типу TSpeedButton («Додати вершину» і «Додати ребро»). Підготовка проекту до нового прикладу здійснюється з допомогою кнопки «Видалити граф» (компонент типу TButton). При натисканні на кнопку «Перевірити орієнтований граф на наявність циклів» (також компонент типу TButton) власне і запускається алгоритм пошуку циклів в орієнтованому графі.

Вихідні дані програми — побудова дерева обходу в глибину та вивід у компонентів TMemo послідовності вершин орієнтованого циклу, якщо він існує.

Читати повністю

Побудова дерева обходу в глибину для орієнтованого графа в середовищі програмування delphi

Розглядуваний в даному параграфі delphi-проект реалізує процес побудови дерева обходу в глибину для орієнтованого графа. Головна форма проекту, як і у випадку з глибинним обходом неорієнтованого графа, ділиться на дві частини і складається з панелі інструментів та графічного редактора.

Головне вікно проекту "Побудова дерева обходу в глибину для орієнтованого графа"

  1. Панель інструментів (компонент типу TPanel): містить чотири кнопки: «Додати вершину» (типу TSpeedButton), «Додати ребро» (типу TSpeedButton), «Видалити граф» (типу TButton) та «Побудувати дерево обходу в гибину» (типу TButton). Відмітимо, що три кнопки з даного списук призначенні для побудови та видалення орієнтованого графа і четверта — реалізує його глибинний обхід.
  2. Графічний редактор (компонент типу TImage): призначений для побудови і візуалізації орієнтованого графа, а також візуалізації відповідного йому дерева обходу в глибину. Для того, щоб намалювати вершини графа потрібно, на першому кроці, активізувати кнопку панелі задач «Додати вершину». На наступному кроці, з допомогою лівої кнопки мишки, розставити їх у відповідній області форми. Після того, як вершини створено потрібно пов'язати їх відповідним орієнтованим ребром. Орієнтоване ребро в даній програмі створюється наступним чином: активізувавши кнопоку «Додати ребро» лівою кнопокою миші поєднюємо необхідні вершини. Для видалення графа чи побудови його дерева обходу в глибину необхідно скористатися однойменними кнопками що містяться на панелі задач.

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

Читати повністю

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

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

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

tochka_spoluchennja_grafa_delphi11

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

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

Читати повністю

Побудова Гамільтонового циклу в середовищі програмування delphi

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

Для того, щоб запустити програму необхідно, в каталозі де збережено delphi-проект, знайти файл Project1.ехе і запустити його. Після запуску програми на екрані буде відображено наступне вікно.

Побудова Гамільтонового циклу на delphi

Головне вікно проекту "Побудова Гамільтонового циклу для неорієнтованого графа"

Тобто, головне вікно складається з панелі інструментів, області графічного представлення та області виводу результатів. На панелі інструментів (компонент типу TPanel) розташовується чотири кнопки (дві типу TSpeedButton і дві що залишились, типу TButton) зліва направо: «Додати вершину», «Додати ребро», «Видалити граф», «Знайти Гамільтонів цикл». Праворуч від кнопки «Видалити граф» знаходиться напис «Вибрати цикл» біля якого міститься поле вибору типу TComboBox. Дане поле зберігає список знайдених Гамільтонових циклів. Змінюючи значення даного компонента згідно з даним списком, можна наглядно спостерігати порядок обходу вершин кожного з циклів. Область графічного представлення (компонент типу TImage), як уже зазначалося вище, використовується для побудови і відображення неорієнтованого графа та Гамільтонового циклу в ньому. І нарешті, область виводу результатів (компонент типу TMemo) відображає, у вигляді списку вершин, всі знайдені Гамільтонові цикли (якщо заданий граф Гамільтонових циклів не містить, в даній області, буде виведено відповідне повідомлення).

Читати повністю

Пошук Ейлерового циклу використовуючи алгоритм Флері в середовищі програмування delphi

Програму розроблено в середовищі програмування Delphi, основним призначенням якої є побудова Ейлерового циклу в Ейлеровому графі. В якості методу, використовується алгоритм Флері.

Граф задається у вигляді вершин (пронумеровані точки) та ребер (прямі лінії що їх з'єднюють). Для цього в програмі передбачено графічний редактор (компонент типу TImage) та дві кнопки типу TSpeedButton («Додати вершину» і «Додати ребро»). Підготовка проекту до нового прикладу здійснюється з допомогою кнопки «Видалити граф» (компонент типу TButton). При натисканні на кнопку «Побудувати Ейлерів цикл» (також компонент типу TButton) власне і запускається алгоритм Флері пошуку Ейлерового циклу.

Вихідні дані програми — послідовність вершин Ейлерового циклу та його представлення у графічному редакторі.

Читати повністю

Наступна сторінка »