Породжений підграф графа — це інший граф, утворений з підмножини вершин графа разом з усіма ребрами, що з'єднують пари вершин з цієї підмножини.
Визначення
Формально, нехай G = (V, E) — будь-який граф, і нехай S ⊂ V — підмножина вершин графа G. Тоді породжений підграф G[S] — це граф, вершинами якого є елементи S а ребра якого складаються з усіх ребер з множини E кінцеві вершини яких належать S. Одне і те ж визначення підходить для неорієнтованих графів, орієнтованих графів і навіть для мультиграфів.
Породжений підграф G[S] може бути також названий підграфом, породженим у G набором вершин S або (якщо контекст не призводить до двозначності) породженим підграфом вершин S
Приклади
Важливими типами підграфів є такі:
- Породжені шляхи — це породжені підграфи, які є шляхами. Найкоротший шлях між будь-якими двома вершинами в невиваженому графі завжди є породженим шляхом. І навпаки, в дистанційно-успадковуваних графах будь-який породжений граф є найкоротшим шляхом.
- Породжені цикли — це породжені підграфи, які є циклами. Обхват графа визначається довжиною його найкоротшого циклу, який завжди є породженим циклом. Згідно з сильною теоремою про досконалі графи породжені цикли і їх доповнення грають критичну роль у характеризації досконалих графів.
- Кліки і незалежні множини є породженими підграфами, які є повними підграфами або графами без ребер відповідно.
- Окіл вершини — це породжений підграф всіх суміжних вершин вибраної вершини.
Обчислення
[ru] є видом (задачі пошуку ізоморфного підграфа), в якій метою є перевірка, чи може один граф бути знайдений як породжений підграф іншого графа. Оскільки ця задача включає задачу про кліку як окремий випадок, вона NP-повна .
Примітки
- Diestel, 2006, с. 3–4.
- Howorka, 1977, с. 417–420.
- Chudnovsky, Robertson, Seymour, Thomas, 2006, с. 51–229.
- Johnson, 1985, с. 434–451.
Література
- Reinhard Diestel. Graph Theory. — Springer-Verlag, 2006. — Т. 173. — С. 3–4. — (Graduate texts in mathematics). — .
- Рейнгард Дистель. Теория графов. — Новосибирск : Издательство Института математики, 2002. — .
- Edward Howorka. A characterization of distance-hereditary graphs // The Quarterly Journal of Mathematics. Oxford. Second Series. — 1977. — Т. 28, вип. 112. — С. 417–420. — DOI:10.1093/qmath/28.4.417.
- Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong perfect graph theorem // Annals of Mathematics. — 2006. — Т. 164, вип. 1. — С. 51–229. — DOI:10.4007/annals.2006.164.51.
- David S. Johnson. The NP-completeness column: an ongoing guide // Journal of Algorithms. — 1985. — Т. 6, вип. 3. — С. 434–451. — DOI:10.1016/0196-6774(85)90012-4.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет