No Aquí hay un contraejemplo.
Considere una gráfica de 5 vértices que es la unión de un triángulo {a, b, c} y una arista {d, e}. Demostraremos que es imposible asignar subconjuntos de S = {1,2,3,4,5} a los vértices de este gráfico de modo que dos vértices sean adyacentes en el gráfico si los subconjuntos son disjuntos.
Primero, tenga en cuenta que si existe una asignación, ninguno de los vértices puede asignarse al conjunto nulo; esto implicaría que el vértice es adyacente a todos los demás vértices, pero no existe ningún vértice de grado 4 en el gráfico.
- ¿Existe un algoritmo para encontrar el día de cualquier fecha de cualquier año?
- ¿Qué te dirías a ti mismo cuando recién comenzaste a programar, aprender algoritmos?
- ¿Cuál es la diferencia entre recursividad e iteraciones brevemente?
- ¿Cuál debería ser mi rutina para dominar el algoritmo y la estructura de datos?
- ¿Cuáles son los algoritmos más rápidos para colorear los bordes en un gráfico con max_degree + 1 colores?
Ahora, {a, b, c} es un triángulo. Si existe una asignación válida, los subconjuntos correspondientes a estos vértices deben estar separados por pares. Pero la cardinalidad de S es 5. Por principio de casillero, debería haber al menos un vértice en el triángulo que se asigna a un subconjunto con un elemento. Sin ninguna pérdida de generalidad, deje que se asigne al vértice a el subconjunto {1}.
Pero no hay borde entre los vértices ad y ae. Esto significa que los subconjuntos correspondientes a a y d (de forma similar a y e) deberían tener algún elemento común. Como el subconjunto correspondiente a a es {1}, esto significa que 1 debería ser un elemento de los subconjuntos correspondientes a d y e.
Pero esto implicaría que los subconjuntos para dye no son disjuntos. Por lo tanto, no puede haber un límite entre dye, una contradicción.
