Знаходження компонент сильної зв'язності орієнтованого графа

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

komponenty_sylnoi_zvjaznosti_grafa110

Орієнтований граф та його компоненти сильної зв'язності

Як видно з рисунка, кожна вершина орієнтованого графа  належить певній компоненті сильної зв'язності, але деякі ребра можуть не належати жодній з них. Такі ребра з'єднують вершини з різних компонент.

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

Редагування та навігація по записах набору даних використовуючи компонент TDBNavigator

Переміщення, або навігація по записах набору даних, може здійснюватися кількома шляхами. Наприклад, в компонентах TDBGrid та TDBCtrlGrid, які відображають відразу кілька записів, можна використовувати клавіші вертикального переміщення курсору або вертикальну смугу прокрутки. Але що робити, якщо на формі знаходяться компоненти, що відображають одне поле тільки поточного запису набору даних (TDBEdit, TDBMemo, TDBComboBox та інші)? Очевидно, що в такому випадку на формі повинні бути розміщені додаткові елементи управління, що відповідають за переміщення по записах.

Навігація та редагування набору даниз використовуючи компонент TDBNavigator

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

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

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

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

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

Вихідні дані програми — побудова дерева обходу в глибину та вивід у компонентів TMemo послідовності вершин орієнтованого циклу, якщо він існує.

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

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

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

topologichne_sortuvannja_grafa28

Орієнтований граф та один з варіантів топологічного сортування його вершин

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

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

Растеризація кола використовуючи алгоритм Брезенхема

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

algorytm_brezenhema_dlja_kola85

Генерація повного кола з дуги в першому октанті

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

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

Перевірка орієнтованого графа на наявність циклів

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

Отже, розглянемо деякий орієнтований граф . Для того, щоб перевірити даний граф на наявність циклів, виконуємо глибинний обхід всіх його вершин. В результаті, отримаємо дерево обходу в глибину. Якщо в побудованому дереві зустрінеться хоча б одне зворотне ребро, то ясно, що орієнтований граф має цикл. Справедливе і обернене твердження, тобто, якщо в орієнтованому графі є цикл, тоді зворотне ребро обов'язково зустрінеться при його обході методом пошуку в глибину. Щоб довести це, припустимо, що орієнтований граф  має цикл.

Перевірка орієнтованого графа на наявність циклів

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

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

Відображення та редагування даних булевого типу використовуючи компонент TDBCheckBox

Компонент TDBCheckBox — пов'язаний з даними аналог звичайного індикатора TCheckBox. Він дозволяє відображати і редагувати дані поля булевого, а також символьного та числового типу. Якщо при виведенні даних булеве поле приймає значення True, то пов'язаний з ним індикатор являється включеним. Якщо ж в процесі редагування користувач включить або вимкне індикатор, то відповідно значення True або False запишеться у відповідному полі таблиці бази даних. Це один із способів забезпечити користувачеві безпомилкове введення значень в поле таблиці бази даних.

Зв'язок компонента типу TDBCheckBox з полем набору даних здійснюється за допомогою його властивостей DataSource типу TDataSource і DataField типу TDataField. Перше з властивостей вказує на ім'я компонента джерела даних, через який здійснюється зв'язок з набором даних. І властивість DataField для пов'язаного набору даних вказує ім'я поля.

Якщо ж delphi-компонент TDBCheckBox пов'язаний з полем символьного або числового типу, то у властивості ValueChecked типу String даного компонента заноситься рядок, який перераховує значення поля, при яких індикатор включається, а у властивості ValueUnchecked (також типу String) перераховуються значення, при яких індикатор вимикається (окремі значення розділяються крапкою з комою). При значеннях, що не перераховані ні у ValueChecked, ні у ValueUnchecked, індикатор TDBCheckBox переходить у невизначений стан, відображаючи сірий прапорець (навіть у тому випадку коли властивість AllowGrayed (відповідає за заборону переводу індикатора в невизначений стан) приймає значення False).

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

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