Теорія графів

Теорія графів - це один з підрозділів математики, головною відмітною ознакою якого є геометричний метод у вивченні об`єктів. Засновником її прийнято вважати відомого математика Л. Ейлера.

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

Основні поняття теорії графів

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

У термінології теорії так само виділяють такі поняття:

Подграфом називається граф, всі ребра і вершини якого знаходяться серед вершин і ребер.

Зв`язний граф - той, у якого для двох різних вершин існує з`єднує їх ланцюг.

Зважений зв`язний граф - той, у якого задана вагова функція.

Дерево - зв`язний граф, без циклів.

Остов - подграф, що є деревом.

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

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

Серед деяких задач теорії графів виділяють:

1. Завдання про найкоротші ланцюга (заміна обладнання, розміщення місць швидкої допомоги та телефонних станцій).
2. Завдання про максимальний потік (упорядкування руху в динамічної мережі, розподіл робіт, організація пропускної спроможності).
3. Завдання про покриттях і упаковках (розміщення диспетчерських пунктів).
4. Розфарбування в графах (розміщення пам`яті на електронно-обчислювальних машинах).
5. Зв`язок мереж і графів (створення комунікаційної мережі, аналіз мереж зв`язку).

В даний час неможливо програмувати більшість завдань без знання теорії графів. Це полегшує і спрощує роботу з ЕОМ.

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

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