Діаметр (теорія графів)

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

Діаметри незважених і зважених графів

Діаметр незв'язного графа може бути нескінченним або невизначеним.

Графи малого діаметра

Задача степеня діаметра шукає тісні зв’язки між діаметром, кількістю вершин і степенем графа. Один із способів її формулювання — пошук найбільшого графа із заданими межами на його степінь та діаметр. Для будь-якого фіксованого степеня максимальний розмір графа є експоненційним у діаметрі, при цьому основа експоненти залежить від степеня. ^[1]

Обхват графа, довжина його найкоротшого циклу, може бути не більше ${\displaystyle 2k+1}$ для графів діаметра ${\displaystyle k}$. Регулярні графи, для яких обхват рівний ${\displaystyle 2k+1}$ є графами Мура. Існує лише скінчена кількість графів Мура, але точна їх кількість невідома. Вони є розв’язками задачі степеня діаметра для своїх степеня та діаметра. ^[2]

Мережі малого світу — це клас графів із малим діаметром, що моделює феномен реального світу — теорії шести рукостискань у соціальних мережах. ^[3]

Алгоритми

Для довільних графів

Діаметр графа можна обчислити за допомогою алгоритму найкоротшого шляху, а саме обчислити найкоротші шляхи між усіма парами вершин, а потім взяти із них максимум. У графі з додатними вагами ребер це можна зробити, повторно використовуючи алгоритм Дейкстри по одному разу для кожної можливої початкової вершини. У графі із ${\displaystyle n}$ вершин та ${\displaystyle m}$ ребер, такий підхід має часову складність ${\displaystyle O(mn+n^{2}\log n)}$. Обчислення найкоротших шляхів для всіх вершин є найшвидшим відомим методом точного обчислення діаметра для зваженого графа. ^[4]

У незваженому графі алгоритм Дейкстри може бути замінений пошуком у ширину, що дасть часову складність ${\displaystyle O(mn)}$. Як альтернатива, діаметр можна обчислити за допомогою алгоритму, заснованого на швидкому множенні матриці, тоді час буде пропорційний часу множення ${\displaystyle n\times n}$ матриці, а саме близько ${\displaystyle O(n^{2.37})}$ використовуючи відомі алгоритми множення матриць. ^[5] Для розріджених графів із невеликою кількістю ребер повторний пошук у ширину є швидшим, ніж множення матриць. Якщо припустити гіпотезу сильного експоненціального часу, повторний пошук у ширину є майже оптимальним: ця гіпотеза означає, що жоден алгоритм не може досягти часу ${\displaystyle O(n^{2-\varepsilon })}$ для будь-якого ${\displaystyle \varepsilon >0}$. ^[4]

Діаметр зваженого графа можна наближати з точністю до коефіцієнта апроксимації ${\displaystyle 3/2}$ за час ${\displaystyle {\tilde {O}}(\min(m^{3/2},mn^{2/3})}$, де позначення ${\displaystyle {\tilde {O}}}$ приховує логарифмічні множники в обмеженні часу. ^[6] Згідно з гіпотезою про експоненціальний час, неможливо отримати суттєво більш точне наближення, суттєво швидше, ніж обрахунок усіх пар найкоротших шляхів. ^[4]

Для спеціальних класів графів

Діаметр можна обчислити за лінійний час для інтервальних графів ^[7] і за майже лінійний час для графів з обмеженою шириною дерева. ^[8] На медіанних графах діаметр можна знайти в межах субквадратичного часу ${\displaystyle {\tilde {O}}(n^{1.6456})}$. ^[9] У будь-якому класі графів, замкнених відносно мінорів графів, таких як планарні графи, можна обчислити діаметр у субквадратичному часі з експонентою, що залежить від сімейства графів. ^[10]

Дивіться також

• Триаметр (теорія графів)
• Діаметр (теорія груп)^[en], діаметр графа Кейлі групи, для генераторів, обраних так, щоб зробити цей діаметр якомога більшим
• Діаметр графа перемикань , що з'єднує пари тріангуляцій локальними ходами