Trazo de figuras 1

1.1. ¿Qué es un grafo?

Un grafo es un esquema formado por:

• vértices o nodos: puntos donde confluyen, nacen o terminan las líneas;
• aristas o arcos: tramos que unen dos vértices.

En trazo de figuras trabajamos con figuras geométricas que podemos convertir en grafos.

En el temario se suele llamar puntos de corte o p. cte. a los puntos donde se juntan o cruzan dos o más líneas. Por ejemplo, si dos diagonales se cruzan dentro de un cuadrado, el punto de cruce es un punto de corte y debe contarse como vértice.

En una figura de alambre, un vértice puede ser:

• un extremo libre;
• una esquina;
• un punto de unión de dos o más varillas;
• un cruce entre líneas si están unidas.

1.2. Grado de un vértice

El grado de un vértice es el número de aristas que llegan a él.

Ejemplo: en un cuadrado con una diagonal $AC$,

• En $A$ llegan tres líneas: $AB$, $AD$ y $AC$. Por eso, $A$ tiene grado 3.
• En $B$ llegan dos líneas: $BA$ y $BC$. Por eso, $B$ tiene grado 2.
• En $C$ llegan tres líneas: $CB$, $CD$ y $CA$. Por eso, $C$ tiene grado 3.
• En $D$ llegan dos líneas: $DA$ y $DC$. Por eso, $D$ tiene grado 2.

1.3. Vértices pares e impares

A partir del grado clasificamos los vértices:

En el cuadrado con diagonal anterior:

• $A$ y $C$ son vértices impares;
• $B$ y $D$ son vértices pares.

1.4. Propiedad fundamental

En todo grafo, la cantidad de vértices impares siempre es un número par.

Esto se debe a que cada arista aporta 2 al total de grados: uno por cada extremo. Por lo tanto, la suma de todos los grados es el doble del número de aristas, es decir, un número par. Entonces no puede haber un número impar de vértices impares.

2.1. ¿Qué es un recorrido euleriano?

Un recorrido euleriano es un trazo continuo que:

• no levanta el lápiz del papel;
• recorre todas las aristas de la figura;
• no repite ninguna arista.

Decimos que una figura admite un recorrido euleriano cuando se puede dibujar de un solo trazo continuo y sin repetir ninguna línea.

No toda figura lo admite. Para saber si una figura lo admite, no es necesario intentar dibujarla; basta aplicar los postulados de Euler.

Suponemos siempre que la figura es conexa, es decir, que no está formada por partes separadas.

2.2. Primer postulado de Euler

Si en un grafo todos los vértices son pares, entonces admite un recorrido euleriano cerrado.

Esto significa que se puede comenzar en cualquier vértice y terminar en el mismo vértice.

Ejemplo: un cuadrado simple tiene cuatro vértices de grado 2. Todos son pares. Por eso se puede dibujar de un solo trazo sin repetir, comenzando en cualquier vértice y terminando en ese mismo vértice.

2.3. Segundo postulado de Euler

Si en un grafo hay exactamente dos vértices impares, entonces admite un recorrido euleriano abierto.

En este caso, el trazo debe comenzar necesariamente en uno de los vértices impares y terminar en el otro vértice impar.

Ejemplo: el cuadrado con una diagonal tiene dos vértices impares: $A$ y $C$. Por lo tanto, se puede dibujar de un solo trazo sin repetir, comenzando en $A$ y terminando en $C$, o comenzando en $C$ y terminando en $A$.

2.4. Tercer postulado de Euler

Si en un grafo hay más de dos vértices impares, entonces no admite un recorrido euleriano.

Esto significa que no se puede dibujar de un solo trazo sin repetir. Para dibujarlo de un solo trazo continuo, será necesario repetir algunas líneas.

Ejemplo: un cuadrado con sus dos diagonales tiene cuatro vértices impares: sus cuatro esquinas. Como hay más de dos impares, no se puede dibujar sin repetir.

3.1. La idea central

Cuando una figura tiene más de dos vértices impares, ya sabemos que no se puede recorrer sin repetir.

Entonces aparece la pregunta práctica:

¿Cuál es la mínima longitud que debe recorrer el lápiz, la hormiga o el robot para pasar por toda la figura en un trazo continuo?

La respuesta es:

$$L_{\text{mín}} = L_0 + L_{\text{rep}}$$

Donde:

• $L_0$: suma de las longitudes de todas las aristas originales de la figura.
• $L_{\text{rep}}$: mínima suma de longitudes de las aristas o trayectorias repetidas.

3.2. ¿Por qué repetir cambia la paridad?

Cada vez que repetimos una trayectoria entre dos puntos:

• los puntos intermedios no cambian su paridad, porque entramos y salimos de ellos;
• los dos extremos sí cambian su paridad: si eran pares se vuelven impares, y si eran impares se vuelven pares.

Por eso, para lograr un recorrido de un solo trazo continuo, repetimos trayectorias que pares de vértices impares, o que conviertan en impares a los puntos que necesitamos como inicio y fin.

