Compuertas

Ejercicios

a. {{1,2},{1,3},{2,3},{4,5},{5,1},{4,6}}
Es una gráfica simple, conexa





b. {{1,1},{1,2},{2,3},{3,4},{3,4},{4,5},{4,5},{5,6},{6,6}}
Es una multigráfica, conexac. {{1,1},{2,3},{3,4},{4,5},{6,6}}
Es una gráfica, inconexa














a. {(1,2),(2,1),(1,3),(3,4),(4,3),(4,5),(5,5)}










MULTIDIGRAFICA

1 (1,2) 2(2,1) 1 (1,3) 3 (3,4) 4 (4,5) 5 (5,5) 5


LISTA DE ADYACENCIA: 1: 2,3; 2: 1; 3: 4; 4: 3, 5; 5: 5;

b. {(1,2),(1,2),(2,2),(2,1),(3,4),(4,5),(5,3),(3,5)}MULTIDIGRAFICA INCONEXA.

1 (1,2) 2 (2,1) 1 (1,3) 3 (3,4) 4 (4,5) 5 (5,5) 5

5 (5,3) 3 (3,4) 4 (4,5)5
LISTA DE ADYACENCIA: 1: 2; 2: 1,2; 3: 5,4; 4: 5; 5: 3;c. {(1,2),(2,3),(2,3),(3,4),(3,4),(4,5)}

DIGRAFICA CONEXA.

1 (1,2) 2 (2,3) 3 (3,4) 4 (4,5) 5









3. NO hay ISOMORFISMO

(1,3) (e,a)
(3,4) (a,d)
(4,5) (d,b)
(5,6)(b,f)
(6,2) (f,c)
(2,1) (c,e)
(2,3) (c,a)
(6,4) (f,d)
(b,d)



















4.












a. Analizar la gráfica resultante y escribirun recorrido euleriano y un circuito euleriano de ella.


RECORRIDO EULERIANO

d{d,c} c {c,a} a {a,d} d{d,a} a {a,b} b {b,d} d{d,e} e {e,b} b {b,e}e.


CIRCUITO EULERIANO

d{d,c} c {c,a} a{a,d} d{d,a} a {a,b} b {b,d} d{d,e} e {e,b} b {b,e}e {e,d}d.

5.

a. 1-8-6-5-2-3-4-7-1 ninguna
b. 1-7-3-2-4-1-8-6-5 CIRCUITO HAMILTONIANO
c. 4-2-3-7-1-8-6-5 TRAYECTORIA HAMILTONIANA
d.1-8-6-2-4-3-7-1 circuito hamiltoniano












6.


7.



PESO= 7 PESO=7

8.#BORDES=(#VERTICES(#VERTICES-1))/2+#V




9.



#BORDES=(#VERTICES(#VERTICES-1))/2







10.


a b c d e a b c d e
a - 2 ∞ 3 5 a - b c d e
b 2 - 4 2 ∞ b a - c d e
c ∞ 4 - 1 ∞ c a b - d e
d...