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

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

Exemple

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

Problema Format:Ill-wd se referă la cele mai lungi Format:Ill-wd în Format:Ill-wd.

• Format:Ill-wd 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 Format:Ill-wd, orice drum indus este cel mai scurt drum.
• Format:Ill-wd sunt subgrafiro induse care sunt cicluri. Format:Ill-wd unui graf este definită de lungimea celui mai scurt ciclu al său, care este întotdeauna un ciclu indus. Conform Format:Ill-wd, ciclurile induse și Format:Ill-wd lor joacă un rol critic în caracterizarea Format:Ill-wd.
• Clicile și Format:Ill-wd sunt subgrafuri induse care sunt, respectiv, grafuri complete sau Format:Ill-wd.
• Potrivirile induse sunt subgrafuri induse care sunt potriviri.
• Format:Ill-wd unui nod este subgraful indus al tuturor nodurilor adiacente acestuia.

Calcul

Format:Ill-wd este o formă a Format:Ill-wd î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ă.