Triángulo monocromático

Triángulo monocromático: El problema del triángulo monocromático es un problema de decisión que pertenece a la clase de los problemas NP-completos.

Entrada: Un grafo no dirigido G(V,E), donde V es un conjunto de n vértices y E es el conjunto de aristas.

Pregunta: ¿Puede el conjunto E ser particionado en dos conjuntos disjuntos E1 y E2, tales que ninguno de los dos grafos G1(V,E1) y G2(V,E2) contengan un triángulo; es decir, tal que para todos los vértices de E1 y E2, no exista un conjunto {u,v,w} tal que las aristas {u,v}, {u,w}, {v,w} estén definidas?

Véase también

Teorema de Ramsey

Referencias

Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 978-0-7167-1045-5 . A1.1: GT6, pg.191.θ

Categoría:
Problemas NP-completos

Игры ⚽ Нужен реферат?

Coloración de grafos — Una vértice coloración propia del grafo de Petersen con 3 colores, el número mínimo posible. En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del … Wikipedia Español
Modelo de color RGB — Se ha sugerido que RGB (vídeo) sea fusionado en este artículo o sección (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí … Wikipedia Español
Monocromador — Un prisma triangular, el dibujo muestra como se dispersan las diferentes longitudes de onda de la luz. (Click para ver la animación) Un monocromador es un dispositivo óptico que permite, por medio de un mecanismo, seleccionar y transmitir una… … Wikipedia Español
Artes plásticas — Saltar a navegación, búsqueda Por artes plásticas se entiende una clase de arte al mismo nivel que las artes escénicas, las artes musicales y las artes literarias. Las artes plásticas se diferencian de todas aquellas en su forma de expresión, ya… … Wikipedia Español
Commodore 64 — El hardware de la commodore 64 Tipo Computadora doméstica Desarrollador Commodore International … Wikipedia Español

Los diccionarios y las enciclopedias sobre el Académico