Ir al contenido principal

Tarea 14, Matemáticas discretas

Fecha de entrega: 25 de mayo


Problema 1


Sea G el grafo cuyos vértices corresponden a las aristas de $latex K_5$, y en el cual son adyacentes si dichas aristas tienen un vértice en común. Calcula el número cromático de G.

 Problema 2



  1. Muestra que las regiones formadas por rectas en el plano son 2-coloreables.

  2. Muestra que las regiones formadas por una curva cerrada en el plano (que posiblemente se interseca a sí misma) son 2-coloreables.


Problema 3


Da un ejemplo de un mapa, con países no necesarimente conexos, que no sea 100-colorable.

Problema 4



  1. Si cada cara de un mapa planar tiene un número par de aristas, entonces el grafo es bipartito.

  2. Si cada vértice de un mapa planar tiene grado par, entonces las caras son 2-coloreables.


Problema 5


FanoConsidera el plano de Fano $latex \mathcal F$ visto en clase.

  1. Representa cada recta en el plano de Fano por un punto, y cada punto x de $latex \mathcal F$ como una recta que contiene, como puntos, a las rectas en $latex \mathcal F$ que pasan por x. Describe el espacio geométrico obtenido.

  2. Un conjunto de 3 puntos en $latex \mathcal F$ que no pertenecen a una recta es llamado un círculo, y una tangente al círculo es una recta que pasa por uno solo de sus puntos. Muestra que para cada punto de un círculo existe una única tangente que pasa por él.

  3. Un hipercírculo es un conjunto de 4 puntos en $latex \mathcal F$ tal que no 3 de ellos pertenecen a una recta. Muestra que los 3 puntos afuera de un hipercírculo forman una recta, y viceversa.

  4. Describe la manera en que podemos rearreglar los puntos de $latex \mathcal F$ de tal forma que, digamos, el vértice superior de la representación vista en clase ocupa ahora el punto central.


Problema 6


Un laboratorio tiene 7 empleados, y cada uno trabaja en tres días distintos de la semana de la siguiente forma: Karla el lunes, martes y jueves, Jaime el martes, miércoles y viernes, etc. Muestra que cada dos empleados se ven solo un día a la semana, y que en cualquiera dos días de la semana hay un empleado que trabaja en ambos. ¿Cuál es la relación con el plano de Fano?

Problema 7


El orden de un plano proyectivo es el número n tal que cada recta tiene n+1 puntos. Muestra que un plano proyectivo de orden n tiene en total $latex n^2+n+1$ puntos y $latex n^2+n+1$ rectas.

Problema 8


Dibuja un plano proyectivo de orden 4. (Sugerencia: considera el campo $latex \mathbb F_4 = \{0, 1, \alpha, 1 + \alpha\}$ visto en clase.)

Comentarios