Розробка програми для поділу граф

Вибір мови програмування, історія Delphi. Граф як множина точок та способи їх з’єднання. Типи матриць, за допомогою яких детально описується орієнтований граф. Дескриптори, користування API функціями. Історія головоломки про Кенігсберзькі мости.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык украинский
Дата добавления 14.09.2012
Размер файла 2,0 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Вступ

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

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

1. Tеоретична частина

Хочу почати з деяких відомостей про історію Delphi щоб пояснити саме такий вибір мови програмування. Turbo Pascal (який ми вивчали на першому курсі) та Borland Pascal були дешевими 16-бітними компіляторами. За роки свого існування, вони пройшли через багато релізів, і в основному використовувалися для створення програм, що виводили інформацію у текстовому режимі. Коли використання графічного інтерфейсу користувача стало необхідним у Microsoft Windows 3.1, було представлено Delphi, розроблене на основі Borland Pascal. Delphi була першою так званою системою швидкої розробки, випущеною у 1995-ому році для 16-бітної Windows 3.1 Delphi 2, представлена роком пізніше, підтримувала 32-бітне Windows-середовище, a версія, що використовувала мову C++ (яку я не використовував у даному проекті), під назвою C++ Builder побачила світ іще кількома роками пізніше. Delphi 7 (на якому власне написаний мій проект), випущена у серпні 2002, навіть зараз вона активно використовується. В Delphi 7 додано підтримку для тем Windows XP (із деяким патчем може бути застосована на Windows 7 якою я власне і користуюся). Також це була остання версія Delphi, яка могла використовуватися без активації. Вона мала лише необов'язкову реєстрацію, яку можна було просто проігнорувати. Delphi 7 є найбільш оціненим програмним середовищем, створеною Borland завдяки своїй стабільності, швидкості і низькими вимогами до апаратного забезпечення. Незважаючи на це у цій версії Delphi, як і у всіх інших, була велика кількість відомих помилок, так і ніколи не виправлених Borland. Завдання виправлення цих помилок компанія залишила на спільноту Delphi (саме один з таких "аматорських" патчів допоміг мені вирішити проблему з деякими функціями BitMap, які не працювали коректно до цього). Ще я характеризую Delphi, як найзручніше і "найпривітніше" щодо користувача у візуальному плані програмне середовище, яке також має не таку високу складність через те,що бере основу з Pascal.

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

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

1 2.

Існують 2 типи матриць за допомогою яких можна детально описати орієнтований граф: матриця суміжності та матриця інциндентності.1) Матриця суміжності графа G зі скінченною кількістю вершин n (пронумерованих числами від 1 до n) - це квадратна матриця A розміру n, в якій значення елементу aij рівне числу ребер з i-ї вершини графа в j-у вершину.

Іноді, особливо у разі неорієнтованого графа, петля (ребро з i-ї вершини в саму себе) вважається за два ребра, тобто значення діагонального елементу aii в цьому випадку рівне подвоєному числу петель навколо i-ї вершини.

Матриця суміжності простого графа (що не містить петель і кратних ребер) є бінарною матрицею і містить нулі на головній діагоналі.

Приклад:

Також на цьому графі ми бачимо петлю - з'єднання ребром однієї і тієї ж вершини.

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

2) Матриця інцендентності - це в матриця в якій вказується зв'язок між інцендетними елементами графу (ребрами (дугами) та вершинами). Стовпці матриці - це вершини,рядки - ребра. Ненульові значення в комірках матриці вказують на зв'язок між ребром там вершиною. Приклад:

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

