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

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

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

Визначення ред.

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

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

Приклади ред.

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

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

Обчислення ред.

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

Примітки ред.

  1. Diestel, 2006, с. 3–4.
  2. Howorka, 1977, с. 417–420.
  3. Chudnovsky, Robertson, Seymour, Thomas, 2006, с. 51–229.
  4. Johnson, 1985, с. 434–451.

Література ред.