El Problema Del Máximo Clique

Páginas: 5 (1244 palabras) Publicado: 6 de agosto de 2012
Problema del máximo clique

Definición de un clique
Un clique dentro de un grafo no dirigido es un conjunto de vértices, para los cuales, cada uno de ellos está conectado con cada uno de ellos por medio de una arista. Otra definición más formal, es la que dice: «Un clique en un grafo no dirigido G es un conjunto de vértices G, tal que para todo par de vértices, existe una arista que los conecta»Dado G = (V , E), en el cual V = {1, 2, , n } es el conjunto de vértices que conforman a G y E es el conjunto de aristas. Un clique es un conjunto C de vértices dónde todo par de vértices está conectado con una arista en G, de lo cual se puede decir que C es un subgrafo completo. Un clique puede ser parcial, si este forma parte de otro clique, en cuyo caso no podrá ser un clique máximo,definiéndose éste como un clique que conjunto el mayor número de vértices porsible del grafo G. Dado el siguiente grafo, se puede notar que los vértices y arcos marcados en rojo forman un clique dentro del grafo de color azul.

Figura 1. Un clique es un subgrafo que une pares de vértices por aristas

Los cliques poseen un tamaño, dicho tamaño está dado por el número de vértices que contiene, así pues ungrafo G puede tener un máximo clique de tamaño igual a la cardinalidad del conjunto de vértices que conforman a G, tal como se demuestra en la siguiente imagen, con lo cual se dice que el grafo G es un grafo completo.

1

2

Sección

Figura 2. Un grafo G que tiene un clique máximo de tamaño igual al si mismo

Problemas de cliques
Dentro de Teoría de Grafos y haciendo uso del conceptodel clique se forman varios problemas computacionales, de entre los cuáles destacan • • • Encontrar el clique de máximo tamaño dentro un grafo G Encontrar todos los cliques que se contienen dentro de un grafo G Encontrar si el grafo G posee un clique de tamaño k

Sobre la complejidad de los problemas anteriores se puede mencionar lo siguiente: Para el problema del clique de máximo tamaño o MCP,el cual es un problema NP complejo, existe una complejidad asociada de O(C(n, k)k2), de la cual se deduce que el problema es de optimización combinatoria y que las técnicas convencionales exactas son ineficientes al momento de buscar una solución. Para encontrar todos los cliques que se contienen dentro de un grafo G, se dice que su complejidad es O(C(n, k)k2) tomando esta dado ser la cota superiory despreciando las que son inherentes a la obtención de cliques de tamaño u orden menor a k, es decir cliques más pequeños que el máximo.

Algoritmos para búsqueda de máximo clique
Existen varios algoritmos para búsqueda de máximo clique dentro de un grafo, de entre todos existe uno que destaca por su eficiencia y sencilla, el cual es el algoritmo de Bron-Kerbosch. Existen dos versiones delAlgoritmo de Bron-Kerbosch para la obtención de cliques dentro de un grafo no dirigido, se diferencian en que en una de ellas se hace una elección de pivote previa a comenzar el algoritmo, lo cual provoca como beneficio una reducción en la complejidad del mismo al hacerse este más eficiente con menor número de llamadas recursivas. El siguiente es el algoritmo de Bron-Kerbosch que no hace uso deselección de pivote. Algoritmo Versión 1 Llamada a Algoritmo : BK(φ,V[G],φ) BK(φ,V[G],φ) if P=φ and X=φ then Report R as maximal clique else Assume P={u1, u2 , , uk }

Aplicaciones

3

for i←1 to k do P=P-{u1} Rnew=R {u1} Pnew=P N [u1] Xnew=X N [u1] BK(Rnew, Pnew, Xnew) X=X {u1} Su representación gráfica se puede encontrar al final de este documento. Como ya se mencionó anteriormente, el árbol dellamadas recursivas generado por la Versión 1 del algoritmo de Bron-Kerbosch es repetitivo en cualquier caso, dado que conforme aumente en nodos el grafo G, el tiempo de ejecución que presentará el algoritmo será mayor. Para evitar que este árbol de recursiones crezca sin mesura, se creo una versión 2 de dicho algoritmo, en la que mediante la selección de un pivote se divide el problema. El...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Problema De Flujo Maximo
  • El Problema De Máximo Soto Hall
  • Calculo problema maximo minimos
  • Maximas
  • Lo Maximo
  • maximo
  • Problema Resuelto Minimo Y Maximo Completo
  • unidad 5 problema flujo maximo

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS