Породжений підграф графа — це інший граф, утворений з підмножини вершин графа разом з усіма ребрами, що з'єднують пари вершин з цієї підмножини.
Визначення Формально, нехай — будь-який граф, і нехай — підмножина вершин графа . Тоді породжений підграф — це граф, вершинами якого є елементи а ребра якого складаються з усіх ребер з множини кінцеві вершини яких належать . Одне і те ж визначення підходить для неорієнтованих графів, орієнтованих графів і навіть для мультиграфів.
Породжений підграф може бути також названий підграфом, породженим у набором вершин або (якщо контекст не призводить до двозначності) породженим підграфом вершин
Приклади Важливими типами підграфів є такі:
Породжені шляхи — це породжені підграфи, які є шляхами. Найкоротший шлях між будь-якими двома вершинами в невиваженому графі завжди є породженим шляхом. І навпаки, в дистанційно-успадковуваних графах будь-який породжений граф є найкоротшим шляхом. Породжені цикли — це породжені підграфи, які є циклами. Обхват графа визначається довжиною його найкоротшого циклу, який завжди є породженим циклом. Згідно з сильною теоремою про досконалі графи породжені цикли і їх доповнення грають критичну роль у характеризації досконалих графів. Кліки і незалежні множини є породженими підграфами, які є повними підграфами або графами без ребер відповідно. Окіл вершини — це породжений підграф всіх суміжних вершин вибраної вершини.
Обчислення є видом задачі пошуку ізоморфного підграфа, в якій метою є перевірка, чи може один граф бути знайдений як породжений підграф іншого графа. Оскільки ця задача включає задачу про кліку як окремий випадок, вона NP-повна .
Примітки
Література