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