Порождённый подграф графа — это другой граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.
Определение Формально, пусть — любой граф, и пусть — подмножество вершин графа . Тогда порождённый подграф — это граф, вершинами которого являются элементы , а рёбра которого состоят из всех рёбер из множества , конечные вершины которых принадлежат . Одно и то же определение подходит для неориентированных графов, ориентированных графов и даже для мультиграфов.
Порождённый подграф может быть также назван подграфом, порождённым в набором вершин или (если контекст не приводит к двусмысленности) порождённым подграфом вершин .
Примеры Важными типами подграфов являются следующие:
порождённые пути — это порождённые подграфы, являющиеся путями. Кратчайший путь между любыми двумя вершинами в невзвешенном графе всегда является порождённым путём. Обратно, в дистанционно-наследуемых графах любой порождённый граф является кратчайшим путём. Порождённые циклы — это порождённые подграфы, являющиеся циклами. Обхват графа определяется длиной его кратчайшего цикла, который всегда является порождённым циклом. Согласно строгой теореме о совершенных графах порождённые циклы и их дополнения играют критическую роль в характеризации совершенных графов. Клики и независимые множества являются порождёнными подграфами, которые являются полными подграфами или графами без рёбер соответственно. Окрестность вершины — это порождённый подграф всех смежных вершин выбранной вершины.
Вычисление Задача изоморфизма порождённых подграфов является видом задачи поиска изоморфного подграфа, в которой целью является проверка, может ли один граф быть найден как порождённый подграф другого графа. Поскольку эта задача включает задачу о клике как частный случай, она NP-полна.
Примечания
Литература
Категория:Операции над графами Категория:Объекты теории графов