Пошук компонент сильної зв'язності орієнтованого графа в середовищі програмування 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) Загрузка ...Перевірка орієнтованого графа на ациклічність в середовищі програмування delphi
Програму розроблено в середовищі програмування Delphi, основним призначенням якої є перевірка орієнтованого графа на ациклічність. Нагадаємо, що орієнтований граф називається ациклічним, якщо в ньому відсутні орієнтовані цикли, тобто шляхи, що починається і закінчується в одній і тій же вершині. Відмітимо, що в якості методу, використовується алгоритм обходу в глибину.
Орієнтований граф в програмі задається у вигляді вершин (пронумеровані точки) та орієнтованих ребер (прямі лінії з заданим напрямком). Для цього на головній формі передбачено графічний редактор (компонент типу TImage) та дві кнопки типу TSpeedButton («Додати вершину» і «Додати ребро»). Підготовка проекту до нового прикладу здійснюється з допомогою кнопки «Видалити граф» (компонент типу TButton). При натисканні на кнопку «Перевірити орієнтований граф на наявність циклів» (також компонент типу TButton) власне і запускається алгоритм пошуку циклів в орієнтованому графі.
Вихідні дані програми — побудова дерева обходу в глибину та вивід у компонентів TMemo послідовності вершин орієнтованого циклу, якщо він існує.
Збережено в категорії: Програми на Delphi (Дослідження операцій) · Мітки: Delphi програма, Delphi проект, ациклічний орієнтований граф, глибина обходу, дерево пошуку в глибину, дослідження операцій на delphi, зворотне ребро, орієнтований граф, орієнтований цикл, пошук в глибину
(Кількість голочів: 1, середній бал: 5.00 із 5) Загрузка ...Топологічне сортування вершин орієнтованого графа
Нехай розглядається деякий орієнтований граф 
який не містить циклів. Під топологічним сортуванням даного графа розуміють процес лінійного впорядковування його вершин таким чином, що якщо в графі існує ребро 
, то, в упорядкованому списку вершин графа , вершина 
передує вершині 
. Якщо в орієнтованому графі є цикли, то упорядкованого таким чином списку для нього не існує.
Орієнтований граф та один з варіантів топологічного сортування його вершин
Відмітимо, що задачу про топологічне сортування можна переформулювати наступним чином: розмістити вершини орієнтованого графа на горизонтальній прямій таким чином, щоб всі його ребра йшли зліва направо. У житті це відповідає, наприклад, наступним проблемам: в якому порядку слід здійснювати розв'язок задачі, якщо вона розпадається на підзадачі і виконання деяких підзадач, зазвичай, починається слідом за закінченням інших; в якому порядку слід розташовувати теми в шкільному курсі математики, якщо для кожної теми відомо, знання яких інших тем необхідні для її вивчення; в якому порядку необхідно розподілити опис процедур в програмі, якщо деякі процедури можуть містити звернення до інших процедур.
Збережено в категорії: Дослідження операцій · Мітки: задача про топологічне сортування, орієнтований граф, пошук в глибину, топологічне сортування, топологічне сортування вершин
(Кількість голочів: 1, середній бал: 5.00 із 5) Загрузка ...Растеризація кола використовуючи алгоритм Брезенхема
У параграфі растеризація відрізка за алгоритмом Брезенхема було розглянуто один з найвідоміших і найбільш викокористовуваних алгоритмів комп'ютерної графіки, призначених для розкладання відрізка в растр. Сьогодні розглянемо найбільш ефективний і простий для розуміння алгоритм генерації більш складної геометричної фігури, а саме кола, який також належить Брезенхему. Для початку зауважимо, що згідно з цим алгоритмом, достатньо згенерувати тільки одну четверту чи навіть одну восьму частину кола. Інші його частини можуть бути отримані послідовними відображеннями, як це показано на насутпному малюнку.
Генерація повного кола з дуги в першому октанті
Тобто, якщо згенерований перший октант (від 
до 
проти годинникової стрілки), то другий октант можна отримати дзеркальним відображенням відносно прямої 
, що дає в сукупності перший квадрант. Перший квадрант відбивається відносно прямої 
для отримання відповідної частини кола в другому квадранті. Верхнє півколо відбивається відносно прямої 
для завершення побудови. Відмітимо, що на рисунку наведені двовимірні матриці відповідних перетворень.
Збережено в категорії: Алгоритми комп’ютерної графіки · Мітки: алгоритм Брезенхема, генерація кола, растеризація кола, растрове представлення, розкладання в растр
(Кількість голочів: 4, середній бал: 5.00 із 5) Загрузка ...
Загрузка ...