Conjunt independent
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[nota 1] é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).[1]
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)
Notes
- ↑ «Conjunt independent maximal» no deu confondre's en el «màxim conjunt independent». El primer és un conjunt independent que no està contingut en cap atre conjunt independent major que ell. En efecte, el problema de trobar un conjunt independent maximal pot resoldre's en temps polinomial per mig d'un simple algoritme voraç.cita requerida
Referències
- ↑ Scheinerman: Matemàtiques discretes ISBN 970-686-071-1
Referències
- Este artícul conté una traducció derivada de «Conjunto independiente» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.