Порождённый подграф
Порождённый подграф графа — это другой граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.
Определение
Формально, пусть G = (V, E) — любой граф, и пусть S ⊂ V — подмножество вершин графа G. Тогда порождённый подграф G[S] — это граф, вершинами которого являются элементы S, а рёбра которого состоят из всех рёбер из множества E, конечные вершины которых принадлежат S[1]. Одно и то же определение подходит для неориентированных графов, ориентированных графов и даже для мультиграфов.
Порождённый подграф G[S] может быть также назван подграфом, порождённым в G набором вершин S или (если контекст не приводит к двусмысленности) порождённым подграфом вершин S.
Примеры
Важными типами подграфов являются следующие:
- порождённые пути — это порождённые подграфы, являющиеся путями. Кратчайший путь между любыми двумя вершинами в невзвешенном графе всегда является порождённым путём. Обратно, в дистанционно-наследуемых графах любой порождённый граф является кратчайшим путём[2].
- Порождённые циклы — это порождённые подграфы, являющиеся циклами. Обхват графа определяется длиной его кратчайшего цикла, который всегда является порождённым циклом. Согласно строгой теореме о совершенных графах порождённые циклы и их дополнения играют критическую роль в характеризации совершенных графов[3].
- Клики и независимые множества являются порождёнными подграфами, которые являются полными подграфами или графами без рёбер соответственно.
- Окрестность вершины — это порождённый подграф всех смежных вершин выбранной вершины.
Вычисление
Задача изоморфизма порождённых подграфов является видом задачи поиска изоморфного подграфа, в которой целью является проверка, может ли один граф быть найден как порождённый подграф другого графа. Поскольку эта задача включает задачу о клике как частный случай, она NP-полна[4].
Примечания
- Diestel, 2006, с. 3–4.
- Howorka, 1977, с. 417–420.
- Chudnovsky, Robertson, Seymour, Thomas, 2006, с. 51–229.
- Johnson, 1985, с. 434–451.
Литература
- Reinhard Diestel. Graph Theory. — Springer-Verlag, 2006. — Т. 173. — С. 3–4. — (Graduate texts in mathematics). — ISBN 9783540261834.
- Рейнгард Дистель. Теория графов. — Новосибирск: Издательство Института математики, 2002. — ISBN 5-86134-101-X.
- Edward Howorka. A characterization of distance-hereditary graphs // The Quarterly Journal of Mathematics. Oxford. Second Series. — 1977. — Т. 28, вып. 112. — С. 417–420. — doi:10.1093/qmath/28.4.417.
- Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong perfect graph theorem // Annals of Mathematics. — 2006. — Т. 164, вып. 1. — С. 51–229. — doi:10.4007/annals.2006.164.51.
- David S. Johnson. The NP-completeness column: an ongoing guide // Journal of Algorithms. — 1985. — Т. 6, вып. 3. — С. 434–451. — doi:10.1016/0196-6774(85)90012-4.