Cosas con M

‘They were learning to draw,’ the Dormouse went on, yawning and rubbing its eyes, for it was getting very sleepy; ‘and they drew all manner of things—everything that begins with an M—’

‘Why with an M?’ said Alice.

‘Why not?’ said the March Hare.

Alice was silent.

Lewis Carroll, Alice in Wonderland.

Si es un grafo (simple, sin lazos, no orientado) finito, una inmersión extraña de en el plano es una forma de dibujarlo en el plano de manera tal que (i) los vértices son todos distintos, (ii) cada arco es un arco de Jordan (sin problemas podemos suponer que son suaves o lineales a trozos), (iii) si dos arcos se intersecan lo hacen o bien en un extremo común o bien en puntos interiores de los dos, y en este segundo caso la intersección es transversal, y (iv) se cumple la condición de que todo par de arcos se interseca una vez.

¿Puede dar ejemplos?

El grafo tenía un papelito que decía “pintame”

Cuando decimos “pintar un grafo” nos referimos a asignar a cada vértice un color, de forma que dos vértices unidos por una arista tengan colores distintos.

Demostrar que un grafo puede pintarse con k colores distintos si y sólo si cada subgrafo finito puede pintarse con k colores distintos.

Art Gallery Problem

a) Se tiene un grafo conexo con vertices, hallar la menor cantidad de vertices (en funcion de ) que podemos escoger de forma que todo vertice del grafo sea vecino de uno de ellos (un vertice es vecino de si mismo).

b) Tenemos un museo que tiene forma de poligono y deseamos ubicar algunos guardias para vigilar las paredes. Cada guardia debe permanecer siempre en el mismo lugar pero puede darse vuelta. Si el museo tiene paredes probar que guardias alcanzan para vigilar todas las paredes.