Введение

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

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

Определение

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

Примеры

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

Вычисления

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