În teoria grafurilor, un subgraf indus al unui graf este un alt graf, format dintr-o submulțime a nodurilor grafului și din toate muchiile (din graful originar) care conectează perechile de noduri din acea submulțime.

Definiție

modificare

Formal, fie   orice graf și fie   orice submulțime de noduri ale lui G. Atunci subgraful indus   este graful a cărui mulțime de noduri este   și a cărui mulțime de muchii constă din toate muchiile din   care au ambele puncte finale în  . [1] Adică pentru oricare două noduri  ,   și   sunt adiacente în   dacă și numai dacă sunt adiacente în  . Aceeași definiție este valabilă pentru grafuri neorientate, grafuri orientate și chiar multigrafuri.

Subgraful indus   poate fi numit și subgraful indus în   de  , sau (dacă contextul face ca alegerea lui   să fie neambiguă) subgraful indus al lui  .

Printre tipurile importante de subgrafuri induse se numără următoarele.

 
Problema șarpelui în cutie⁠(d) se referă la cele mai lungi drumuri induse⁠(d) în grafurile hipercub⁠(d).

Problema izomorfismului subgrafurilor induse⁠(d) este o formă a problemei izomorfismului subgrafurilor⁠(d) în care scopul este de a testa dacă un graf poate fi găsit ca subgraf indus al altuia. Deoarece include problema clicii drept caz special, este o problemă NP-completă.[4]

  1. ^ Diestel, Reinhard (), Graph Theory, Graduate texts in mathematics, 173, Springer-Verlag, pp. 3–4, ISBN 9783540261834 .
  2. ^ Howorka, Edward (), „A characterization of distance-hereditary graphs”, The Quarterly Journal of Mathematics, Second Series, 28 (112), pp. 417–420, doi:10.1093/qmath/28.4.417, MR 0485544 .
  3. ^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (), „The strong perfect graph theorem”, Annals of Mathematics⁠(d), 164 (1), pp. 51–229, arXiv:math/0212070 , doi:10.4007/annals.2006.164.51, MR 2233847 .
  4. ^ Johnson, David S. (), „The NP-completeness column: an ongoing guide”, Journal of Algorithms, 6 (3), pp. 434–451, doi:10.1016/0196-6774(85)90012-4, MR 0800733 .