У теорії графів діаметр зв'язного неорієнтованого графа є найбільшою відстанню між будь-якими двома його вершинами. Тобто це діаметр множини для множини вершин графа, для найкоротшої відстані в графі. Діаметр може розглядатися як для зважених, так і для незважених графів. Дослідники вивчали проблему обчислення діаметра, як для довільних графів, так і для спеціальних класів графів.
Діаметр незв'язного графа може бути нескінченним або невизначеним.
Графи малого діаметра Задача степеня діаметра шукає тісні зв’язки між діаметром, кількістю вершин і степенем графа. Один із способів її формулювання — пошук найбільшого графа із заданими межами на його степінь та діаметр. Для будь-якого фіксованого степеня максимальний розмір графа є експоненційним у діаметрі, при цьому основа експоненти залежить від степеня.
Обхват графа, довжина його найкоротшого циклу, може бути не більше для графів діаметра . Регулярні графи, для яких обхват рівний є графами Мура. Існує лише скінчена кількість графів Мура, але точна їх кількість невідома. Вони є розв’язками задачі степеня діаметра для своїх степеня та діаметра.
Мережі малого світу — це клас графів із малим діаметром, що моделює феномен реального світу — теорії шести рукостискань у соціальних мережах.
Алгоритми
Для довільних графів Діаметр графа можна обчислити за допомогою алгоритму найкоротшого шляху, а саме обчислити найкоротші шляхи між усіма парами вершин, а потім взяти із них максимум. У графі з додатними вагами ребер це можна зробити, повторно використовуючи алгоритм Дейкстри по одному разу для кожної можливої початкової вершини. У графі із вершин та ребер, такий підхід має часову складність . Обчислення найкоротших шляхів для всіх вершин є найшвидшим відомим методом точного обчислення діаметра для зваженого графа.
У незваженому графі алгоритм Дейкстри може бути замінений пошуком у ширину, що дасть часову складність . Як альтернатива, діаметр можна обчислити за допомогою алгоритму, заснованого на швидкому множенні матриці, тоді час буде пропорційний часу множення матриці, а саме близько використовуючи відомі алгоритми множення матриць. Для розріджених графів із невеликою кількістю ребер повторний пошук у ширину є швидшим, ніж множення матриць. Якщо припустити гіпотезу сильного експоненціального часу, повторний пошук у ширину є майже оптимальним: ця гіпотеза означає, що жоден алгоритм не може досягти часу для будь-якого .
Діаметр зваженого графа можна наближати з точністю до коефіцієнта апроксимації за час , де позначення приховує логарифмічні множники в обмеженні часу. Згідно з гіпотезою про експоненціальний час, неможливо отримати суттєво більш точне наближення, суттєво швидше, ніж обрахунок усіх пар найкоротших шляхів.
Для спеціальних класів графів Діаметр можна обчислити за лінійний час для інтервальних графів і за майже лінійний час для графів з обмеженою шириною дерева. На медіанних графах діаметр можна знайти в межах субквадратичного часу . У будь-якому класі графів, замкнених відносно мінорів графів, таких як планарні графи, можна обчислити діаметр у субквадратичному часі з експонентою, що залежить від сімейства графів.
Дивіться також Триаметр (теорія графів) , діаметр графа Кейлі групи, для генераторів, обраних так, щоб зробити цей діаметр якомога більшим Діаметр графа перемикань , що з'єднує пари тріангуляцій локальними ходами
Список літератури