20/12/06

MATEMÁTICA DISCRETA
Coloquio

1. Dada la proposición
   1. Analizar el valor de verdad de la misma.
   2. Negar la proposición.
   3. Escribir las expresiones contraria, recíproca y contra-recíproca analizando en cada caso su valor de verdad.
      
      
2. 1. Definir ecuación de recurrencia lineal de orden n, ecuación caracteríastica o indicial y probar que: si es solución de la ecuación indicial → es solución de la ecuación de recurrencia.
   2. Resolver: .
      
      
3. Sea un grafo. Se dice que є V es un punto de articulación del grafo sii G' (el grafo que resulta de sacarle a G el vértice y todas las aristas incidentes en él) tiene más componentes conexas que G.
   1. Proporcione dos ejemplos de grafos con 6 vértices tal que uno tenga exactamente dos puntos de articulación y el otro ninguno.
   2. Probar que si G es un árbol es un punto de articulación sii grado () > 1.
      
      
4. Analizar el valor de verdad de las siguientes proposiciones justificando su respuesta
   1. Algunos grafos con no son árboles.
   2. Si G es un grafo conexo con por lo menos 2 vértices, uno de grado 1 y los demás de grado ≥ 2 entonces G es no acíclico.
      
      
5. 1. Definir red de transporte y flujo de una red.
   2. Probar que el valor del flujo saliente en el vértice fuente es igual al entrante en el sumidero.
   3. Hallar los valores de є para que constituyan un flujo compatible con la red dibujada.
   4. A partir del flujo de III que tenga el menor valor de x hallar el flujo máximo y corte minimal.