Recorriendo el dodecaedro

abril 7, 2007

Demostrar que no existe un camino que recorra todas las aristas de un dodecaedro dos veces (una en cada sentido) sin ir y volver por la misma arista en dos movimientos consecutivos.

7 comentarios to “Recorriendo el dodecaedro”

  1. marcossarini said

    Hasta ahora sólo conseguí las siguientes cosas:

    Pensemos que el dodecaedro es un planeta y nosotros caminamos por su superficie.

    Como el grado de los vértices es tres, al llegar a un vértice y partir de él, siempre deberemos doblar a la derecha o a la izquierda (no podemos volver por el mismo camino). Se puede demostrar fácilmente (a partir de la restricción de que queremos pasar por cada arista una vez en cada sentido) que las tres veces que llegamos al mismo vértice, doblamos para el mismo lado. Por lo tanto, se puede asignar a cada vértice del dodecaedro una letra I o D, que nos diga para dónde doblar.

    Una vez asignadas las letras, nos paramos en una arista y empezamos a caminar. Si respetamos las letras hasta que volvemos a la arista inicial en la dirección inicial, nos aseguramos no pasar dos veces por la misma arista en la misma dirección, pero no es seguro que vayamos a recorrer todos los tramos: puede que volvamos a donde salimos, cerrando un ciclo, pero que este ciclo no cubra todos los tramos. Entonces, podemos ir a un tramo no recorrido aún, y hacer lo mismo. Si armamos ciclos hasta que no queden más tramos por recorrer, quedará recorrido todo el dodecaedro pero en varios ciclos. Queremos que sea un sólo ciclo.

    Observemos que si ponemos todas D o todas I, el dodecaedro queda cubierto por 12 ciclos, y cada ciclo consiste en recorrer el perímetro de una arista. Ahora, la cantidad mínima de ciclos que pude obtener es 2, y siempre obtengo una cantidad par.

    También probé con un tetraedro y un cubo, que tienen todos vértices de grado tres, con los mismos resultados (siempre cantidad par de ciclos). Los dos tienen cantidad par de caras, así que la coloración trivial (todas D o todas I) conduce a una cantidad par de ciclos.

  2. charlydif said

    Creo haber probado que la cantidad de ciclos es par. Si no quieren que lo termine no sigan leyendo. O sea….una vez que sabemos que tiene que ser par es facil probarlo, alcanza con cambiar de a una las letras. Hay 3 o 4 casitos e hice un par y todos salen igual asi que supongo que todos salen igual.

  3. marcossarini said

    Sí, salen.

  4. tey said

    cual es la medida de un dodecaedro

  5. Grin Without a Cat said

    Supongamos que se puede, y que existe un camino \gamma.

    Elijamos una orientación para cada una de las aristas del dodecaedro, y a cada una de ellas pongámosle un nombre: a, b, etc. Elijamos un vértices x_0 y recorramos el camino \gamma, armando a medida que avanzamos una palabra w con las letras que son los nombres de las aristas y sus inversas formales (a^{-1}, b^{-1}, etc) de acuerdo a que avancemos por una arista en la dirección elegida o en la contraria, hasta llegar al vértice x_0 de partida. Así, si la palabra obtenida es abc^{-1}de^{-1}\dots, es porque el camino empieza recorriendo la arista a en su dirección elegida, después la b otra vez en la dirección elegida, después la c en la dirección contraria a la elegida, y así… Es claro que como el vértice x_0 es arbitrario, así como las orientaciones que elegimos para las aristas, la palabra que obtenemos de esta forma está bien definida por el camino a menos de permutaciones cíclicas de sus símbolos e intercambios de una letra por su inversa formal. Como el dodecaedro tiene 30 aristas, nuestra palabra w tiene 60 símbolos.

    Consideremos ahora el grafo \Gamma cuyos vértices y lados son los del dodecaedro, y consideremos a \Gamma como un espacio topológico. Consideremos, por otro lado, un 60-gono regular D (lleno) con borde \partial D. Usando la palabra w podemos construir una función continua f:\partial D\to\Gamma, usándola como «instrucciones para recorrer a \Gamma».

    Sea X=\Gamma\cup_f D es espacio que se obtiene de \Gamma pegándole el disco D vía la función f. Es fácil ver, usando la propiedad especial que satisface el camino \gamma y el hecho de que el grafo \Gamma es cúbico, que el espacio X es una 2-variedad orientable compacta.

    Ahora bien, por construcción X es un CW-complejo, que se construye usando veinte puntos, treinta 1-celdas y una 2-celda. En particular, su característica de Euler es \chi(X)=20-30+1=-9.

    Esto es imposible porque toda 2-variedad orientable y compacta tiene característica de Euler par.

    Notemos que exactamente el mismo argumento se aplica al tetraedro, al cubo y a todo grafo cúbico con un número par de aristas (si un grafo con n vértices es cúbico, entonces tiene \frac32n aristas, así que necesariamente n es par—la característica de Euler del espacio X que se obtiene de él, entonces, es impar)

  6. Grin Without a Cat said

    No sé que fué lo que hizo Carlos… pero la idea de las Is y las Ds termina bien si observamos que cuando uno cambia una I por una D o una D por una I en una coloración, la paridad de la cantidad de ciclos no cambia. Como la coloración trivial en la que todos los vértices tienen una I tiene un número par de ciclos (uno por cara y el dodecaedro tiene 12 caras (¡!)), y como todas las coloraciones se obtienen de la trivial cambiando de a uno el color de los vértices, vemos que toda coloración tiene un número par de ciclos. En particular, ninguna coloración tiene un solo ciclo.

    Este argumento se aplica tal cual a todo grafo cúbico y plano con un número par de aristas (porque en ese caso el número de caras es par en todo dibujo del grafo en la esfera)

    Observemos que el argumento de mi comentario anterior no necesita la planaridad del grafo. Este segundo argumento se arregla si observamos que todo grafo cúbico puede dibujarse bien un alguna superficie orientable (en realidad todo grafo, cúbico o no, puede dibujarese bien en alguna tal superficie—pero solo necesito grafos cúbicos ahora), y que toda superficie orientable tiene característica de Euler par. Así, en ultima instancia, las dos demostraciones están basadas en la misma cosa😉

    PS: Se me ocurre por lo menos una generalización a grafos no cúbicos… ¿Ideas?

  7. Grin Without a Cat said

    Un problema…

    Sea \Gamma un grafo cúbico dibujado en una superfiecie compacta orientable, orientada y sin borde S (como las consideradas arriba; supongo además que todas las regiones en las que queda partida S tiene son discos y, en particular, tienen su borde conexo—esta condición está implicita en mi comentario anterior…) Sea \Sigma elconjunto de todas las \{I,D\}-coloraciones de \Gamma.

    Para cada \sigma\in\Sigma, sea n(\sigma) el número de ciclos en los que queda recorrido \Gamma siguiendo la regla de Marcos, sea q una variable, y consideremos el polinomio

    f_\Gamma(q)=\sum_{\sigma\in\Sigma} q^{n(\sigma)}.

    ¿Alguien puede decir algo sobre f_\Gamma? Lo que probamos arriba nos dice que f_\Gamma es de hecho un polinomio en q^2, por ejemplo. Parece muy complicado de calcular en general: ¿hay alguna recurrencia (por ejemplo, con respecto a la operación de sacarle un arco a \Gamma y arreglarlo para que vuelva a quedar cúbico, o cosas por el estilo?

    LATER: Un grafo planar 3-conexo se puede dibujar de una única forma en el plano (esto es un teorema de Whitney), así que f_\Gamma es un invariante del grafo en ese caso, no del embedding.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: