Индуцированный подграф - Induced subgraph
В теории графов , подграф графа представляет другой график, формируется из подмножества вершин графа и все ребер (от исходного графа) , соединяющий пары вершин в этом подмножестве.
Определение
Формально, пусть будет любой граф, и пусть любое подмножество вершин G . Тогда индуцированный подграф - это граф, множество вершин которого и множество ребер состоит из всех ребер , имеющих оба конца в . То есть, для любых двух вершин , и смежны тогда и только тогда , когда они находятся рядом с . То же определение работает для неориентированных графов , ориентированных графов и даже мультиграфов .
Подграфа можно также назвать подграф , индуцированный в с , или (если контекст делает выбор однозначным) индуцированный подграф .
Примеры
Важные типы индуцированных подграфов включают следующее.
- Индуцированные пути - это индуцированные подграфы, которые являются путями . Кратчайший путь между любыми двумя вершинами в графе невзвешенной всегда индуцированный путь, потому что любые дополнительные ребра между парами вершин , которые могли бы привести к его не индуцируются бы также привести к его не кратчайшему. Наоборот, в дистанционно-наследственных графах каждый индуцированный путь является кратчайшим.
- Индуцированные циклы - это индуцированные подграфы, которые являются циклами . Обхват графа определяется длиной ее кратчайшего цикла, который всегда индуцируется цикл. Согласно сильной теореме о совершенных графах , индуцированные циклы и их дополнения играют решающую роль в характеристике совершенных графов .
- Клики и независимые множества - это индуцированные подграфы, которые являются соответственно полными графами или графами без ребер .
- Индуцированные сопоставления - это индуцированные подграфы, являющиеся сопоставлениями .
- Окрестности вершины является индуцированный подграф всех вершин , смежных с ней.
Вычисление
Проблема изоморфизма индуцированных подграфов - это форма проблемы изоморфизма подграфов, цель которой состоит в том, чтобы проверить, может ли один граф быть найден как индуцированный подграф другого. Поскольку он включает проблему клики как частный случай, он является NP-полным .