Геодезический график
- Геодезические графы – неориентированные графы с уникальным кратчайшим путем между каждой парой вершин.
- Введение геодезических графов было сделано Эйстейном Оре в 1962 году.
- Примеры геодезических графов включают деревья, полные графы и циклические графы нечетной длины.
- Замена ребер в геодезическом графе приводит к другому геодезическому графику.
- Если каждый двусвязный компонент графа является геодезическим, то и сам граф является геодезическим.
- Геодезические графы могут быть распознаны за полиномиальное время с помощью поиска в ширину.
- Геодезические графы не содержат индуцированных циклических графов с четырьмя вершинами или ромбовидных графов.
- Геодезические графы обладают свойством, что каждое ребро принадлежит уникальной максимальной клике.
- Для графов диаметром два геодезические графы и слабо геодезические графы совпадают.
Полный текст статьи: