Seminario de análisis combinatorio

Segunda tarea Se entrega el martes 6 de noviembre

1. Prueba que:

a) La trayectoria T_{n} tiene un único núcleo.

b) El ciclo C_{2n} tiene exactamente dos núcleos.

c) El ciclo C_{2n+1} no tiene núcleos.

2. Prueba que todo núcleo es un seminúcleo y que existen seminúcleos que no son núcleos.

3. Prueba que tienen seminúcleo no vacío y, por lo tanto, tiene núcleo: a) Las digráficas acíclicas.

b) Las digráficas simétricas.

c) Las digráficas transitivas.

4. Prueba que toda digráfica sin núcleo tiene una subdigráfica inducida que es núcleo-imperfecta crítica.

5. Prueba que si D es una digráfica núcleo-imperfecta crítica entonces D no tiene seminúcleos diferentes al vacío.