Породжений підграф

Породжений підграф графу — це інший граф, утворений з підмножини вершин графу разом з усіма ребрами, що з'єднують пари вершин з цієї підмножини.

Визначення

Формально, нехай $G = (V, E)$ — будь-який граф, і нехай $S \subset V$ — підмножина вершин графу $G$ . Тоді породжений підграф $G [S]$ — це граф, вершинами якого є елементи $S$ а ребра якого складаються з усіх ребер з множини $E$ кінцеві вершини яких належать $S$ [1]. Одне і те ж визначення підходить для неорієнтованих графів, орієнтованих графів і навіть для мультиграфів.

Породжений підграф $G [S]$ може бути також названий підграфом, породженим у $G$ набором вершин $S$ або (якщо контекст не призводить до двозначності) породженим підграфом вершин $S$

Приклади

Важливими типами підграфів є такі:

Задача про змію в коробці відноситься до пошуку найдовших породжених шляхів у графах гіперкубів .

Породжені шляхи — це породжені підграфи, які є шляхами. Найкоротший шлях між будь-якими двома вершинами в невиваженому графі завжди є породженим шляхом. І навпаки, в дистанційно-успадковуваних графах будь-який породжений граф є найкоротшим шляхом[2].
Породжені цикли — це породжені підграфи, які є циклами. Обхват графу визначається довжиною його найкоротшого циклу, який завжди є породженим циклом. Згідно з строгою теоремою про досконалі графи породжені цикли і їх доповнення грають критичну роль у характеризації досконалих графів[3].
Кліки і незалежні множини є породженими підграфами, які є повними підграфами або графами без ребер відповідно.
Окіл вершини — це породжений підграф всіх суміжних вершин вибраної вершини.

Обчислення

Задача ізоморфізму породжених підграфів є видом задачі пошуку ізоморфного підграфу, в якій метою є перевірка, чи може один граф бути знайдений як породжений підграф іншого графу. Оскільки ця задача включає задачу про кліку як окремий випадок, вона NP-повна [4].

Примітки

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). — ISBN 9783540261834.
- Рейнгард Дистель. Теория графов. — Новосибирск : Издательство Института математики, 2002. — ISBN 5-86134-101-X.
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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[FOOTNOTEDiestel20063–4-1] Diestel, 2006, с. 3–4.

[FOOTNOTEHoworka1977417–420-2] Howorka, 1977, с. 417–420.

[FOOTNOTEChudnovsky,_Robertson,_Seymour,_Thomas200651–229-3] Chudnovsky, Robertson, Seymour, Thomas, 2006, с. 51–229.

[FOOTNOTEJohnson1985434–451-4] Johnson, 1985, с. 434–451.