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

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

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

Определение

Формально, пусть будет любым графом, и пусть будет любым подмножеством вершин графа 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. Howorka, Edward (1977), «Характеристика дистанционно-наследуемых графов», The Quarterly Journal of Mathematics , Вторая серия, 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-полноты: постоянное руководство», Журнал алгоритмов , 6 (3): 434–451, doi :10.1016/0196-6774(85)90012-4, MR  0800733.