En teoría de grafos, un conjunto independiente o estable es un conjunto de vértices en un grafo tal que ninguno de sus vértices es adyacente a otro. Es decir, es un conjunto V de vértices tal que para ningún par de ellos existe alguna arista que los conecten. En otras palabras, cada arista en el grafo contiene a lo más un vértice en V. El tamaño de un conjunto independiente es el número de vértices que contiene.
El (inesperadamente asimétrico) conjunto de 9 vértices azules es un conjunto independiente maximal para este grafo de 24 vértices.
Un conjunto independiente maximal[nota 1] es un conjunto independiente tal que añadiendo cualquier otro vértice al conjunto, este deja de ser independiente.
Definición formal
Dado un grafo G, un subconjunto de vértices H ⊂ V(G) se llama conjunto independiente si no hay dos vértices en H que sean adyacentes.
El número de independencia de G es el tamaño de un conjunto independiente más grande, y se denota por α(G).[1]
Computabilidad
El conjunto independiente máximo corresponde al mayor conjunto independiente definible sobre un grafo dado. El problema de encontrar un conjunto con estas características se llama problema del máximo conjunto independiente y es NP-completo, por lo cual es poco probable que exista un algoritmo que lo resuelva eficientemente.
El problema de decidir si un grafo dado tiene un conjunto independiente de un tamaño particular es el Problema del conjunto independiente, el cual es computacionalmente equivalente a decidir si un grafo tiene un clique de un tamaño particular. Esto porque, si un grafo tiene un conjunto independiente de tamaño k, luego su grafo complemento tendrá un clique de tamaño k. El problema de decisión del conjunto independiente (al igual que el problema del clique) también es NP-completo.
«Conjunto independiente maximal» no debe confundirse con el «máximo conjunto independiente». El primero es un conjunto independiente que no está contenido en ningún otro conjunto independiente mayor que él. En efecto, el problema de encontrar un conjunto independiente maximal puede resolverse en tiempo polinomial mediante un simple algoritmo voraz.[cita requerida]
Pruebas de testing (benchmarks) para problemas del Clique máximo, Máximo conjunto independiente, Mínima cobertura de vértices y Coloreo de vértices
Datos:Q1060343
Multimedia:Independent set (graph theory)
Febrero 21, 2022
conjunto, independiente, teoría, grafos, conjunto, independiente, estable, conjunto, vértices, grafo, ninguno, vértices, adyacente, otro, decir, conjunto, vértices, para, ningún, ellos, existe, alguna, arista, conecten, otras, palabras, cada, arista, grafo, co. En teoria de grafos un conjunto independiente o estable es un conjunto de vertices en un grafo tal que ninguno de sus vertices es adyacente a otro Es decir es un conjunto V de vertices tal que para ningun par de ellos existe alguna arista que los conecten En otras palabras cada arista en el grafo contiene a lo mas un vertice en V El tamano de un conjunto independiente es el numero de vertices que contiene El inesperadamente asimetrico conjunto de 9 vertices azules es un conjunto independiente maximal para este grafo de 24 vertices Un conjunto independiente maximal nota 1 es un conjunto independiente tal que anadiendo cualquier otro vertice al conjunto este deja de ser independiente Indice 1 Definicion formal 2 Computabilidad 3 Vease tambien 4 Notas 5 Referencias 6 Enlaces externosDefinicion formal EditarDado un grafo G un subconjunto de vertices H V G se llama conjunto independiente si no hay dos vertices en H que sean adyacentes El numero de independencia de G es el tamano de un conjunto independiente mas grande y se denota por a G 1 Computabilidad EditarEl conjunto independiente maximo corresponde al mayor conjunto independiente definible sobre un grafo dado El problema de encontrar un conjunto con estas caracteristicas se llama problema del maximo conjunto independiente y es NP completo por lo cual es poco probable que exista un algoritmo que lo resuelva eficientemente El problema de decidir si un grafo dado tiene un conjunto independiente de un tamano particular es el Problema del conjunto independiente el cual es computacionalmente equivalente a decidir si un grafo tiene un clique de un tamano particular Esto porque si un grafo tiene un conjunto independiente de tamano k luego su grafo complemento tendra un clique de tamano k El problema de decision del conjunto independiente al igual que el problema del clique tambien es NP completo Vease tambien EditarMatching conjunto de aristas independientes Notas Editar Conjunto independiente maximal no debe confundirse con el maximo conjunto independiente El primero es un conjunto independiente que no esta contenido en ningun otro conjunto independiente mayor que el En efecto el problema de encontrar un conjunto independiente maximal puede resolverse en tiempo polinomial mediante un simple algoritmo voraz cita requerida Referencias Editar Scheinerman Matematicas discretas ISBN 970 686 071 1Enlaces externos EditarWeisstein Eric W MaximalIndependentVertexSet En Weisstein Eric W ed MathWorld en ingles Wolfram Research Pruebas de testing benchmarks para problemas del Clique maximo Maximo conjunto independiente Minima cobertura de vertices y Coloreo de vertices Datos Q1060343 Multimedia Independent set graph theory Obtenido de https es wikipedia org w index php title Conjunto independiente amp oldid 135198924, wikipedia, wiki, leyendo, leer, libro, biblioteca,
