Пошук точок сполучення в неорієнтованому графі засобами delphi

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

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

tochka_spoluchennja_grafa_delphi11

Головне вікно проекту "Пошук точок сполучення в зв'язному неорієнтованому графі"

Як видно з малюнку, головне вікно delphi-проекту складається з наступних елементів: панель інструментів (компонент типу TPanel — служить контейнером для чотирьох кнопок «Додати вершину», «Додати ребро», «Видалити граф», «Знайти точки сполучення»), графічний редактор (компонент типу TImage) та область виводу результатів (компонент типу TMemo). Перші два з них призначені для побудови та графічного представлення зв'язного неорієнтованого графа і третій — виводить номера вершин, які для заданого графа являються точками сполучення.

Далее

Знаходження точок сполучення зв'язного неорієнтованого графа та перевырка його на двозв'язність

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

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

Графічне представлення алгоритму пошуку точок сполучення в неорієнтованому графі

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

Далее

Знаходження значення функції за побудованим графіком засобами Delphi: Приклад 3

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

Ілюстрація функції графічно

Отже, відкриємо середовище Delphi та створимо новий проект. На наступному кроці, на головній формі розмістимо наступні елементи: вікно редагування багаторядкового тексту Memo1 типу TMemo, кнопку Button1 типу TButton та компонент-діаграму Chart1 типу TChart. В результаті, головна форма набуде наступного вигляду.

Далее

Перегляд та редагування полів таблиць бази даних використовуючи компонент TDBEdit

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

Для того, щоб компонент TDBEdit відображав і дозволяв редагувати значення деякого поля набору даних, потрібно встановити для його властивості DataSource, в якості значення, ім'я джерела даних, а для властивості DataField — ім'я поля пов'язаного з цим джерелом набору даних. Зробити це можна за допомогою інспектора об'єктів або програмно. Відмітимо, що яким чином це реалізується в інспекторі об'єктів нами вже було показано при розгляді візуального компонента TDBTetx. Для текстового редактора TDBEdit процес підключення аналогічний: всі компоненти зв'язуються з відповідним полем набору даних через свої властивості DataSource та DataField.

tdbedit_komponent6

Підключення компонента DBEdit1 до поля Kod набору даних Table1 використовуючи інспектор об'єктів

Сьогодні встановимо необхідні значення для цих властивостей програмно. Для цього модифікуємо delphi-проект, що міститься за вказаним вище посиланням таким чином, щок користувач мав змогу не тільки переглядати рядки таблиці cars бази даних autobazar, а і вносити в її полях певні зміни. Отже, відкриємо delphi-проект та видалимо з головної форми всі компоненти типу TDBTetx. Замість них будемо використовувати однорядкові редактори TDBEdit. Для цієї мети на формі розмістимо стільки компонентів, скільки полів ми хочемо переглядати. В нашому випадку необхідно сім компонентів.

Далее

Візуальні компоненти призначені для роботи з базами даними

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

Далее

Знаходження значення функції за побудованим графіком засобами Delphi: Приклад 2

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

Ілюстрація функції графічно

Виходячи з того, що для рішення даної задачі буде використовуватись об'єктно-орієнтована мова програмування Delphi, то, на першому кроці, відкриємо середовище Delphi 7 та створимо новий проект. Після цього, на головній формі розмістимо наступні компоненти: Memo1 типу TMemo, Button1 типу TButton і Chart1 типу TChart. Далі, докладно проаналізувавши побудований графік бачимо, що його доцільно розбити на п'ять частин і розглядати кожну з них окремо. І в залежності від того, яке значення приймає аргумент, обчислювати для відповідної функції.

Далее

Основні властивості та методи компонентів набору даних

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

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

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

Далее

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