более одного разу, и пробачимо Ланцюг, если будь-яка вершина орграфа інцідентна НЕ більш чем двом его ребрах.
Визначення. Контуром назівається шлях, качан и Кінець которого збігаються. Контур назівається циклом, если ВІН є Ланцюг, и пробачимо циклом - если це просто ланцюг.
Приклад. Для графа, збережений на рис. 5.11, а, Приклад: орієнтованого ланцюга -; контуру -; циклу -. Для графа, збережений на рис. 5.11, б, Приклад: простого орієнтованого ланцюга -; простого циклу -. При цьом зауважімо, что при запісі циклу як для орієнтованого, так и для неорієнтованого графа, як качаном, так и кінцем может буті звертаючись будь-яка вершина. Наприклад:; и т.п.
Малюнок 5.11 - прикладом ланцюгів и ціклів
Визначення. Для шкірного орієнтованого графа может буті побудованій неорієнтованій граф, такий, что всі вершини ціх графів збігаються, а Кожне ребро (крім петель), стані неорієнтованім ребром графа. У такому випадка граф назівається співвіднесенім графом орієнтованого графа.
Приклад. Для графа, збережений на рис. 5.12, а, співвіднесеній граф буде мати вигляд (рис. 5.12, б):
Малюнок 5.12 - Приклад співвіднесеного графа
Визначення. Вершина назівається досяжною з вершини, если існує шлях з качаном у і кінцем у.
Визначення. Орієнтований граф назівається зв язнім, если его співвіднесеній граф є зв язнім. Орієнтований граф назівається сильно зв'язного, если для будь-якої парі вершин існує орієнтований шлях з, у.
Так, например, граф, збережений на рис. 5.12, а, є зв язнім, альо НЕ є сильно зв язнім.
5.4 Метрика на графах
Визначення. Відстанню между вершинами и графа назівається Мінімальна довжина простого ланцюга з качаном у вершіні и кінцем у вершіні. Если вершини и не з'єднані Ланцюг, тобто належати різнім компонентам, то покладається, що.
У зв'язного графі відстань между вершинами задовольняє Наступний умів:
), и тоді и только тоді, коли;
),;
),.
Функція, что задовольняє трьом перерахованого умів, назівається метрикою графа.
Визначення. Центром графа назівається вершина, від якої максимальна з відстаней до других вершин би була мінімальною.
Визначення. Періферійною цяткою графа назівається вершина, від якої максимальна з відстаней до других вершин би була максимальна.
Визначення. Максимальна відстань від центру графа до его вершин назівається радіусом графа.
Визначення. Найпростішій ланцюг найкоротшої Довжина назівається геодезичній.
Визначення. Відхіленням вершини назівається найбільша довжина геодезічної, яка з неї виходим.
У зв'язку Із ЦІМ можна дати ще одне визначення радіуса графа:
Визначення. Відхилення центру назівається радіусом графа, а Відхилення періферійної точки - діаметром графа.
Алгоритм знаходження відстаней від даної вершини до других вершин графа:
1) позначаємо через;
2) позначаємо індексом всі вершини, суміжні з вершиною, віпісуємо множини всех ціх вершин з їхнімі Позначку;
) шкірних вершину, что НЕ Належить множіні и суміжну з шкірними з вершин, что належати множіні, позначаємо індексом; віпісуємо множини всех ціх вершин з їхнімі Позначку ...;
) повторюємо опис процедур Доті, поки множини непоміченіх вершин не віявіться порожнє.
Приклад. Візначіті відстань від вершини 7 (для зручності записів позначімо вершини графа Арабською цифрами) до всіх вершин графа, збережений на Наступний малюнку.
розв язання. Согласно алгоритмом відстань від вершини 7 будемо шукати в такий способ:
); 2); 3).
Більше непоміченіх вершин немає. Тобто відстані від вершини 7 до кожної з вершин графа Такі:
;.
Для визначення центру и радіуса графа необходимо побудуваті для него матрицю відстаней, КОЖЕН елемент якої опісує відстань между вершинами и графа, тобто. Очевидно, что матриця відстаней симетричного относительно головної діагоналі (елементи якої дорівнюють нулю, тому що).
Приклад. Візначіті центр, Периферійні вершини, радіус и діаметр графа, збережений на на Наступний малюнку.
розв язання.
Матриця відстаней графа має вигляд.
