Перевірка неорієнтованого графа на дводольність в середовищі програмування delphi
Дводольні графи, що виникають при розгляді задач з використанням математичних об'єктів такого типу, нерідко бувають задані множиною вершин, яка складається з двох частин та множиною ребер, кожне з яких з'єднує вершини з різних частин. У таких випадках питання про їх дводольність просто не виникає. Однак, нас буде цікавити випадок, коли інформація про те, чи заданий графа являється дводольним заздалегідь є не відомою, і потрібно це з'ясувати. Зазначимо, що саме з цією метою і було розроблено розглядуваний в даному параграфі delphi-проект.
Головне вікно проекту "Перевірка неорієнтованого графа на дводольність"
Отже, неорієнтований граф в програмі задається у вигляді вершин (пронумеровані точки) та ребер (прямі лінії). Для цього на головній формі передбачено графічний редактор (компонент типу TImage) та дві кнопки типу TSpeedButton («Додати вершину» і «Додати ребро»). Підготовка проекту до нового прикладу здійснюється з допомогою кнопки «Видалити граф» (компонент типу TButton). При натисканні на кнопку «Перевірити граф на дводольність» (також компонент типу TButton) власне і запускається алгоритм перевірки графа на дводольність.
Переборний алгоритм для розфарбування вершин графа
Розфарбуванням вершин графа називається процес призначення певного кольору кожній з його вершин. Зазвичай кольори — це числа 
. Тоді, розфарбування є функцією, визначеною на множині вершин графа, яка приймає значення з множини 
.
Розмальовку можна також розглядати як розбиття множини вершин графа на підмножини, кожна з яких являється множиною вершин певного кольору. Відмітимо, що такі підмножини називаються кольоровими класами. Розфарбування називається правильним, якщо кожен кольоровий клас є незалежною множиною. Інакше кажучи, в правильному розфарбуванні будь-які дві суміжні вершини повинні мати різні кольори. Задача про розфарбовування полягає в знаходженні правильної розмальовки графа 
в найменше число кольорів. Це число називається хроматичним числом графа і позначається 
.
Розфарбування вершин графа найменшим набором квітів
У правильному розфарбуванні повного графа , кожна з його 
вершин повинна бути зафарбована у свій колір, тому хроматичне числа графа такого типу дорівнює кількості його вершин, тобто 
. Якщо в графі існує повний підграф з 
вершинами, то для розмальовки цього підграфа необхідно кольорів. Звідси випливає, що для будь-якого графа виконується нерівність 
, де 
— клікове число графа .
Перевірка графа на дводольність
Граф називається дводольним, якщо множину його вершин можна розбити на дві підмножини так, щоб кінці кожного ребра належали різним підмножини. Ці підмножини називаються частками, кожна з яких породжує порожній підграф. Відмітимо, що дводольний граф у якого будь-яка вершина першої частки з'єднана з усіма вершинами другої частки називається повним дводольним графом.
Приклад дводольного графа
Прикладне значення поняття дводольного графа пов'язано з тим, що за допомогою таких графів моделюються відносини між об'єктами двох типів, а такі відносини часто зустрічаються на практиці. Наприклад, відношення між вихідними продуктами і готовими виробами (продукт 
використовується у виробництві виробу 
), відношення між працівниками і професіями (працівник володіє професією ), відношення між викладачами та навчальними курсами (викладач веде навчальний курс ) та інші.
Топологічне сортування вершин орієнтованого графа методом видалення вершини-джерела в середовищі програмування delphi
Топологічне сортування — це сортування елементів, для яких визначено частковий порядок, тобто впорядкування задано не на всіх, а тільки на деяких парах елементів. Крім того, це однин з основних алгоритмів на графах, який застосовується для вирішення більш складних задач.
Відмітимо, що на даному сайті нами вже були розглянуті загальні принципи топологічного сортування, вивчені основні методи топологічного сортування (метод, що базується на обході графа в глибину та метод видалення вершини-джерела), а також, розглянута реалізація першого методу, в середовищі програмування delphi.
Сьогодні розглянемо delphi-проект, який реалізує другий з методів, а саме метод видалення вершини-джерела. Виходячи з того, що розглядуваний проект нічим не відрізняється від свого попередника (тільки методом, що реалізується), то досліджувати призначення кожного з елементів його головної форми в даному параграфі не будемо. Це все можна знайти і ознайомитись, перейшовши за посиланням Топологічне сортування графа методом обходу в глибини в середовищі програмування delphi.
Топологічне сортування орієнтованого графа методом видалення вершини-джерела
Нагадаємо, що за посиланням топологічне сортування вершин графа нами була розглянута одна з основних задач, що виникає при роботі з орієнтованими графами та один з методів для її рішення.
Топологічне сортування графа методом видалення вершини-джерела
Сьогодні, для розв'язку задачі такого типу, застосуємо дещо інший алгоритм, заснований на безпосередній реалізації методу зменшення розміру задачі, а якщо бути більш точним, то зменшенням розміру на одиницю.
Основна суть даного алгоритму полягаєв в тому, що на кожній з його ітерацій, здійснюється визначення вершини-джерела орієнтованого графа що залишився (джерелом називається вершина в яку не входить жодне ребро), і, в подальшому, видалення його з усіма, що виходять з нього, ребрами. Якщо таких вершин декілька, довільним чином вибирається одна з них. Порядок видалення таким чином вершин, дає рішення задачі про топологічне сортування. Відмітимо, що якщо на деякому кроці виявиться, що для орієнтованого графа що залишився, вершини-джерела не існує, то задача про тополігічне сортування розв'язків немає.
Застосування методу Крилова для знаходження власних векторів матриці
Метод Крилова, як і метод Данилевського, дає можливість достатньо просто знайти власні вектора матриці, якщо коефіцієнти характеристичного полінома та його коріння визначені. Продемонструємо це і для простоти обмежимося випадком, коли характеристичний многочлен 
матриці 
, має різні корені 
.
Отже, нехай 
— вектори, використовувані в методі Крилова для знаходження коефіцієнтів 
. Розкладаючи вектор 
за власними векторами 
матриці 
отримаємо:
Де 
— деякі коефіцієнти.
Звідси, враховуючи, що 
, отримаємо:
Нехай, 
— довільна система многочленів. Тоді, складаючи лінійну комбінацію векторів 
з коефіцієнтами з (3) та в силу співвідношень (1) і (2), знаходимо:
Пошук власних векторів матриці методом Данилевського
Розглянутий в параграфі Пошук власних значень матриці метод Данилевського дає можливість визначати не тільки всі власні значення матриці 
, а і всі її власні вектори, при умові, що відповідні їм власні значення являються відомими. Покажемо, яким чином це реалізується. Отже, нехай 
— власне значення матриці , а отже, і власне значення подібної їй матриці Фробеніуса 
.
Знайдемо власний вектор 
матриці , який відповідає власному значенню . Для цього, запишемо лінійне рівняння наступного вигляду: 
. Звідси 
або у матрично-векторній формі:
Перемноживши матриці, отримаємо систему для визначення координат 
власного вектора 
:
Система (3) — однорідна. Рішення її може бути знайдене в такий спосіб. Покладемо 
. Тоді, починаючи з останнього рівняння, послідовно отримаємо:
Загрузка ...