Triàngul monocromàtic
El problema del triàngul monocromàtic és un problema de decisió que pertany a la classe dels problemes NP-complets.
- Entrada: Un grafo no dirigit G(V,I), a on V és un conjunt de n vèrtiços i I és el conjunt d'arestes.
- Pregunta: ¿Pot el conjunt I ser particionado en dos conjunts disjuntos E1 i E2, tals que cap dels dos grafos G1(V,E1) i G2(V,E2) continguen un triàngul; és dir, tal que para tots els vèrtiços de E1 i E2, no existixca un conjunt {o,v,w} tal que les arestes {o,v}, {o,w}, {v,w} estiguen definides?
Vore també
[editar | editar còdic]Referències
[editar | editar còdic]- Erro en la seqüencia d'órdens: no existix el mòdul «Citas».. A1.1: GT6, pg.191.θ
- Este artícul conté una traducció derivada de «Triángulo monocromático» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.