Planar slink

Estuve la semana pasada en el Instituto Fields y asistí a una plática de Jack Edmonds, en la cual  planteó este problemilla. No se me ocurre una traducción aceptable de planar slink, así que no lo traduciré.

Versión 1.

Imagina que tienes una cuadrícula de m×n. Dos jugadores se turnan como sigue: el primer jugador escoge una casilla y cada uno elige sucesivamente una casilla contigua (unida por un lado) desocupada, como en este ejemplo:

Ejemplo de "slink" plano

Pierde el primer jugador que no pueda continuar.

La pregunta natural es: ¿Existe alguna estrategia ganadora para alguno de los dos jugadores? Si es así ¿cuál es?

De acuerdo con Edmonds, este problema está relacionado con apareamientos en gráficas bipartitas.  ¿Cual sería esta relación?

Por ahora lo dejamos aquí, en una entrada posterior hablamos del slink en gráficas planas arbitrarias

Anuncios

Examen parcial: Matemática discreta

Este es el 3er parcial del curso de matemática discreta (tema: teoría de gráficas).

  1. Sea G una gráfica simple sin ciclos. Demuestra que |E| = |G|-\omega(G).
  2. Sea G una gráfica simple (posiblemente disconexa). Si G es 4-regular, entonces puedes colorear las aristas de rojo o azul de forma que cada vértice tenga el mismo número de aristas de cada color.
  3. Si en una gráfica simple cada vértice tiene grado k (k\ge 2), prueba que debe existir un ciclo de longitud mayor o igual a k+1.
  4. Si G, H son dos gráficas simples con el mismo número de vértices y las listas ordenadas de los grados de los vértices en cada gráfica son iguales, ¿necesariamente son gráficas isomorfas?
  5. Sea G una gráfica con 10 vértices y 38 aristas. Demuestra que contiene a K_4 como subgráfica inducida.
  6. ¿Cuantos automorfismos tiene la gráfica siguiente?