Conjunt independent

Erro al crear miniatura:

El (inesperadament asimètric) conjunt de 9 vèrtiços blaus és un conjunt independent maximal per a este grafo de 24 vèrtiços.

En teoria de grafos, un conjunt independent o estable és un conjunt de vèrtiços en un grafo tal que cap dels seus vèrtiços és adjacent a un atre. És dir, és un conjunt V de vèrtiços tal que per a cap parell d'ells existix alguna aresta que els conecten. En atres paraules, cada aresta en el grafo conté a lo més un vèrtiç en V. El tamany d'un conjunt independent és el número de vèrtiços que conté.

Un conjunt independent maximal és un conjunt independent tal que afegint qualsevol atre vèrtiç al conjunt, est deixa de ser independent.

Definició formal

Donat un grafo G, un subconjunt de vèrtiços H ⊂ V(G) es diu conjunt independent si no hi ha dos vèrtiços en H que siguen adjacents.

El número d'independència de G és el tamany d'un conjunt independent més gran, i es denota per α(G).

Computabilidad

El conjunt independent màxim correspon al major conjunt independent definible sobre un grafo donat. El problema de trobar un conjunt en estes característiques es diu problema del màxim conjunt independent i és NP-complet, per lo que és poc provable que existixca un algoritme que ho resolga eficientemente.

El problema de decidir si un grafo dau té un conjunt independent d'un tamany particular és el Problema del conjunt independent, el qual és computacionalment equivalent a decidir si un grafo té un clique d'un tamany particular. Açò perque, si un grafo té un conjunt independent de tamany k, després la seua grafo complement tindrà un clique de tamany k. El problema de decisió del conjunt independent (de la mateixa manera que el problema del clique) també és NP-complet.

Vore també

• Matching (conjunt d'arestes independents)