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

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

Определение

Формально пусть $г = (V, E)$ - любой граф, и пусть $S \subset V$ - любое подмножество вершин $г$ . Тогда индуцированный подграф $г [S]$ - граф, множество вершин которого $S$ и чье множество ребер состоит из всех ребер в $E$ которые имеют обе конечные точки в $S$ .^[1] То же определение работает для неориентированные графы, ориентированные графы, и даже мультиграфы.

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

Примеры

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

В змея в коробке проблема касается самого длинного индуцированные пути в графы гиперкуба

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

Вычисление

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

использованная литература

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

[1] Дистель, Рейнхард (2006), Теория графов, Выпускные тексты по математике, 173, Springer-Verlag, стр. 3–4, ISBN 9783540261834.

[2] Ховорка, Эдвард (1977), "Характеристика дистанционно-наследственных графов", Ежеквартальный журнал математики. Оксфорд. Вторая серия, 28 (112): 417–420, Дои:10.1093 / qmath / 28.4.417, Г-Н 0485544.

[3] Чудновский, Мария; Робертсон, Нил; Сеймур, Пол; Томас, Робин (2006), "Сильная теорема о совершенном графе", Анналы математики, 164 (1): 51–229, arXiv:математика / 0212070, Дои:10.4007 / анналы.2006.164.51, Г-Н 2233847.

[4] Джонсон, Дэвид С. (1985), "Колонка NP-полноты: постоянное руководство", Журнал алгоритмов, 6 (3): 434–451, Дои:10.1016/0196-6774(85)90012-4, Г-Н 0800733.

[1]

[2]

[3]

[4]