Многогранный граф
-
Определение и характеристики многогранных графов
- Многогранный граф — неориентированный граф из вершин и ребер выпуклого многогранника.
- Альтернативное определение — плоский граф с 3 вершинами.
- Диаграмма Шлегеля представляет вершины и ребра в виде точек и отрезков на плоскости.
- Теорема Балински утверждает, что многогранные графы имеют 3 вершины.
- Теорема Стейница утверждает, что наличие трех вершин и плоскости достаточно для полного описания многогранных графов.
-
Гамильтоновость и краткость
- Тейт предположил, что кубические многогранные графы имеют гамильтонов цикл, но это предположение было опровергнуто.
- Существуют негамильтоновы многогранные графы с меньшим числом вершин и ребер.
- Существует постоянная краткости α < 1 и бесконечное семейство графов с длиной самого длинного простого пути O(nα).
-
Комбинаторное перечисление и особые случаи
- Duijvestijn предоставил подсчет многогранных графов с числом ребер до 26.
- Платоновы тела имеют гамильтоновы циклы и являются симметричными графами.
- Многогранные графы могут быть простыми или симплициальными в зависимости от типа многогранника.
-
Рекомендации
- Ссылки на внешние источники для дополнительной информации.
Полный текст статьи: