Теорія графів
Теорія графів - це один з підрозділів математики, головною відмітною прізнакомкоторого є геометричний метод у вивченні об`єктів. Засновником її прийнятовважати відомого математика Л. Ейлера.
Застосування теорії графів до кінця 19 століття зводилося до вирішення цікавих завдань і не привертало значного загальної уваги. Починаючи з 20 століття, коли теорія графів сформувалася в самостійну математичну дисципліну, вона знайшла широке застосування в таких областях науки, як кібернетика, фізика, логістика, програмування, біологія, електроніка, транспортні та комунікаційні системи.
Основні поняття теорії графів
Базовим є граф. У термінології можна зустріти таке поняття, як мережа, ідентичне графу. Останнє - це непорожня кількість точок, тобто вершин, і відрізків, тобто ребер, обидва кінці яких відповідають заданій кількості точок. Теорія графів не вкладає певного сенсу в значення ребер і вершин. Наприклад, міста і з`єднують їх дороги, де перші - це вершини графа, а другі - ребра. Більше значення в теорії приділяється дуг. Якщо у ребра є напрям, то воно має назву дуги, якщо граф з орієнтованими ребрами, він називається Орграф.
У термінології теорії так само виділяють такі поняття:
Подграфом називається граф, всі ребра і вершини якого знаходяться серед вершин і ребер.
Зв`язний граф - той, у якого для двох різних вершин існує з`єднує їх ланцюг.
Зважений зв`язний граф - той, у якого задана вагова функція.
Дерево - зв`язний граф, без циклів.
Остов - підграф, що є деревом.
При зображенні графа на площині використовується певна система позначень: обраної вершині відповідає точка на найпростішої поверхні, і якщо між вершинами знаходиться ребро, то відповідні точки об`єднуються відрізком. Якщо ж граф орієнтований, ці відрізки замінюються стрілками.
Але не варто порівнювати зображення графа з ним самим, тобто з абстрактної структурою, тому що одному графу можна надати не одне графічне представлення. Малюнок на площині дано для того, щоб побачити, які пари вершин об`єднуються ребрами, а які ні.
Серед деяких задач теорії графів виділяють:
- Завдання про найкоротші ланцюга (заміна обладнання, розміщення місць швидкої допомоги і телефонних станцій).
- Завдання про максимальний потік (впорядкування руху в динамічної мережі, розподіл робіт, організація пропускної здатності).
- Завдання про покриттях і упаковках (розміщення диспетчерських пунктів).
- Розфарбування в графах (розміщення пам`яті на електронно-обчислювальних машинах).
- Зв`язок мереж і графів (створення комунікаційної мережі, аналіз мереж зв`язку).
В даний час неможливо програмувати більшість завдань без знання теорії графів. Це полегшує і спрощує роботу з ЕОМ.
Програмування використовує безліч структур і універсальних методів для вирішення завдань, і одним з них є теорія графів. Її значення важко переоцінити. Теорія графів в програмуванні дозволяє спростити пошук інформації, оптимізувати програми, перетворити і розподілити дані. Завдяки алгоритмам теорії виникає можливість застосування і їх оцінки в використанні для вирішення конкретних завдань, здійснювати модифікацію алгоритму, не зменшуючи її ступеня математичної достовірності кінцевого варіанту програми.
Важливим властивістю керуючої системи або моделі є сукупність бінарних відносин при наборі дій і одиниць даних. Ці структури є єдиними частинами програм і перетвориться ними інформації. Тому графи є основою конструкцією для програміста.
