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