Орієнтованим графом, або орграфом, G називається пара множин (V,E), де Е (V? V. Елементи множини V називаються вершинами орграфа G, а елементи множини Е (дугами орграфа G = (V,E). Отже, дуга (це впорядкована пара вершин. Відповідно, V називається множиною вершин і Е (множиною дуг орграфа G.

Якщо е= (v,w) (дуга, то вершина v називається початком, а вершина w (кінцем дуги е. Кажуть, що дуга е веде з вершини v у вершину w або виходить з v і заходить у w. Дугу е і вершини v та w називають інцедентними між собою, а вершини v i w суміжними.

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

Маршрутом або шляхом в орграфі G = (V,E) називається послідовність його вершин і дуг v1, e1, v2, e2, …, ek, vk +1 така, що ei = (vi,vi +1), i=1,2,.,k. Кажуть, що цей маршрут веде з вершини v1 у вершину vk +1. Число k дуг у маршруті називається його довжиною.

Маршрут, в якому всі дуги попарно різні, називається ланцюгом. Маршрут, в якому всі вершини попарно різні, називається простим ланцюгом. Маршрут називається замкненим (або циклічним), якщо v1=vk +1. Замкнений ланцюг називається циклом, а замкнений простий ланцюг - простим циклом, або контуром.

Орграф називається ациклічним (або безконтурним), якщо він не має жодного циклу. Якщо існує маршрут, який веде з вершини v у вершину w, то кажуть, що вершина w є досяжною з вершини v. У цьому випадку відстанню d (v,w) від вершини v до вершини w називається довжина найкоротшого маршруту, що веде з v y w. Відстань між вершиною v i вершиною w, яка є недосяжною зv, позначається символом.

1). Відношення досяжності на множині вершин орграфа є транзитивним.

2). Якщо в орграфі G вершина w є досяжною з вершини v, а вершина u є досяжною з вершини w, то d (v,w) +d (w, u)? d (v, u). Вершина v орграфа G називається джерелом, якщо з v є досяжною будь-яка інша вершина орграфа G. Вершина w називається стоком, якщо вона є досяжною з будь-якої іншої вершини орграфа G.

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

Теорема 3.24. Для довільного повного орграфа G = (V,E) з n вершинами виконуються такі рівності (n (1 (? + (vi)) = |E |=n (n-1) /2; (? ( (vi)) 2.

Теорема 3.25. У будь-якому повному орграфі завжди є принаймні одне джерело і принаймні один стік.

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

Послідовність (3.4) називається напівмаршрутом, якщо кожна дуга еі цієї послідовності є такою, що або еi = (vi,vi +1), або ei = (vi +1,vi). (Можна вважати, що при побудові напівмаршруту ми ігноруємо орієнтацію дуг орграфа). Аналогічно означаються напівланцюг, напівцикл і напівконтур.

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

Маршрут в орграфі G назвемо кістяковим, якщо він містить всі вершини орграфа G. Сформулюємо необхідні та достатні умови для кожного з типів а G. Сформулюємо необхідні та достатні умови для кожного з типів зв'язності.

Теорема 3.27. Орграф є сильно зв'язним тоді і тільки тоді, коли він має замкнений кістяковий маршрут.

Теорема 3.28. Орграф є однобічно зв'язним тоді і тільки тоді, коли він має кістяковий маршрут.

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

Неважко переформулювати теореми 3.9 і 3.10, їхні наслідки та алгоритми пошуку вшир і вглиб на випадок різних типів зв'язності орграфів. Ці ж теореми й алгоритми можна пристосувати для обчислення відстаней між вершинами заданого орграфа.

Орграф, у якому є джерело і немає жодного напівконтура, називається кореневим деревом. Вхідне дерево - це орграф, який має стік і не має жодного напівконтура.

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

Тепер я хочу розповісти про Graphics Device Interface або простіше кажучи графіку в Delphi. Graphics Device Interface являє собою інтерфейс, який Windows використовує для малювання 2D графіки. Також це найповільніший спосіб відображення графіки з існуючих, проте найпростіший для розуміння основ. Отже, для початку, поговоримо про основні поняття і терміни у GDI.

Почнемо з того, що GDI зазвичай не використовують для створення крутих графічних ефектів, для цього є DirectX, OpenGL, або будь-які графічні бібліотеки (такі як: DelphiX, FastLib, DIBUltra, Graphics32.). Однак, для створення простих ефектів з мінімальними зусиллями GDI цілком згодиться.

З GDI тісно пов'язана ще одна абревіатура - DC ("Device Context" - контекст пристрою). Це те, на чому ми малюємо, і в Delphi контекст пристрою представлений як TCanvas. Ідея контексту пристрою полягає в тому, що це універсальний пристрій виводу, тому можна використовувати однакові функції як для екрану, так і для принтера.

Всі графічні функції в Delphi є надбудовами над стандартними GDI функціями Windows. Пізніше ми поговоримо про ці функції.

Pen Використовується для малювання простих ліній. Зазвичай застосовується для функції LineTo або при малюванні рамки для певної фігури (наприклад для функції Rectangle).

Brush Кисть використовується для заповнення області певним кольором. Застосовується у функціях Rectangle, FillRect або FloodFill.

Font Використовується для завдання шрифту, яким буде намальований текст. Можна вказати ім'я шрифту, розмір і т.д.

Region Дозволяє задати регіон (замкнутий простір). Регіоном може бути коло, квадрат або довільна фігура. Дозволяє так само робити дірки у фігурах.

Спершу необхідно чітко усвідомити, що координата (0,0) це верхній лівий кут екрану. Тобто значення по осі y збільшуються вниз екрану. Відповідно, координата (0, 50) означає, що ми просто відступили на 50 пікселів від верху екрана.

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

Нижче наведено дві функції, які використовуються для малювання ліній і обидві належать TCanvas: Ім'я Опис Приклад

MoveTo Переміщає точку початку малювання лінії у зазначені координати x і y Canvas. MoveTo (50, 100);

LineTo Малює лінію починаючи з поточної позиції (див. MoveTo) до зазначених координат x та y. Canvas. LineTo (50, 100);

Ефект переміщення точки початку малювання лінії так само досягається за допомогою установки своства PenPos в канвасе. наприклад, "Canvas. PenPos. x: = 20;", "Canvas. PenPos. y: = 50", або "Canvas. PenPos: = Point (20,50);".

За замовчуванням, точка початку малювання встановлена в (0,0), тобто, якщо відразу викликати "Canvas. LineTo (100,100); " то буде намальована лінія з точки (0,0) в точку (100, 100). Точка початку малювання автоматично переміститься в (100, 100), тобто, якщо виконати команду "Canvas. LineTo (200, 100);", то наступна лінія буде намальована з точки (100, 100) в (200, 100). Тому, якщо ми хочемо малювати лінії нез'єднаних один з одним, то доведеться скористатися методом MoveTo.

Лінія, намальована за допомогою LineTo використовує поточне перо в Сanvas (типу TPen). Основні властивості пера, це ширина - "Canvas. Pen. Width: = 4; " (за допомогою якого можна задавати різну ширину ліній), і колір "Canvas. Pen. Color: = clLime;".

Погляньмо на простий приклад безладного малювання різнокольорових ліній:

procedure TForm1. FormCreate (Sender: TObject);

begin

// инициализируем генератор

// случайных чисел Randomize;

end;

const NUM_LINES = 2000;

procedure TForm1. DrawLines;

var

i: Integer;

begin

for i: = 0 to NUM_LINES - 1 do

begin

Canvas. Pen. Color: = RGB (Random (256), Random (256), Random (256)); Canvas. LineTo (Random (ClientWidth),Random (ClientHeight));

end;

end;

Процедура DrawLines викликається з обробника кнопки OnClick. Кількість ліній задається в константі NUM_LINES. Між іншим, функція RGB, становить колір кожної лінії із трьох основних складових: червоного, зеленого і синього (значення від 0 до 255) і повертає нам колір у вигляді TColor.

Для малювання фігур, в TCanvas передбачені наступні функції:

Ellipse Малює еліпси, вписаний в невидимий квадрат з координатами верхнього лівого кута і правого нижнього. Якщо координати х і y у кутів будуть збігатися, то вийде коло. Canvas. Ellipse (0,0,50,50);

FillRect Заповнює прямокутник кольором поточної кисті (brush), але ніяк не за межами нього. Canvas. FillRect (Bounds (0,0,100,100));

FloodFill Заповнює дану область кольором поточної кисті, до тих пір поки не буде досягнутий край. Canvas. FloodFill (10, 10, clBlack, fsBorder);

Rectangle Малює прямокутник (або квадрат), заповнений кольором поточної кисті і обрамлений кольором поточного пера Canvas. Rectangle (Bounds (20, 20, 50, 50));

RoundRect Теж, що і Rectangle, але з загругленнимі кутами. Canvas. RoundRect (20, 20, 50, 50, 3,3);

Ще є дуже потрібна функція TextOut, яка дозволяє малювати текст, використовуючи шрифт, заданий в Canvas:

TextOut Малює дану рядок на канвасе починаючи з координат (x, y) - фон тексту заповнюється поточним кольором кисті. Canvas. TextOut (10, 10, 'Some text');

До речі, функція дозволяє малювати текст, не заповнюючи його фон. Якщо Вам необхідно змінити шрифт, використовуваний в TextOut, то необхідно змінити властивість Font Canvas (ця властивість має тип TFont) - наприклад "Canvas. Font. Name: = 'Verdana';", "Canvas. Font. Size: = 24; " або "Canvas. Font. Color: = clRed;".

Коротенько хотілося б звернути Вашу увагу на досить корисний клас TRect, який вміє зберігати в собі значення ліво, право, верху і низу (до речі, в Windows API це RECT). Те їсть, досить вказати ліву і верхню координату і ширину і висоту області, а TRect автоматично підставить у вигляді (ліво, верх, ліво + ширина, верх + висота). Ще є інша функція Rect (), яка робить те саме, але координати в ній задаються безпосередньо як ліво, право, верх і низ. Ну і за бажанням, можна використовувати API функцію SetRect.

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

Малювання, це те, що ми робили вище. Тобто, малювали будь-які лінії і графічні фігури. Однак, малюнок зберігався до тих пір, поки вікно (форма) не було оновлено.

Перемальовування дещо відрізняється від поняття "малювання". Коли вікна необхідно перемальовувати, то Windows посилає певне повідомлення. Це повідомлення надходить в обробник події "OnPaint". Будь-який код, який помістити в обробник OnPaint буде викликаний кожен раз, коли формі необхідно оновитися.

Дескриптори, або як користуватися аналогічними API функціями.

Отже, ми навчилися малювати лінії, різні фігури, навчилися робити так, щоб наше творіння не стиралася при переміщенні форми, і виконали ми все це за допомогою стандартних функцій VCL (таких як Canvas. TextOut і т.д.). Однак, що робити, якщо Ви не хочете користуватися графічними функціями VCL, які всього на всього є надбудовами над аналогічними функціями з Windows API? Будь ласка! Ніхто нам не забороняє користуватися API функціями безпосередньо! Але постійте-ка, всі вони вимагають якогось HDC! Що таке HDC?

Майже все в Windows використовує "Дескриптор" (Handle). Дескриптор, це спосіб ідентифікації Вашого об'єкта в системі. У кожного вікна є свій дескриптор, у кожної кнопки теж є свій дескриптор і т.д. Саме тому всі наші об'єкти мають дескриптор в якості властивості - наприклад, "MyForm. Canvas. Handle".

Тип HDC це Дескриптор (Handle) Контексту Прилади (Device Context). Я вже говорив на самому початку, що TCanvas включає в себе більшість функцій DC. Тому, ми спокійно можемо підставляти властивість канвасе Handle скрізь, де нам це потрібно.

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

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

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

Бітмапами можна малювати не тільки на формі, а й по всьому екрану. Може це і може здатися трохи дивним, але іноді це буває корисно, особливо при створенні скрінсейвера.

TCanvas має кілька корисних функцій, які працюють з типом TGraphic. Тип TGraphic є базовим класом для графічних об'єктів у Delphi, таких як: бітмапами (TBitmap), іконки (TIcon), метафайли (TMetafile) і JPEG-і (TJPEGImage). Всі вони використовують одні і ті ж функції.

Всі ці функції є методами TCanvas.

Draw Малює TGraphic на канвасе так як він є, не розтягуючи. Canvas. Draw (5,10, MyGraphic);

StrechDraw Малює TGraphic на Canvas, підганяючи (розтягуючи) його під задану область. Canvas. StretchDraw (Bounds (0,0,32,32), MyGraphic);

CopyRect Копіює частина TCanvas-а в іншій, при необхідності розтягуючи його. Canvas. CopyRect (Bounds (0,0,32,32), MyBmp. Canvas, Bounds (0, 0, 640, 480));

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

2. Спеціальна частина

Я хотів би почати власне з історії головоломки про Кенігсберзькі мости. Здавна у жителів Кенігсбергу (сучасного Калінінграду) була розповсюджена така загадка: як пройти по всім мостам, не проходячи ні по одному з мостів два рази? Багато жителів Кенігсбергу намагалися вирішити цю головоломку, як теоретично так і практично, під час прогулянок містом. Але нікому так і не вдалося, а що найцікавіше що й не вдалося довести теоретично що це - неможливо.

В 1736 році головоломка про сім мостів Кенігсбергу зацікавила відомого математика, члена Петербурзької академії наук Леонарда Ейлера, про що він і написав у листі італійському математику і інженеру Маріоні від 13 березня 1736 року. В цьому листі Ейлер писав про те, що він зміг знайти правило завдяки якому він зміг би легко побачити, чи можливо пройти всі мости, не проходячи один і той же два рази (у випадку Кенігсберзьких мостів це неможливо)

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

1) Число непарних вершин (вершин до яких іде непарне число ребер) граф завжди парне. Неможливо намалювати граф, який мав би непарне число непарних вершин

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

3) Граф с більш ніж двома непарними вершинами неможливо накреслити за один раз

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

програма граф матриця delphi

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

На карті старого Кенігсберга був ще один міст, що з'явився трохи пізніше, і що з'єднував острів Ломзе з південного боку. Своїй появі цей міст зобов'язаний самої задачі Ейлера-Канта. А сталося це ось як. Імператор Кайзер Вільгельм славився своєю прямотою, простотою мислення і солдатської "недальнобачністью".

Одного разу, перебуваючи на світському рауті, він мало не став жертвою жарту, яку з ним вирішили зіграти вчені уми, присутні на прийомі. Вони показали Кайзерові карту Кенігсберга, і попросили спробувати вирішити цю знамениту задачу, яка за визначенням була нерозв'язною. На загальний подив, Кайзер попросив перо та аркуш паперу, сказавши, що вирішить завдання за півтори хвилини. Приголомшений німецька світська громада, не могла повірити своїм вухам, але папір і чорнило швидко знайшли. Кайзер поклав аркуш на стіл, узяв перо, і написав: "наказую побудувати восьмий міст на острові Ломзе". Так у Кенігсберзі і з'явився новий міст, який так і назвали - міст Кайзера. А завдання з вісьмома мостами тепер міг вирішити навіть дитина.

3

4

2.1 Постановка задачі

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

Наступним кроком було саме зобразити граф. Я зробив це 2ма способами:

1) По кроково на Canvas

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

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

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

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

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

Перебиралися різні варіанти з'єднання.

with Image1. Picture. Bitmap do begin

for i: =1 to 1000 do begin

rx: =Random (Width);

ry: =Random (Height);

if Canvas. Pixels [rx, ry] = clWhite then begin

Canvas. Brush. Color: =RGB (RegionCount + 1, 0, 0) and $000000FF;

Canvas. FloodFill (rx, ry, clBlack, fsBorder);

SetLength (Coords, Length (Coords) + 1);

Coords [Length (Coords) - 1]: =Point (rx, ry);

Inc (RegionCount);

end;

end;

end;

if RegionCount = 0 then Exit;

Потім ми знову перераховуемо регіони але вже до 100000. Це і буде така собі специфічна корекція данних

with Image1. Picture. Bitmap do begin

for i: =1 to 100000 do begin

rx: =Random (Width - BorderSize + 4) + Diff;

ry: =Random (Height - BorderSize + 4) + Diff;

if Canvas. Pixels [rx, ry] = clBlack then begin

ColorCount: =0;

for j: =0 to RegionCount - 1 do aColors [j]: =clBlack;

for cx: =rx - Diff to rx + Diff do begin

for cy: =ry - Diff to ry + Diff do begin

cc: =Canvas. Pixels [cx, cy];

if cc <> clBlack then begin

b: =False;

for j: =0 to ColorCount - 1 do b: =b or (aColors [j] = cc and $000000FF);

if not b then begin

Inc (ColorCount);

aColors [ColorCount - 1]: =cc and $000000FF;

end;

end;

end;

end;

for j: =0 to ColorCount - 2 do begin

for k: =j + 1 to ColorCount - 1 do begin

if (aColors [j] <= RegionCount) and (aColors [k] <= RegionCount)

then begin

Matrix [aColors [j] - 1, aColors [k] - 1]: =1;

Matrix [aColors [k] - 1, aColors [j] - 1]: =1;

end;

end;

end;

end;

end;

end;

Це було певне найцікавіша частина мого, так би мовити додаткового проекту. Тепер цей проект може в картографії для поділу регіонів. У подальшому його можна буди використовувати у соціології якщо додати до нього поділ регіонів на певні данні наприклад людей які мають вищу освіту в Україні наведений нижче. А якщо все таки виконати мою ідею по будування графів по маршруту який ми будемо малювати вже у вкладеному програму Paint Box (який зараз не використовується у моєму проекті) і буде активно використовуватися у побудові доріг.

2.1 Опис алгоритму та ідентифікатори

Тут я хотів описати алгоритм малювання першим способом та алгоритм мого власного доповнення:

1) Алгоритм малювання графу про головоломку першим способом:

2) Алгоритм мого власного додатку

2.2 Інструкція по експлуатації

Коли ми запускаємо програму перший раз нас зустрічає такий інтерфейс складаючись з власне форми та меню.

Щоб перейти до саме малювання графу нам потрібно перейти: Головне меню=>Файл=>Намалювати=>і вибираємо 1 спосіб

Тут вже нас зустрічає вже знайомий інтерфейс

Вже тут ми знову виберемо Головне меню=>Файл=>Нарисовать тут зразу з'являються кнопки - кроки

1) крок 1 - малюються подвійні дуги А та В

2) крок 2 - малюються подвійні дуги А та С

