Î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 orice graf și fie orice submulțime de noduri ale lui . 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 . . 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 .
Exemple Printre tipurile importante de subgrafuri induse se numără următoarele. miniatura| Problema se referă la cele mai lungi în .
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 , orice drum indus este cel mai scurt drum.. sunt subgrafiro induse care sunt cicluri. unui graf este definită de lungimea celui mai scurt ciclu al său, care este întotdeauna un ciclu indus. Conform , ciclurile induse și lor joacă un rol critic în caracterizarea .. Clicile și sunt subgrafuri induse care sunt, respectiv, grafuri complete sau . Potrivirile induse sunt subgrafuri induse care sunt potriviri. unui nod este subgraful indus al tuturor nodurilor adiacente acestuia.
Calcul este o formă a î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ă..
Note
Categorie:Teoria grafurilor