Taller digrafo

Punto 1. Dado el siguiente dígrafo

[pic 1]

Punto A. Defina la terna que le corresponde.
sea D=(V,A)= donde

         V(D) = {1,2,3,4,5}

         A(D) = {a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}

         F(D) = {a1(5,5), a2(5,5), a3(5,1), a4(2,1), a5(1,4), a6(4,3), a7(4,3), a8(4,3), a9(3,2), a10(2,3)}

Punto B. Determine los arcos paralelos y bucles.

Bucle: Se forma cuando el vértice inicial y final de una arista es el mismo vértice.
[pic 2]

Arcos paralelos: Si dos o más aristas poseen el mismo vértice inicial y el mismo vértice final.

[pic 3]

Punto C. Determine el grado positivo y negativo de cada vértice.

     g+ (1) = 1             g- (1) = 2             g (1) = 3

     g+ (2) = 2             g- (2) = 1             g (2) = 3

     g+ (3) = 1             g- (3) = 4             g (3) = 5

     g+ (4) = 3             g- (4) = 1             g (4) = 4

     g+ (5) = 3             g- (5) = 2             g (5) = 5

Punto 2. Dada la siguiente terna construya el siguiente dígrafo.

 V(D) = { v1, v2, v3, v4, v5 }

A(D) = {a, b, c, d, e, f }

F(D) = f(a) = (v1, v2), f(b) = (v3, v2), f(c) = (v1, v3)

            f(d) = (v4, v1), f(a) = (v3, v3), f(a) = (v4, v5)

[pic 4]

Punto 3.

        V(D) = {O, A, AB, B}

         A(D) = {a1, a2, a3, a4, a5, a6, a7, a8, a9}

         F(D) = {a1(0,0), a2(0,A), a3(0,AB), a4(0,B), a5(A,A), a6(AB,AB), a7(B,B), a8(A,AB), a9(B,BA)}

[pic 5]

Punto 4 .

4 punto A. Un digrafo simetrico de 5 vertices y 8 aros.

[pic 6]

4 punto B. Un digrafo simétrico con 5 vertices y 5 aros.

[pic 7]

4 Punto C. Un dígrafo con 4 vértices que no sea ni simétrico ni asimétrico

[pic 8]

Punto 5. Dado el siguiente dígrafo D y los dígrafos, Encuentre:

5 Punto A. los subdigrafos cobertores.

[pic 9]

5 Punto B. Las parejas de subdigrafos vértices-disjuntos.

[pic 10]

[pic 11]

5 Punto C. Las parejas de subdigrafos arcos-disjuntos.

[pic 12]

[pic 13]

5 Punto D. Los subdigrafos restantes al suprimir un conjunto de vértices.

[pic 14]

5 Punto E. Los subdigrafos restantes al suprimir un conjunto de arcos.

[pic 15]

Punto 6. Dado el siguiente dígrafo:

[pic 16]

Determine:

6 Punto A. Una ruta dirigida RD-(v1, v3) con l(RD) = 4

RD = V1 –a1 –V2 –a4 –V4 –a5-V2 –a2 – V3 l (RD) = 4

...