3) Крок 3 - ребро від В до D

4) крок 4 - ребро від С до D

5) крок 5 (остній крок) - ребро від A до D

Після того як ми намалювали ми закриваємо вікно Головне меню=>Файл=>Вихід

Повернемося до головного вікна якщо ми виберемо спосіб 2 то нам зразу виведеться це вікно

Якщо хочемо побачити масив треба натиснути на головному вікні

Головне меню=>Файл=>Описати масивом і на виводиться ось такий масив

Тепер давайте перейдемо до мого додатку для цього треба на головному вікні натиснути Головне меню=>Файл=>Описати масивом=Граф по регіонам і ми побачимо ось таке вікно

Тепер малюємо карту в Paint і вставляємо її в програму натискаючи кнопку "Отрыть карту" після цього бачимо це:

Тепер натискаємо кнопку "Построить граф" і бачимо такий масив у правій верхній частині екрану

Тепер треба перевірити чи правильно програма вибрала регіони. Для цього ми натискаємо кнопку "Закрасить" і бачимо це:

Потім натискаємо кнопку "Нарисовать граф" і в нас по малюнку малюється граф і бачимо це:

І тепер ми можемо зберегти даний малюнок кнопкою "Сохранить"

Для виходу натискаємо кнопку "Вихід"

2.3 Висновок

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

