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

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

Головне вікно проекту "Перевірка неорієнтованого графа на дводольність"

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

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

Переборний алгоритм для розфарбування вершин графа

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

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

Розфарбування вершин графа найменшим набором квітів

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

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

Перевірка графа на дводольність

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

Дводольний граф

Приклад дводольного графа

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

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

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

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

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

tochka_spoluchennja_grafa_delphi11

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

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

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

Знаходження точок сполучення зв'язного неорієнтованого графа та перевырка його на двозв'язність

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

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

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

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

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

Пошук Гамільтоновго циклу в неорієнтованому графі

Гамільтоновим циклом (Гамільтоновим ланцюгом) неорієнтованого графа називають простий цикл, що містить всі його вершини в точності по одному разу. Зовні визначення Гамільтонового циклу схоже на визначення Ейлерового циклу. Однак є кардинальна відмінність в складності розв'язку відповідних задач на розпізнавання і побудову. Тобто, якщо при розгляді Ейлерового циклу ми бачили, що для нього існує досить простий критерій перевірки його існування і ефективний алгоритм його побудови. То для Гамільтонових же циклів невідомо ніяких необхідних і достатніх умов їх існування, а всі відомі алгоритми вимагають, для деяких графів, перебору великого числа варіантів.

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

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

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

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

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

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

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