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