FIGURAS DE UN SOLO TRAZO RECORRIDOS EULERIANOS EJERCICIOS RESUELTOS PDF
RECORRIDO EULERIANO
Un recorrido euleriano o camino euleriano consiste en un trazo continuo que recorre todas las aristas (líneas) de un grafo sin pasar por una arista más de una vez .
Para averiguar si un grafo admite un camino euleriano sin hacer el trazo aplicaremos los postulados de Euler.
PRIMER POSTULADO
Si todos los puntos son pares, entonces el grafo admite un camino euleriano.
SEGUNDO POSTULADO
Si presenta dos puntos impares, entonces el grafo admite un camino euleriano.
TERCER POSTULADO
Si presenta más de dos puntos impares, entonces el grafo no admite un camino euleriano
En estos casos nos pedirán determinar la longitud mínima de dicho trazo (recorrido mínimo).
CAMINOS EULERIANOS
Consiste en un trazo continuo que recorre toda la gráfica sin pasar por ningún lado más de una vez.
El objetivo de esta parte, es verificar sí una figura se puede dibujar de un solo trazo; sin levantar el lapicero del papel, ni pasar 2 veces por una misma línea, y para ello debemos de considerar lo siguiente
Punto Par ó VÉRTICE PAR (P) :
Es aquel punto donde convergen un número par de líneas.
Ejemplo:
Es decir son aquellos puntos de la figura al cuál llegan un número par de líneas.
Son vértices o puntos pares, porque se puede apreciar que convergen 4 y 6 líneas respectivamente.
Llamados también vértice par ; es aquél donde concurren un número par de trazos (líneas rectas o curvas) , tal como lo muestra la siguiente figura:
PUNTO ó vértice IMPAR (I) :
Es el punto en el cual convergen un número impar de líneas.
Es decir son aquellos puntos de la figura al cual llegan un número impar de líneas.
ejemplos :
Llamados también vértice impar; es aquél donde concurren un número impar de trazos (líneas rectas o curvas) , tal como lo muestra la siguiente figura :
Ahora estamos interesados en averiguar, si una figura se puede dibujar completamente de un solo trazo continuo, sin pasar 2 veces por una misma línea. Para tal efecto, haremos uso de los postulados de Euler, quien descubrió y enunció la siguientes conclusiones:
teoremas de euler
TEOREMA 1 :
Una gráfica admite un camino Euleriano si y solo sí todos los puntos son pares (carece de puntos impares).
sí admite un camino Euleriano
Es decir si una figura posee sólo puntos pares , se podrá dibujar de un solo trazo y se puede comenzar por cualquier punto y terminando en el mismo punto.
EJEMPLO 1 :
‘‘La figura se puede dibujar de un solo trazo ,
porque todos sus vértices o puntos de intersección son pares’’.
Ejemplo 2 :
Las 3 figuras si se pueden realizar de un solo trazo, dado que únicamente poseen vértices pares.
Como puedes apreciar en cada una de las figuras mostradas, si la figura carece de puntos impares, entonces se podrá realizar de un sólo trazo comenzando por cualquier punto y acabando en ese mismo punto.
Otro Ejemplo :
En esta figura, observamos que todos los puntos son pares, luego sí se puede construir de un solo trazo continuo.
!recuerda¡
Para que se pueda trazar una figura , sin levantar el lápiz ni repetir ningún trazo , es necesario que todos los puntos de intersección sean pares.
Podemos empezar por cualquier punto par .
TEOREMA 2 :
Una gráfica admite un camino Euleriano si y sólo sí tiene 2 puntos impares.
Sí admite camino Euleriano
Si una figura presenta 2 puntos impares, se podrá dibujar de un sólo trazo, siempre y cuando se empiece en uno de los puntos impares y se termine en el otro.
EJEMPLO 1 :
La figura se puede dibujar de un solo trazo, porque solo presenta 2 puntos impares.
Ejemplo 2 :
Si la figura solo presenta puntos pares y además 2 impares, entonces se podrá dibujar de un solo trazo continuo sin pasar dos veces por una misma línea, siempre y cuando se comience en un punto impar y se termine en el otro impar.
Si se pueden dibujar de un solo trazo, dado que poseen únicamente 2 vértices impares y el resto pares.
Para que una figura se pueda trazar sin levantar el lápiz ni repetir ningún trazo, es necesario que existan a lo más dos vértices impares, siendo los demás vértices pares. Esto significa que, si hay más de dos vértices impares, la figura no se puede realizar de un solo trazo. Siempre debemos empezar por un punto impar y terminar en el otro vértice impar .
TEOREMA 3 :
Una gráfica no admite un camino Euleriano , sí y solo sí tiene más de 2 puntos impares.
no admite camino Euleriano
Si la figura presenta más de 2 puntos impares , es imposible dibujarla de un sólo trazo .
EJEMPLO 1 :
Estas figuras nunca se podrán dibujar de un sólo trazo porque poseen más de 2 puntos impares.
No se puede construir en la figura, por tener más de dos puntos impares.
Si la figura presenta más de 2 puntos impares, entonces no se podrá dibujar de un solo trazo continuo sin pasar dos veces por una misma línea .
TeOREMA DEL RECORRIDO MÍNIMO
Si queremos dibujar una figura que presente más de dos puntos impares de un solo trazo continuo , se deben repetir algunas líneas ¿Cuál es el menor número de líneas que se repiten?
Se presenta 2 casos :
I) Si empezamos de un punto (debe ser impar) y terminamos en un punto distinto (también impar) :
II) Si empezamos en un punto (debe ser impar) y terminamos en el mismo punto :
Las líneas que repitan son líneas impares .
Ejemplo 1 :
Una araña recorre todas las aristas de un cubo en 1 minuto como mínimo. Qué tiempo demora en recorrer una arista.
Aristas de 1 sólo trazo: 12 aristas
Aristas repetidas: (I = 8)
Finalmente:
Observaciones :
* El número de puntos impares de una figura es siempre un número par .
* Para trazar el gráfico de una figura que tiene dos vértices impares se comienza de un vértice impar y se termina en el otro.
* Si se tiene una figura no realizable de un solo trazo (con más de dos vértices impares) , y se realiza de un trazo continuo, aún repitiendo algunos trazos, el número de trazos repetibles está dado por :
Los trazos no tienen que ser consecutivos.
La fórmula dada anteriormente garantiza el número de trazos repetidos, pero no precisa cuál o cuáles de ellas se repiten como mínimo . En tales condiciones , para realizar la figura , se recomienda identificar los puntos impares más cercanos , y repetir los trazos que unen dichos puntos según el número dado por la fórmula .
Ejemplo 1 :
En la siguiente figura , encontrar la longitud del recorrido mínimo que se debe hacer para trazar la figura sin levantar el lápiz del papel.
A) 28cm B) 29cm C) 30cm D) 32cm E)42 cm
Resolución :
# vértices impares = 6
# trazos repetidos
Þ Lmín = 8 + 8 + 10 + 2(2) = 30 cm
rpta : ‘‘C’’
Ejemplo 2 :
El siguiente es un cubo construido de alambre: Calcular el recorrido mínimo de una hormiga para pasar por todas las aristas.
# de puntos impares : I=8
# mínimo de líneas repetidas:
Recorrido mínimo = (12+3)(10) = 150
BUENA COLORACIÓN DE MAPAS
(Número Cromático)
Es el menor número de colores necesarios para colorear cualquier mapa con la condición que 2 países fronterizos estén pintados de colores diferentes.
Ejemplo:
Teorema de los cuatro colores :
Dibujando muchos mapas se ha demostrado que es siempre suficiente 4 colores como máximo para colorear un mapa en el plano.