Запрещенная характеристика графа
-
Основы теории графов
- Семейства графов могут быть описаны набором запрещенных графов.
- Граф является плоским, если не содержит запрещенные графы K5 и K3,3.
-
Понятие сдерживания
- Сдерживание – это гомеоморфизм графов, при котором подграф одного графа отображается как подграф другого.
-
Определение характеристик запрещенных графов
- Запрещенная подструктура – это подграф, который не должен содержаться в графе семейства.
- Подструктуры могут быть подграфами, индуцированными подграфами, гомеоморфными подграфами или минорамы.
-
Использование запрещенных характеристик в алгоритмах
- Запрещенные характеристики могут быть использованы для проверки принадлежности графа семейству.
- Проверка принадлежности графа к семейству может быть выполнена за полиномиальное время.
-
Замкнутость семейств по подструктурам
- Семейство должно быть замкнуто по подструктурам, чтобы иметь запрещенную характеристику.
- Если граф не принадлежит семейству, то все его подструктуры должны быть исключены.
-
Теорема Робертсона-Сеймура
- Для миноров графа семейство с запрещенной характеристикой имеет конечное множество препятствий.
-
Список запрещенных характеристик
- Статья не содержит списка запрещенных характеристик, но упоминает другие связанные проблемы и гипотезы.
Полный текст статьи: