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

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

Содержание

• 1 Определение
• 2 Примеры
• 3 Вычисление
• 4 Ссылки

Определение

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

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

Примеры

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

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

Вычисление

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

Ссылки