Топологічне сортування орієнтованого графа методом видалення вершини-джерела
Нагадаємо, що за посиланням топологічне сортування вершин графа нами була розглянута одна з основних задач, що виникає при роботі з орієнтованими графами та один з методів для її рішення.
Топологічне сортування графа методом видалення вершини-джерела
Сьогодні, для розв'язку задачі такого типу, застосуємо дещо інший алгоритм, заснований на безпосередній реалізації методу зменшення розміру задачі, а якщо бути більш точним, то зменшенням розміру на одиницю.
Основна суть даного алгоритму полягаєв в тому, що на кожній з його ітерацій, здійснюється визначення вершини-джерела орієнтованого графа що залишився (джерелом називається вершина в яку не входить жодне ребро), і, в подальшому, видалення його з усіма, що виходять з нього, ребрами. Якщо таких вершин декілька, довільним чином вибирається одна з них. Порядок видалення таким чином вершин, дає рішення задачі про топологічне сортування. Відмітимо, що якщо на деякому кроці виявиться, що для орієнтованого графа що залишився, вершини-джерела не існує, то задача про тополігічне сортування розв'язків немає.
Збережено в категорії: Дослідження операцій · Мітки: задача про топологічне сортування, методом зменшення розміру задачі, орієнтований граф, топологічне сортування, топологічне сортування вершин
(Ще не оцінили)
Загрузка ...Застосування методу Крилова для знаходження власних векторів матриці
Метод Крилова, як і метод Данилевського, дає можливість достатньо просто знайти власні вектора матриці, якщо коефіцієнти характеристичного полінома та його коріння визначені. Продемонструємо це і для простоти обмежимося випадком, коли характеристичний многочлен 
матриці 
, має різні корені 
.
Отже, нехай 
— вектори, використовувані в методі Крилова для знаходження коефіцієнтів 
. Розкладаючи вектор 
за власними векторами 
матриці 
отримаємо:
Де 
— деякі коефіцієнти.
Звідси, враховуючи, що 
, отримаємо:
Нехай, 
— довільна система многочленів. Тоді, складаючи лінійну комбінацію векторів 
з коефіцієнтами з (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) Загрузка ...Топологічне сортування вершин орієнтованого графа в середовищі програмування delphi
В даному параграфі розглянемо delphi-проект, який використовуючи алгоритм обходу орієнтованого графа в глибину, виконує топологічне сортування всіх його вершин. Нагадаємо, що під топологічним сортуванням орієнтованого графа розуміють такий лінійний порядок його вершин, при якому всі його ребра йдуть зліва направо. Очевидно, що якщо в графі містяться цикли, то такого порядку не існує.
Головна форма розглядуваного проекту складається з панелі інструментів та графічного редактора.
Головне вікно проекту "Топологічне сортування вершин орієнтованого графа"
Розглянемо призначення кожного з цих едементів більш детально.
Збережено в категорії: Програми на Delphi (Дослідження операцій) · Мітки: топологічне сортування delphi, топологічне сортування вершин, топологічне сортування графа
(Кількість голочів: 1, середній бал: 5.00 із 5) Загрузка ...Знаходження компонент сильної зв'язності орієнтованого графа
Компонентою сильної зв'язності орієнтованого графа називається максимальна множина його вершин, в якій існують шляхи з будь-якої вершини в будь-яку іншу. Так наприклад, граф 
, зображений на рисунку що міститься нижче, складається з чотирьох компонент сильної зв'язності: 
, 
, 
і 
.
Орієнтований граф та його компоненти сильної зв'язності
Як видно з рисунка, кожна вершина орієнтованого графа належить певній компоненті сильної зв'язності, але деякі ребра можуть не належати жодній з них. Такі ребра з'єднують вершини з різних компонент.
Збережено в категорії: Дослідження операцій · Мітки: зв'язність графа, компоненти сильної звязності, конденсація орієнтованого графа, сильна зв'язність графа
(Кількість голочів: 1, середній бал: 5.00 із 5) Загрузка ...Редагування та навігація по записах набору даних використовуючи компонент TDBNavigator
Переміщення, або навігація по записах набору даних, може здійснюватися кількома шляхами. Наприклад, в компонентах TDBGrid та TDBCtrlGrid, які відображають відразу кілька записів, можна використовувати клавіші вертикального переміщення курсору або вертикальну смугу прокрутки. Але що робити, якщо на формі знаходяться компоненти, що відображають одне поле тільки поточного запису набору даних (TDBEdit, TDBMemo, TDBComboBox та інші)? Очевидно, що в такому випадку на формі повинні бути розміщені додаткові елементи управління, що відповідають за переміщення по записах.
Навігація та редагування набору даниз використовуючи компонент TDBNavigator
Для вирішення зазначених завдань і призначений delphi-компонент TDBNavigator, який являє собою сукупність керуючих кнопок, які реалізують операції навігації по набору даних, а також, модифікації та видалення записів цілком.
Збережено в категорії: Робота з базами даних в середовищі програмування Delphi · Мітки: delphi-компонент tdbnavigator, TDBNavigator, навігатор tdbnavigator, навігації по набору даних, переміщення по набору даних, редагування записів набору даних
(Кількість голочів: 1, середній бал: 5.00 із 5) Загрузка ...
Загрузка ...