El modelo es un grafo dibujado en el plano. Hay seis vértices: A, B, C, D, E y F. No representan poblaciones ni cantidades medidas: son puntos del dibujo, y las aristas son los segmentos que los unen.
El grafo no está dirigido. La arista que une A con B se escribe AB, y es la misma que BA.
Lista de aristas, leída del dibujo:
AB, BC, CD, DE, EF, FA y BD.
Son 7. Las seis primeras forman el contorno. BD es la cuerda que cruza por dentro, de B a D.
El grado de un vértice es el número de aristas que inciden en él. En un grafo sin dirección, cada arista suma uno al grado de cada extremo, así que la suma de todos los grados es el doble del número de aristas.
Condición que vamos a decidir en el dibujo: si existe un camino que pase exactamente una vez por cada arista. Puede repetir vértice. No puede repetir arista ni dejarse ninguna.
Suma: 2 + 3 + 2 + 3 + 2 + 2 = 14. Y 2·7 = 14. El dibujo y la lista no se contradicen.
Grados impares: solo B y D. Hay exactamente dos. Por eso, si existe un camino que use cada arista una vez, tiene que empezar en uno de esos dos vértices y acabar en el otro.
Camino: B–A–F–E–D–C–B–D.
Salen las siete aristas de la lista: AB, FA, EF, DE, CD, BC y BD. Ninguna se repite y no falta ninguna. El camino empieza en B y acaba en D, los dos vértices de grado impar.
B aparece dos veces, al principio y en el penúltimo puesto. Eso está permitido: la condición habla de aristas, no de vértices.
Rechazar el camino porque repite el vértice B. La condición no era «pasar una vez por cada vértice». Era «pasar una vez por cada arista». Un camino que no repite vértices, en este grafo, no puede cubrir las siete aristas: seis vértices seguidos solo producen cinco aristas.
El otro fallo es contar AB y BA como dos aristas. El grafo no tiene flechas. Si las doblas, la lista deja de tener 7 y la suma de grados deja de cuadrar con el dibujo.
Los seis vértices y las siete aristas. La cuerda es BD.
El control es el número de aristas ya recorridas, de 0 a 7. El camino fijo es B–A–F–E–D–C–B–D.
Se guarda solo en este navegador (bach1-mates-i-L24).
Cada una de las 7 aristas aporta 2 a la suma de grados, uno por extremo. 2·7 = 14, y 2 + 3 + 2 + 3 + 2 + 2 = 14. Si al contar un vértice te saliera otra suma, te has dejado una arista o has contado AB dos veces.
Las siete usadas, leídas sin sentido, son AB, FA, EF, DE, CD, BC y BD. La lista del dibujo es AB, BC, CD, DE, EF, FA y BD. Es el mismo conjunto: siete aristas distintas, así que no falta ninguna y no sobra ninguna.
Dar la vuelta es D–B–C–D–E–F–A–B. Las aristas, en orden, son BD, BC, CD, DE, EF, FA y AB. Otra vez las siete, sin repetir. Empieza en D y acaba en B. Encaja con los dos únicos grados impares.
No hace falta para la lección. Si tienes una placa, este boceto solo escribe por el puerto serie el orden del camino ya comprobado: B, A, F, E, D, C, B, D. Sirve para ver que el camino es una lista ordenada de vértices, la misma de la figura. No mide nada y no añade aristas.
/* Opcional. Orden del camino de la lección.
La lección está completa sin esta placa. */
const char *orden[] = {"B", "A", "F", "E", "D", "C", "B", "D"};
void setup() {
Serial.begin(9600);
}
void loop() {
for (int i = 0; i < 8; i++) {
Serial.println(orden[i]);
delay(500);
}
}
Escribe el razonamiento completo. Si necesitas un boceto, dibújalo en el lienzo de esta misma página.
Seis vértices, siete aristas, grados 2, 3, 2, 3, 2 y 2, suma 14. El camino B–A–F–E–D–C–B–D recorre cada arista una vez y acaba en el otro vértice de grado impar.
Di si un camino que use cada arista de este grafo exactamente una vez puede empezar en A. Apóyate en el grado de A, que ya está calculado, y no cambies la lista de aristas.
reto_id: bach1-mates-i-L24