Порождённый подграф графа — это другой граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.

Определение

Формально, пусть G = ( V , E ) — любой граф, и пусть S ⊂ V — подмножество вершин графа G . Тогда порождённый подграф G [ S ] — это граф, вершинами которого являются элементы S , а рёбра которого состоят из всех рёбер из множества E , конечные вершины которых принадлежат S . Одно и то же определение подходит для неориентированных графов , ориентированных графов и даже для мультиграфов .

Порождённый подграф G [ S ] может быть также назван подграфом, порождённым в G набором вершин S или (если контекст не приводит к двусмысленности) порождённым подграфом вершин S .

Примеры

Важными типами подграфов являются следующие:

• порождённые пути — это порождённые подграфы, являющиеся путями . Кратчайший путь между любыми двумя вершинами в невзвешенном графе всегда является порождённым путём. Обратно, в дистанционно-наследуемых графах любой порождённый граф является кратчайшим путём .
• Порождённые циклы — это порождённые подграфы, являющиеся циклами . Обхват графа определяется длиной его кратчайшего цикла, который всегда является порождённым циклом. Согласно строгой теореме о совершенных графах порождённые циклы и их дополнения играют критическую роль в характеризации совершенных графов .
• Клики и независимые множества являются порождёнными подграфами, которые являются полными подграфами или графами без рёбер соответственно.
• Окрестность вершины — это порождённый подграф всех смежных вершин выбранной вершины.

Вычисление

Задача изоморфизма порождённых подграфов является видом задачи поиска изоморфного подграфа , в которой целью является проверка, может ли один граф быть найден как порождённый подграф другого графа. Поскольку эта задача включает задачу о клике как частный случай, она NP-полна .

Примечания

Литература

• Reinhard Diestel. . — Springer-Verlag, 2006. — Т. 173. — С. 3–4. — (Graduate texts in mathematics). — ISBN 9783540261834 .
  • Рейнгард Дистель. Теория графов. — Новосибирск: Издательство Института математики, 2002. — ISBN 5-86134-101-X .
• Edward Howorka. // The Quarterly Journal of Mathematics. Oxford. Second Series. — 1977. — Т. 28 , вып. 112 . — С. 417–420 . — doi : .
• Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. // Annals of Mathematics . — 2006. — Т. 164 , вып. 1 . — С. 51–229 . — doi : .
• David S. Johnson. The NP-completeness column: an ongoing guide // Journal of Algorithms. — 1985. — Т. 6 , вып. 3 . — С. 434–451 . — doi : .