Радіус, діаметр і центр графа
Обчислення відстаней і визначення маршрутів у графі є однією з найбільш очевидних і практичних завдань, які виникають в теорії графів. Введемо деякі необхідні визначення.
Ексцентриситет вершини графа - відстань до максимально віддаленої від неї вершини. Для графа, для якого не визначено вагу його ребер, відстань визначається у вигляді числа ребер.
Радіус графа - мінімальний ексцентриситет вершин, а діаметр графа - максимальний ексцентриситет вершин.
Центр графа утворюють вершини, у яких ексцентриситет дорівнює радіусу. Центр графа може складатися з однієї, декількох або всіх вершин графа.
Периферійні вершини мають ексцентриситет, рівний діаметру.
Простий ланцюг з довжиною, що дорівнює діаметру графа, називається діаметральної.
Теорема 12.1.В зв'язкового графі діаметр трохи більше рангу його матриці суміжності.
Теорема 12.2. (Жордана) Кожне дерево має центр, що складається з однієї або двох суміжних вершин.
Теорема 12.3.Еслі діаметр дерева парний, то дерево має єдиний центр, і все діаметральні ланцюга проходять через нього, якщо діаметр непарний, то центрів два і все діаметральні ланцюга містять ребро, їх з'єднує.
Очевидно практичне значення центру графа. Якщо, наприклад, мова йде про графа доріг з вершинами-містами, то в математичному центрі доцільно розміщувати адміністративний центр, складські приміщення і т.п. Цей же підхід можна застосовувати і для зваженого графа, де відстані - це ваги ребер. В якості ваги можна брати Евклідовому відстань, час або вартість пересування між пунктами.
Приклад 12.5. Знайти радіус, діаметр і центр графа, зображеного на рис. 12.1.
Рішення. У цьому завданню зручно використовувати матрицю відстаней S. Елемент цієї квадратної симетричною матриці дорівнює відстані між вершиною i і вершиною j. Для графа, показаного на рис. 12.1, матриця відстаней має наступний вигляд:
Обчислимо ексцентриситет кожної вершини. Цю величину можна визначити як максимальний елемент відповідного стовпця матриці відстаней (або рядки - оскільки матриця S симетрична). отримуємо
Радіус графа r - мінімальний ексцентриситет вершин. В даному випадку r = 2. Такий ексцентриситет мають вершини № 2, № 4 та № 5. Ці вершини утворюють центр графа. Діаметр графа d - максимальний ексцентриситет вершин. В даному випадку d = 3. Такий ексцентриситет мають вершини № 1 і № 3, це периферія графа. У дослідженому графі вершини виявилися або центральними, або периферійними. У графах більшого порядку існують і інші вершини.
Ексцентриситети вершин невеликого графа легко обчислювати безпосереднім підрахунком по малюнку. Однак не завжди граф заданий своїм малюнком. Крім того, граф може мати великий розмір. Тому необхідний інший спосіб вирішення попередньої задачі. Відома наступна теорема.
Теорема 12.4.Пусть - матриця суміжності графа G без петель і, де. Тоді одно числу маршрутів довжини k від вершини до вершини.
Рішення задач теорії графів за допомогою різних перетворень матриці суміжності називають алгебраїчним методом.
Приклад 12.6. Знайти матрицю відстаней графа, зображеного на рис. 12.1, алгебраїчним методом.
Рішення. Матриця суміжності даного графа дорівнює:
Заповнюватимемо матрицю відстаней, розглядаючи ступеня матриці суміжності. Одиниці матриці суміжності показують пари вершин, відстань між якими дорівнює одиниці (тобто вони з'єднані одним ребром).
Діагональні елементи матриці відстаней - нулі. Множимо матрицю суміжності на себе:
Згідно з теоремою між вершинами 2 і 3, 1 і 4 і т.д. є деяка кількість маршрутів довжиною 2 (оскільки ступінь матриці дорівнює двом). Число маршрутів тут не використовується, важливий сам факт наявності маршруту і його довжина, на що і вказує ненульовий елемент ступеня матриці, який не збігається з елементом, зазначеним при обчисленні маршруту меншої довжини. Проставляємо 2 в незаповнені елементи матриці відстаней і отримуємо наступне наближення:
Залишилося невідомим відстань між вершинами 1 і 3. Будемо множити матрицю суміжності саму на себе до тих пір, поки в матриці чи не з'явиться ненульовий елемент. Тоді відповідний елемент матриці відстаней дорівнює ступеню матриці суміжності:. На наступному кроці отримуємо
отже,. і остаточно
Отримана матриця збігається з матрицею відстаней S (12.2), знайденої безпосередніми обчисленнями по малюнку.
Всі теми даного розділу:
Основні визначення
Граф - це сукупність двох множин: вершин
ейлерова ланцюг
Маршрут в Неограф, в якому все ребра різні, називається ланцюгом. Ланцюг в графі називається ейлеровой, якщо вона містить усі ребра і всі вершини графа.
реберний граф
Розглянемо два графа G і L (G). Граф G має довільну форму, а вершини графа L (G) розташовані на ребрах графа G. У цьому випадку граф L (G) називається
Розфарбування графа, хроматичний поліном
Припустимо, що перед нами стоїть завдання: розфарбувати карту світу так, щоб кожна країна мала свій власний колір. Оскільки на світі існує кілька сотень держав, то, природно, потр
Ранг-поліном графа
Ранг графа визначається як. де n - число вершин, k - число компонент зв'язності графа. до
Основні визначення
Ребро в графі G може бути орієнтованим і мати початок і кінець. Таке ребро називається
Маршрути в орграфе
Завдання, пов'язані з маршрутами в орграфе, мають велике практичне значення, що і дає стимул до розвитку і вдосконалення методів їх вирішення. Найбільш часто постає питання про мінімальні і макс
транзитивне замикання
Прямим (декартовим) твором множин A і B називається множина
Компоненти сильної зв'язності графа
Поняття сильної зв'язності відноситься тільки до орграфа. Підстава орграфа - Неограф з тими ж вершинами, але ребрами замість відповідних дуг. орграф називає
Основні визначення
Дерево - зв'язний граф без циклів. Ліс (або ациклічний граф) - Неограф без циклів. Компонентами лісу є дерева.
центроид дерева
Гілка до вершини v дерева - це максимальний підграф, що містить v як висячої вершини. вага
десяткова кодування
Дерева є важливим вид графів. За допомогою дерев описуються бази даних, дерева моделюють алгоритми і програми, їх використовують в електротехніці, хімії. Однією з актуальних завдань