Problema de la clique

Problema de la clique

Problema de la clique

En complejidad computacional, el problema de la Clique o problema de la liga de amigos es un problema NP-completo según la Teoría de la complejidad computacional.


6n-graf-clique.svg

Una clique en un grafo es un conjunto de vértices dos a dos adyacentes. En el grafo de la derecha, los vértices 1, 2 y 5 forman una clique porque cada uno tiene un arco que le une a los otros. En cambio, los vértices 2, 3 y 4 no, dado que 2 y 4 no son adyacentes.

El problema de la clique es un problema de optimización para determinar cuándo un grafo contiene una clique de al menos un tamaño k. Una vez que tenemos k o más vertices que forman una clique, es trivial verificar que lo son, por eso es un problema NP. El correspondiente problema de optimización, consiste en encontrar una clique de tamaño máximo en un grafo (un subgrafo completo de tamaño máximo). Este problema se puede enunciar como un problema de decisión si la pregunta que se hace es saber si existe una clique de tamaño k en el grafo.


CLIQUE = \{(G, k)\big | G \} ;tama\tilde{n}o\ge\; k

Algoritmos

Un ejemplo de algoritmo de fuerza bruta para encontrar una clique en un grafo consiste en listar todos los subconjuntos de vértices V y verificar para cada uno de ellos si forma una clique. Ese algoritmo es polinómico si k es una constante pero no lo es cuando se hace depender a k de, por ejemplo, |V|/2.

Un mejor algoritmo (Bron y Kerbosch) consiste en arrancar con cliques de un solo elemento (cualquier elemento sirve) e intentar mezclar cliques para obtener otras más grandes, hasta que no queden más mezclas por intentarse. Dos cliques pueden ser mezcladas si cada nodo de la primera es adyacente a cada nodo de la segunda.

Véase también

Obtenido de "Problema de la clique"

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • Problema de la clique — En Computación, el problema de la Clique o problema de la liga de amigos es un problema NP completo según la Teoría de la complejidad computacional. Una clique en un grafo es un conjunto de vértices dos a dos adyacentes. En el grafo de la derecha …   Enciclopedia Universal

  • Problema de isomorfismo de subgrafos — Saltar a navegación, búsqueda En complejidad computacional, el Problema de isomorfismo de subgrafos, también a veces llamado Problema de matching de subgrafos, es un problema de decisión NP completo, que formalmente, se define de la siguiente… …   Wikipedia Español

  • Problema de la cobertura de vértices — Saltar a navegación, búsqueda En ciencias de la computación, el Problema de la cobertura de vértices es un problema NP completo, que pertenece a los 21 problemas NP completos de Karp. Es muy utilizado en teoría de complejidad computacional para… …   Wikipedia Español

  • Problema de satisfacibilidad booleana — Saltar a navegación, búsqueda En teoría de la complejidad computacional, el Problema de satisfacibilidad booleana (SAT) fue el primer problema identificado como perteneciente a la clase de complejidad NP completo. Se trata de un problema donde… …   Wikipedia Español

  • Clique — El grafo completo K5. En un subgrafo como éste, los vértices forman un clique de tamaño 5. En teoría de grafos, un clique en un grafo no dirigido G es un conjunto de vértices V tal que para todo par de vértices de V, existe una arista que las… …   Wikipedia Español

  • NP-completo — En teoría de la complejidad computacional, la clase de complejidad NP completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP completo. Se puede decir que los… …   Wikipedia Español

  • Algoritmo de aproximación — En ciencias de la computación e investigación de operaciones, un algoritmo de aproximación es un algoritmo usado para encontrar soluciones aproximadas a problemas de optimización. Están a menudo asociados con problemas NP hard; como es poco… …   Wikipedia Español

  • Cobertura de vértices — En matemáticas, en el campo de la teoría de grafos, un covering de un grafo es un conjunto de vértices (o arcos) cuyos elementos son cerrados (adyacentes) a todos los vértices (o nodos) del grafo. Es de especial interés encontrar pequeños… …   Wikipedia Español

  • NP (Complejidad computacional) — Saltar a navegación, búsqueda Los recursos comúnmente estudiados en complejidad computacional son: – El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema. – El espacio: mediante… …   Wikipedia Español

  • NP (clase de complejidad) — En teoría de la complejidad computacional, NP es el acrónimo en inglés de nondeterministic polynomial time ( tiempo polinomial no determinista ). Es el conjunto de problemas que pueden ser resueltos en tiempo polinómico por una máquina de Turing… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”