Diferencia entre revisiones de «Teoría de grafos»
Contenido eliminado Contenido añadido
Línea 104:
* Encontrar el subgrafo completo más grande se llama [[problema de la clique]].
Un problema similar es encontrar un [[subgrafo inducido]] en un grafo dado. De nuevo, algunas propiedades importantes son heredadas con respecto a subgrafos inducidos, lo que significa que un grafo tiene una propiedad si y solo si todos los subgrafos inducidos la tienen. Encontrar subgrafos inducidos máximos de un determinado tipo es, de nuevo, un problema [[NP-completo]]. Como ejemplo:
* Encontrar el subgrafo inducido más grande sin bordes o [[conjunto independiente]] se denomina [[problema del conjunto independiente]].
| |||