Оглавление
Встраивание графа
-
Определение и свойства вложения графа
- Вложение графа G на поверхности Σ – это представление графа, в котором вершины и ребра связаны с точками и дугами поверхности.
- Вложение должно удовлетворять условиям непересечения ребер и отсутствия точек, связанных с другими вершинами.
- Вложение графа в трехмерное евклидово пространство R3 возможно для любого конечного графа.
-
Род графа и его классификация
- Род графа – это минимальное целое число n, такое что граф может быть встроен в поверхность рода n.
- Плоский граф имеет род 0, а граф, который может быть встроен в тор, называется тороидальным.
- Эйлеров род графа – это минимальное целое число n, такое что граф может быть встроен в ориентируемую или неориентируемую поверхность рода n/2.
- Ориентируемо простой граф – это граф с эйлеровым родом меньше неориентируемого рода.
- Максимальный род графа – это максимальное целое число n, такое что граф может быть вложен в поверхность рода n.
-
Комбинаторное вложение и его эквивалентности
- Комбинаторное вложение – это вложение с фиксированной системой вращения ребер.
- Эквивалентные вложения имеют одинаковую систему вращения ребер.
- Существуют другие эквивалентные представления для комбинаторных вложений, включая ленточный граф и карту с кодировкой графа.
-
Вычислительная сложность и примеры
- Задача определения рода графа является NP-полной.
- Существуют алгоритмы для проверки возможности вложения графа в поверхность заданного рода и для нахождения такого вложения.
- Примеры вложений включают книжное вложение графа и бессвязное вложение.
-
Встраивание графов в многомерные пространства
- Любой конечный граф может быть вложен в трехмерное пространство.
- Существуют различные способы вложенности графа в трехмерное пространство, включая книжное вложение и бессвязное вложение.
Полный текст статьи: