Индуцированный подграф

Граф, составленный из подмножества узлов другого графа и их ребер.

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

Определение

Формально, пусть это любой граф и любое подмножество вершин G . Тогда индуцированный подграф — это граф, набор вершин которого равен , а набор ребер состоит из всех ребер, у которых обе конечные точки находятся в . ^[1] То есть для любых двух вершин и смежны в тогда и только тогда , когда они смежны в . То же определение работает для неориентированных графов , ориентированных графов и даже мультиграфов . ${\displaystyle G=(V,E)}$ ${\displaystyle S\subseteq V}$ ${\displaystyle G[S]}$ ${\displaystyle S}$ ${\displaystyle E}$ ${\displaystyle S}$ ${\displaystyle u,v\in S}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G[S]}$ ${\displaystyle G}$

Индуцированный подграф можно также назвать подграфом, индуцированным в , или (если контекст делает выбор однозначным) индуцированным подграфом . ${\displaystyle G[S]}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle S}$

Примеры

Важные типы индуцированных подграфов включают следующие.

Проблема « змея в коробке» касается самых длинных индуцированных путей в графах гиперкубов.

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

Вычисление

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

Рекомендации

1. Дистель, Рейнхард (2006), Теория графов, Тексты для выпускников по математике, том. 173, Springer-Verlag, стр. 3–4, ISBN. 9783540261834.
2. Ховорка, Эдвард (1977), «Характеристика дистанционно-наследственных графов», Ежеквартальный журнал математики , вторая серия, 28 (112): 417–420, doi : 10.1093/qmath/28.4.417, MR  0485544.
3. Чудновский, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), «Сильная теорема о совершенном графе», Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , doi :10.4007/annals.2006.164.51, MR  2233847.
4. Джонсон, Дэвид С. (1985), «Колонка NP-полноты: постоянное руководство», Journal of Algorithms , 6 (3): 434–451, doi : 10.1016/0196-6774(85)90012-4, MR  0800733.