В теории графов , подграф графа представляет другой график, формируется из подмножества вершин графа и все ребер , соединяющих пары вершин в этом подмножестве.
Определение
Формально пусть - любой граф, и пусть любое подмножество вершин G . Тогда индуцированный подграф - граф, множество вершин которого и чье множество ребер состоит из всех ребер в у которых есть обе конечные точки в . [1] То есть для любых двух вершин, а также соседствуют в тогда и только тогда, когда они смежны в . То же определение работает для неориентированных графов , ориентированных графов и даже мультиграфов .
Индуцированный подграф можно также назвать подграфом, индуцированным в от , или (если контекст делает выбор однозначно) индуцированный подграф .
Примеры
Важные типы индуцированных подграфов включают следующее.
- Индуцированные пути - это индуцированные подграфы, которые являются путями . Кратчайший путь между любыми двумя вершинами в графе невзвешенной всегда индуцированный путь, потому что любые дополнительные ребра между парами вершин , которые могли бы привести к его не индуцируются бы также привести к его не кратчайшему. Наоборот, в дистанционно-наследственных графах каждый индуцированный путь является кратчайшим. [2]
- Индуцированные циклы - это индуцированные подграфы, которые являются циклами . Обхват графа определяется длиной ее кратчайшего цикла, который всегда индуцируется цикл. Согласно сильной теореме о совершенных графах , индуцированные циклы и их дополнения играют решающую роль в характеристике совершенных графов . [3]
- Клики и независимые множества - это индуцированные подграфы, которые являются соответственно полными графами или графами без ребер .
- Индуцированные сопоставления - это индуцированные подграфы, являющиеся сопоставлениями .
- Окрестности вершины является индуцированный подграф всех вершин , смежных с ней.
Вычисление
Проблема изоморфизма индуцированных подграфов - это форма проблемы изоморфизма подграфов, цель которой состоит в том, чтобы проверить, может ли один граф быть найден как индуцированный подграф другого. Поскольку он включает проблему клики как частный случай, он является NP-полным . [4]
Рекомендации
- ^ Diestel, Райнхард (2006), Теория графов , Graduate тексты в математике, 173 , Springer-Verlag, стр. 3-4, ISBN 9783540261834.
- ^ Howorka, Эдвард (1977), "Характеристика расстояния наследственных графов", Ежеквартальный журнал математика , Вторая серия, 28 (112): 417-420, DOI : 10,1093 / qmath / 28.4.417 , МР 0485544.
- ^ Чудновский, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), "Сильная совершенная теорема графа", Анналы математики , 164 (1): 51-229, Arxiv : математика / 0212070 , DOI : 10,4007 / annals.2006.164.51 , MR 2233847.
- ^ Джонсон, Дэвид С. (1985), "NP-полнота колонки: постоянная руководство", журнал алгоритмов , 6 (3): 434-451, DOI : 10,1016 / 0196-6774 (85) 90012-4 , МР 0800733.