Subgraf indus

Î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

Formal, fie ${\displaystyle G=(V,E)}$ orice graf și fie ${\displaystyle S\subset V}$ orice submulțime de noduri ale lui G. Atunci subgraful indus ${\displaystyle G[S]}$ este graful a cărui mulțime de noduri este ${\displaystyle S}$ și a cărui mulțime de muchii constă din toate muchiile din ${\displaystyle E}$ care au ambele puncte finale în ${\displaystyle S}$. ^[1] Adică pentru oricare două noduri ${\displaystyle u,v\in S}$, ${\displaystyle u}$ și ${\displaystyle v}$ sunt adiacente în ${\displaystyle G[S]}$ dacă și numai dacă sunt adiacente în ${\displaystyle G}$. Aceeași definiție este valabilă pentru grafuri neorientate, grafuri orientate și chiar multigrafuri.

Subgraful indus ${\displaystyle G[S]}$ poate fi numit și subgraful indus în ${\displaystyle G}$ de ${\displaystyle S}$, sau (dacă contextul face ca alegerea lui ${\displaystyle G}$ să fie neambiguă) subgraful indus al lui ${\displaystyle S}$.

Exemple

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).

• Drumurile induse^⁠(d) sunt subgrafuri induse care sunt drumuri. Cel mai scurt drum între oricare două noduri dintr-un graf neponderat este întotdeauna un drum indus, deoarece orice muchie suplimentară între o pereche de noduri care ar putea face ca aceasta să nu fie indus ar face, de asemenea, să nu mai fie cel mai scurt. În schimb, în grafurile cu distanțe ereditare^⁠(d), orice drum indus este cel mai scurt drum.^[2]
• Ciclurile induse^⁠(d) sunt subgrafiro induse care sunt cicluri. Circumferința^⁠(d) unui graf este definită de lungimea celui mai scurt ciclu al său, care este întotdeauna un ciclu indus. Conform teoremei grafurilor perfecte puternice^⁠(d), ciclurile induse și complementele^⁠(d) lor joacă un rol critic în caracterizarea grafurilor perfecte^⁠(d).^[3]
• Clicile și mulțimile independente^⁠(d) sunt subgrafuri induse care sunt, respectiv, grafuri complete sau grafuri fără muchii^⁠(d).
• Potrivirile induse sunt subgrafuri induse care sunt potriviri.
• Vecinătatea^⁠(d) unui nod este subgraful indus al tuturor nodurilor adiacente acestuia.

Calcul

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]

Note

1. Diestel, Reinhard (2006), Graph Theory, Graduate texts in mathematics, 173, Springer-Verlag, pp. 3–4, ISBN 9783540261834 .
2. Howorka, Edward (1977), „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 (2006), „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. (1985), „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 .