Seminario de análisis combinatorio

Primera tarea

1. Definir la matriz de incidencia hacia I^{−}(D) y usarla para demostrar

que

∑_{v∈V (D)} δ_{D}^{−}(v) = q = |F (D)|.

2. Dada una digráfica D, si δ_{D}^{−}(z) ≥ 1 para todo vértice z en V (D) entonces D tiene un ciclo dirigido. Muestra que esta cota es la mejor posible.

3. Dada una digráfica D, si δ_{D}^{−}(z) ≥ k ≥ 221 para todo vértice z en V (D) entonces D tiene una trayectoria de longitud mayor o igual que k. Muestra que esta costa es la mejor posible.

4. Dada una digráfica D, si δ_{D}^{−}(z) ≥ k ≥ 1 para todo vértice z en V (D) entonces D tiene un ciclo dirigido de longitud al menos k + 1. Muestra que esta cota es la mejor posible.

5. Prueba que si una digráfica D posee un camino dirigido que pasa por todos los vértices entonces D es unilateralmente conexa.

6. Prueba que si D es una digráfica fuertemente conexa entonces existe un camino dirigido cerrado que pasa por todos sus vértices.

7. Considera una digráfica D y sea G_{D} la gráfica subyacente de D. Prueba que D es bipartita si y sólo si G_{D} lo es.