графи 3

Графи: 3.6. Радіус і діаметр

Нехай - зв'язний граф. Визначимо відстань між вершинами наступним чином. Якщо ьфхю, тобто число ребер, що міститься в найкоротшій (за кількістю ребер) ланцюга, що з'єднує Тоді для всіх

Для фіксованої вершини ціле число

відповідає відстані від до вершини (або вершин), найбільш віддаленої від Інтуїтивно зрозуміло, що вершина є відносно центральної, якщо відносно мало. Тому природно назвати

радіусом графа і вважати вершину центром графа, якщо

На рис. 3.30, показані графи, які мають відповідно радіуси 1 і 3. Граф може мати кілька центрів. Наприклад, на рис. кожна вершина є центром.

Діаметром зв'язкового графа є максимальна відстань між парами вершин або в символічному записі

Графи, показані на рис. 3.30, мають відповідно діаметри 2 і 3. З другого прикладу видно, що радіус і діаметр зв'язного графа можуть бути рівні.

Поняття радіус, центр і діаметр можуть бути узагальнені на орієнтовані графи певних типів. Якщо ми перевизначити ну) як число дуг в найкоротшому шляху з то потрібно або припустити, що існує шлях з у до для кожної або вважати, що поняття радіусів і діаметрів не визначені для деяких орієнтованих графів. Остання умова можна усунути, вважаючи, що розглядаються тільки сильно зв'язні графи.

Якщо є сильно зв'язковим графом, то радіус, діаметр і центр формально визначаються в точності, як у неорієнтованому випадку при використанні нового визначення Щоб уникнути двозначності, радіус і діаметр в орієнтованому випадку будемо позначати

На рис. 3.31 показаний орієнтований граф отриманий з неорієнтованого графа рис. 3.30, а найбільш невдалою орієнтацією ребер. Неважко бачити, що цей граф сильно зв'язний і що вершини є центрами.

Крім того, і відповідає єдиному простому шляху з Таким чином, в орієнтованому випадку радіус

може бути меншим, ніж діаметр більш ніж удвічі. Це в кінцевому рахунку випливає з асиметрії відстані в орієнтованому випадку. (Зауважимо, наприклад, що на рис. 3.31 ми маємо

Цих кілька незвичайних властивостей можна уникнути, обмежуючи подальший розгляд ще більш вузьким класом зв'язкових, симетричних орієнтованих графів. Для таких графів немає принципової різниці між поняттями орієнтованих радіусів і діаметрів і неорієнтованих. Кожна ланцюг, що з'єднує в неорієнтованому графі, визначає шлях з в відповідному орієнтованому графі (те ж саме відноситься до пари причому ланцюг і шлях мають однакове число дуг. Таким чином, два визначення призводять до однакового чисельним значенням відстані.