Guía 7, Ejercicios 9 a 15
La Guía 7 cambia de estructura y no de lenguaje. Hasta acá el tipo traía un orden, o dos operaciones, o las dos cosas; un grafo es más pobre: un conjunto de vértices y una relación binaria r simétrica y sin lazos —nadie es vecino de sí mismo—, sin orden, sin operaciones, sin nada más. Las fórmulas de la nota anterior siguen escribiéndose igual — lo único que cambió es qué símbolos tiene el tipo a mano.
Sobre esa estructura tan flaca la guía hace una pregunta que no se parece a ninguna de las anteriores. Bicolorear un grafo es pintar cada vértice con uno de dos colores de modo que ninguna arista una dos vértices del mismo color. No se pide que los dos colores se usen, ni que queden parejos: sólo que ninguna arista sea monocromática.
Abajo está el triángulo, que es donde esto se pone interesante por primera vez. Tocá un vértice y pasa de sin pintar a lleno, de lleno a hueco, y de hueco a sin pintar otra vez. Las aristas que unan dos del mismo color se van a marcar solas.
Los dos colores se dibujan como lleno y hueco, los dos en azul, y no como dos tonos distintos. En este sitio el rojo significa una sola cosa —acá algo falla— y en este widget lo necesitamos entero para las aristas monocromáticas, que son exactamente donde el bicoloreo se rompe. Pintar la mitad de los vértices con el color del fracaso diría dos cosas con un mismo color.
Lo que acaba de pasar tiene una demostración de un renglón, y es el Ejercicio 14: en un triángulo los tres vértices son vecinos de a pares, así que los tres tendrían que llevar colores distintos de a pares — y hay dos colores. Tres cosas distintas no entran en dos cajas.
Con tres vértices y dos colores hay ocho pinturas completas, que son las de dos elevado a tres, y el contador lleva la cuenta de cuáles probaste. No hace falta agotarlas para creerle al ejercicio, pero agotarlas es barato y la diferencia entre «no me sale» y «las probé todas» es la diferencia entre una sospecha y una prueba. El mínimo alcanzado no baja de uno.
El ejercicio termina ahí, y está bien que termine ahí. Lo que sigue es lo que el ejercicio no dice.
El mismo widget, ahora con cinco grafos y un botón. El botón le pregunta a bicolorear, que hace una búsqueda en anchura alternando colores entre un vértice y sus vecinos, y que devuelve una de dos cosas: un bicoloreo concreto, o el ciclo donde la búsqueda se chocó consigo misma. Las dos respuestas vienen con su testigo dibujado, porque «no se puede» sin el testigo es una afirmación y no una prueba.
Empezá por el cuadrado y el camino de cuatro: los dos salen, y salen a la primera. Seguí con el triángulo y con el K4 —cuatro vértices, todos vecinos entre sí— y mirá la lectura de ciclos de largo 3: el triángulo tiene uno, el K4 tiene cuatro, y ninguno de los dos se pinta. Hasta acá la regla del Ejercicio 14 explica todo lo que ves.
Y después está el pentágono. Miralo antes de preguntarle nada al módulo: buscá un triángulo adentro. No hay. Ninguna terna de sus vértices es vecina de a pares, y la lectura de ciclos de largo 3 marca cero. Ahora intentá pintarlo.
El pentágono tiene cero ciclos de largo 3 y tampoco se bicolorea. El testigo que devuelve el módulo no es un triángulo: es el pentágono entero, un ciclo de largo 5.
Ahí se ve qué parte de la demostración del Ejercicio 14 estaba haciendo el trabajo de verdad. Recorré un ciclo pintando: cada paso va a un vecino, y un vecino obliga a cambiar de color, así que el color alterna paso a paso. Después de un número par de pasos volvés al color con el que saliste; después de un número impar, al otro. Y un ciclo se cierra volviendo al vértice de partida. Si su largo es par no pasa nada. Si su largo es impar, el vértice de partida tendría que ser distinto de sí mismo.
El número tres no aparece en ningún lado de ese argumento. Lo único que se usa es impar. El triángulo es el ciclo impar más chico que existe, y por eso es el caso que la guía manda probar: se demuestra sin recorrer nada, contando tres vértices y dos cajas. Pero la regla que se aprende con él es más chica que la regla verdadera, y el pentágono es el primer contraejemplo de la regla chica.
La vuelta también vale, y eso ningún ejercicio lo pide: un grafo se bicolorea si y sólo si no tiene ningún ciclo de largo impar. bicolorear es literalmente esa demostración escrita como programa — pinta por anchura alternando, y si nunca choca, lo que terminó de pintar es el bicoloreo; si choca, el camino de vuelta por el árbol de búsqueda es el ciclo impar. Está verificado sobre los 1024 grafos de cinco vértices, que son los subconjuntos de los diez pares posibles, y no hay una sola discrepancia entre las dos cosas.
El Ejercicio 14 no está mal ni está incompleto. Pide el caso más chico, que es el único que se prueba de un renglón, y ese renglón es el que conviene tener escrito en el parcial. Lo que está incompleto es la lectura que uno se lleva sin darse cuenta: «el problema son los triángulos». El problema no eran los triángulos. El triángulo era el caso más chico de algo más grande, y la guía —que lo sabe— eligió pedir el caso chico.
Vale la pena mirar el K4 con eso en la cabeza. Tiene cuatro ciclos de largo 3, uno por cada terna de sus cuatro vértices, y sus cuatro valencias valen 3: cada vértice ve a todos los demás. El Ejercicio 14 lo tumba cuatro veces seguidas, y alcanzaba con una.
Los ejercicios 9 a 12 piden otra cosa y es el mismo movimiento de la nota anterior, ahora sobre un tipo con una sola relación binaria: escribir fórmulas que digan «x tiene valencia 3», «no hay cliques de cardinal 4», «no hay ciclos de largo 4». La lectura de valencias del widget es la que contestaría la primera, y el K4 es su ejemplo: una fórmula que diga «x tiene valencia 3» tiene que nombrar tres vecinos distintos y además negar que exista un cuarto, porque el lenguaje no sabe contar — sólo sabe nombrar y negar.
Y de paso queda insinuado por qué el bicoloreo entra en una guía de lógica y no en una de grafos. Mirá qué forma tiene cada uno de los dos lados de la equivalencia. «No hay ciclos de largo 3» se escribe con una fórmula del lenguaje, igual que la nota anterior escribía las suyas; «no hay ciclos de largo 5» también, y así una por cada largo impar — pero son infinitas, y una fórmula es una palabra finita. «Este grafo se bicolorea», del otro lado, habla de repartir los vértices en dos partes, y el tipo de un grafo no tiene ningún símbolo con el que nombrar una parte. La equivalencia cruza esas dos formas de decir, y cuándo se puede cruzarlas es la clase de pregunta con la que arranca la Guía 8.
Sirve para los ejercicios 9 a 15 de la Guía 7. Los cinco grafos de esta nota son los mismos que fija test/grafo.test.js, junto con el recorrido de los 1024.