Индуцированный подграф
-
Определение индуцированного подграфа
- Индуцированный подграф — это граф, сформированный из вершин исходного графа и ребер, соединяющих эти вершины.
- Подмножество вершин S определяет индуцированный подграф G[S], который имеет те же вершины и ребра, что и G, но только с ребрами, соединяющими вершины из S.
-
Примеры индуцированных подграфов
- Индуцированные пути — это подграфы, которые являются путями и могут быть кратчайшими путями в невзвешенных графах.
- Индуцированные циклы — это подграфы, которые являются циклами и определяют обхват графа.
- Клики и независимые множества — это подграфы, которые являются полными графами и графами без ребер соответственно.
- Индуцированные соответствия — это подграфы, которые являются соответствиями.
- Окрестность вершины — это подграф, состоящий из всех соседних с ней вершин.
-
Вычисление индуцированного изоморфизма подграфов
- Задача об индуцированном изоморфизме подграфов является NP-полной и включает в себя проблему клики как частный случай.
Полный текст статьи: