Правильне розфарбування вершин графа в середовищі програмування delphi

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

Отже, головна форма розробленого delphi-проекту складається з панелі інструментів, графічного редактора та області виводу резільтатів.

Головне вікно проекту "Розфарбування вершин графа"

  1. Панель інструментів (компонент типу TPanel): містить чотири кнопки: «Додати вершину» (типу TSpeedButton), «Додати ребро» (типу TSpeedButton), «Видалити граф» (типу TButton) та «Знайти правильне розфарбування графа» (типу TButton). Відмітимо, що серед зазначених кнопок, три відповідають за процес побудови та видалення графа і четверта — реалізує процес розфарбування його вершин (відмітимо, що для реалізації задуманого використовується переборний алгоритм).
  2. Графічний редактор (компонент типу TImage): призначений для побудови та візуалізації неорієнтованого графа, а також візуалізації правильного розфарбування його вершин.
  3. Область виводу результатів (компонент типу TMemo): призначена для виводу мінімального числа кольорів, необхідних для правильного розфарбування графа.

Далее

Периметр і площа трикутника

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

В окремому випадку, для рівностороннього трикутника, дана формула прийме наступного вигляду: . Тобто, довжина сторони, помножена на три. Якщо трикутник буде рівнобедренним, то формула може бути записана у вигляді: , де  — бічні сторони трикутника і  — основа.

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

Площа трикутника дорівнює половині добутку його сторони та проведеної до неї висоти. Для доведення даного твердження, розглянемо трикутник і його висоту . Покажемо, що .

Площа трикутника дорівнює половині добутку його сторони та проведеної до неї висоти

Для цього, через вершини і трикутника проведемо прямі, паралельні сторонам  і відповідно. Нехай ці прямі перетинаються в точці . Чотирикутник  — паралелограм за означенням. Трикутники  і рівні ( та , як протилежні сторони паралелограма і  — спільна). Отже, їх площі також рівні. Тоді, площа трикутника дорівнює половині площі паралелограма . Висота  трикутника  є також висотою паралелограма . Звідси, .

Далее

Види трикутників. Співвідношення між кутами і сторонами трикутника

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

Зображення різностороннього трикутника

Зауваження: виходячи з того, що сторони трикутника утворюють у його вершинах три кути, то трикутник можна також визначити як багатокутник, у якого є рівно три кути.

Залежно від довжин сторін трикутника (довжин відрізків) та величини кутів між ними, виділяють різні види трикутників. Розглянемо характерні ознаки кожного з них.

Далее

Квадрат. Означення квадрата та його властивості

Квадратом називають прямокутник, у якого всі сторони рівні. На рисунку що міститься нижче, зображено квадрат діагоналі якого перетинаються в точці (діагональ квадрата — це відрізок, що з'єднує протилежні кути квадрата і проходить через його центр).

Властивості квадрата

Зображення квадрата та його діагоналей

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

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

Далее

Площа та периметр прямокутника

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

Зображення прямокутника

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

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

Далее

Ромб та його властивості

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

Зображення ромба та його діагоналей

З означення випливає, що ромб має всі властивості паралелограма (протилежні кути ромба рівні, діагоналі ромба точкою перетину діляться навпіл) і, крім того, діагоналі ромба перпендикулярні і є бісектрисами його кутів.

Для доведення властивостей, які є притаманними лише ромбу, розглянемо його зображення з рисунка вище, і покажемо, що і .

Далее

Формули для обчислення периметра та площі паралелограма

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

Периметр паралелограма

Периметр паралелограма дорівнює сумі кожної з його сторін

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

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

Далее

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