Una trayectoria repetida no necesariamente es una sola arista; puede ser una cadena de varias aristas.

3.3. Procedimiento general para calcular el recorrido mínimo

Sea $I$ el número de vértices impares de la figura original.

Paso 1: Convierte la figura en un grafo y marca los grados de todos los vértices.

Paso 2: Calcula $L_0$, la suma de las longitudes de todas las aristas originales.

Paso 3: Determina qué vértices deben ser emparejados mediante repeticiones, según la condición del problema.

Paso 4: Empareja esos vértices usando los caminos más cortos posibles, sin compartir extremos.

Paso 5: Suma las longitudes de esos caminos repetidos. Ese resultado es $L_{\text{rep}}$.

Paso 6: Aplica $L_{\text{mín}} = L_0 + L_{\text{rep}}$.

3.4. Casos según la condición

Caso A: No hay condición de inicio y fin

Si no nos dicen dónde empezar ni dónde terminar, podemos elegir los extremos del recorrido.

• Si $I = 0$ o $I = 2$, no hay que repetir.
• Si $I > 2$, se dejan dos vértices impares como inicio y fin, y se emparejan los $I-2$ restantes.

Entonces el número de pares a repetir es:

$$\frac{I-2}{2}$$

La clave es elegir cuáles dos impares se dejan sin emparejar para que la suma de las repeticiones sea mínima.

Caso B: El recorrido debe empezar y terminar en el mismo punto

Esto obliga a que, después de repetir, todos los vértices queden pares.

Entonces se deben emparejar todos los vértices impares originales.

Número de pares a repetir:

$$\frac{I}{2}$$

Caso C: El recorrido inicia en $P$ y termina en $Q$, con $P \neq Q$

Aquí hay que distinguir si $P$ y $Q$ son originalmente pares o impares.

Una vez formada la lista de vértices que deben emparejarse, se calculan las distancias más cortas a lo largo de la figura entre cada posible pareja y se elige el emparejamiento total de menor suma.

3.5. ¿La pregunta pide longitud o número de líneas repetidas?

Hay dos variantes muy comunes:

1. Cálculo de longitud mínima
   Suma las longitudes de las aristas repetidas.

2. Cálculo del número de aristas repetidas
   Después de elegir el emparejamiento mínimo, cuenta cuántas aristas individuales aparecen en las trayectorias repetidas.

4.1. Cálculo rápido de $L_0$

En lugar de sumar arista por arista al azar, conviene:

• contar primero los lados verticales;
• luego los horizontales;
• después las diagonales;
• por último las curvas o arcos.

En un cuadrado de lado $a$:

• cada lado mide $a$;
• cada diagonal mide $a\sqrt{2}$.

En una malla de cuadrados, no sumes los perímetros de cada cuadrado por separado, porque las aristas compartidas se contarían dos veces.

4.2. Emparejamiento mínimo de impares

Para encontrar $L_{\text{rep}}$ con rapidez:

1. Ubica todos los vértices impares.
2. Observa qué parejas pueden unirse por una arista corta.
3. Compara sobre todo:
   • unir dos impares por un lado: longitud $a$;
   • unir dos impares por una diagonal: longitud $a\sqrt{2}$;
   • unir dos impares por dos lados: longitud $2a$.
4. Elige parejas sin compartir un mismo vértice.
5. Si hay varias posibilidades, calcula la suma de cada emparejamiento y quédate con la menor.

En la mayoría de problemas de San Marcos, los impares están dispuestos de manera que la mejor opción es unir parejas de impares por las aristas más próximas.

4.3. Figuras curvas

Una circunferencia, un arco o una semicircunferencia se tratan como una arista o como un conjunto de aristas.

Por ejemplo, si una circunferencia está dividida en seis arcos congruentes, cada arco es una arista. Los puntos de división son vértices.

Si una circunferencia tiene radios, cada radio es una arista. El centro es un vértice con grado igual al número de radios que llegan a él.

4.4. Figuras espaciales: cubos y sólidos de alambre

El método es exactamente el mismo.

Un cubo de alambre tiene:

• $8$ vértices;
• $12$ aristas;
• cada vértice tiene grado 3.

Por lo tanto, en un cubo todos los vértices son impares.

Entonces:

• sin condición: se emparejan $8-2=6$ impares, es decir, $3$ pares;
• si debe iniciar y terminar en el mismo punto: se emparejan los $8$ impares, es decir, $4$ pares.

Como las trayectorias más cortas entre vértices impares de un cubo son las aristas de longitud $a$, el cálculo se vuelve rápido.

Ejemplo rápido: cubo de arista $a=5$ cm.

$$L_0 = 12(5) = 60 \text{ cm}$$

Si se inicia y termina en vértices distintos, por ejemplo $P$ y $Q$ adyacentes, hay que repetir $3$ aristas:

$$L_{\text{rep}} = 3(5) = 15$$

Entonces:

$$L_{\text{mín}} = 60 + 15 = 75 \text{ cm}$$