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