Список літератури

1) "Дискретная математика" Асанов М. О

2) "Дискретная математика для програмистов" Новико Ф. А

3) "Графи в програмирование: обработка, визуализация и пременение" В.Н. Касьянов

4) "Введение в теорию графов" Уилсон Р.

Размещено на Allbest.ru


Подобные документы

  • Визначення та способи представлення графів. Основні алгоритми на графах. Побудова мінімального остового дерева. Алгоритми Прима та Дейкстри. Модель Флойда-Уоршалла. Огляд можливостей мови програмування. Опис функцій програмної моделі, інтерфейс програми.

    дипломная работа [563,7 K], добавлен 03.08.2014

  • Разработка и реализация универсальной программной коллекции для абстрактного типа данных (АТД) "Простой статический граф" с графическим интерфейсом. Особенности использование ее для решения задач для неориентированных, ориентированных и взвешенных графов.

    курсовая работа [502,3 K], добавлен 24.09.2013

  • Прототип об'єктно-орієнтованого програмування. Управління процесом реалізації програми. Розвиток апаратних засобів. Об'єктно-орієнтовані мови програмування. Надійність і експлуатаційні якості програм. Візуальне об’єктна-орієнтовне проектування Delphi.

    контрольная работа [28,9 K], добавлен 18.05.2009

  • Програми і мови програмування. Алфавіт мови програмування. Лексеми, зарезервовані слова мови Pascal. Ідентифікатори, типи даних. Арифметичні вирази, операції. Стандартні функції, структура програми. Процедури введення-виведення. Правила написання команд.

    лекция [445,0 K], добавлен 24.07.2014

  • Поняття черги в програмуванні, основні операції з чергою і їх реалізація. Опис алгоритму й специфікація програми. Розробка додатку з використанням задачі Ларсона по опису зв'язного неорієнтованого графа. Алгоритм розв’язку і результати виконання програми.

    курсовая работа [1,1 M], добавлен 14.09.2012

  • Прості та умовні оператори мови С++. Робота з двовимірними масивами. Пошук та сортування даних. Робота з файлами та з динамічними структурами даних. Опис мови програмування Delphi. Складення програми до розроблених алгоритмів. Організація циклів.

    отчет по практике [4,3 M], добавлен 28.08.2014

  • Задача об оптимальном графе для децентрализованного поиска. Жадный алгоритм. Модель Клайнберга. Математическая модель. Алгоритмы решения. Алгоритм локального поиска. Табу алгоритм. Метод ветвей и границ. Выбор между одинаковыми соседями. Стартовый граф.

    дипломная работа [4,1 M], добавлен 23.10.2016

  • Модель аналізу-синтезу компіляції. Формальний опис вхідної мови програмування. Вибір технології програмування, проектування таблиць транслятора та вибір структур даних. Опис програми реалізації лексичного аналізатора. Розробка дерев граматичного розбору.

    курсовая работа [75,8 K], добавлен 26.12.2009

  • Побудування блок-схеми рішення завдання зі знайдення центра ваги однорідної усіченої призми. Розробка програми за допомогою язика програмування C++, опис змінних та функцій програми та загальної математичної моделі. Розробка інструкції користувача.

    курсовая работа [1,1 M], добавлен 04.01.2012

  • Аналіз особливостей мови програмування Java та середовища Android Studio. Розробка програмного забезпечення для якісного та ефективного вивчення іноземних слів. Побудова базових алгоритмів і структури даних. Вибір мови програмування, реалізація програми.

    курсовая работа [335,3 K], добавлен 11.01.2015

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.