Introduccion

Equipo:

Osvaldo Javier Hinojosa Rdz - 1452344 {Calificación: 80}

Blanca Alicia Rodriguez Rivas - 1458143 {Calificación: 80}

Rafael Lopez Gutierrez - 1451428 {Calificación: 80}

Lenguaje:

PYTHON

Definición del problema escogido:

Clique Maximo

Dado un grafo no dirigido G = V,E, donde V es un conjunto de vértices y E es el conjunto de bordes, se dice que dos vértices son adyacentes cuando están conectados por un borde. Se dice que el grafo es completo cuando dos vertices cualiesquiera son adyacentes y, cuando esto sucede, tambien se dice que el grafo es un clique. Un problema tipico es la obtencion del subconjunto maximo de vertices de V tal que sus elementos forman un clique. En este caso hablamos del "problema del maximo clique" (MCP).

La figura 5.6 ilustra el concepto de clique con un grafo de ejemplo formado por 4 elemtentos. el estudio de los cliques tiene importantes alicaiones practicas en campos como la vision por computador o el procesamiento de señales. En particular resulta gran interes en problemas de optmizacion combinacional, en aplicaciones como el analisis de mercados.