TALLER N.º 1 2do CORTE MATEMATICAS DISCRETAS

TALLER N.º 1     2do CORTE

MATEMATICAS DISCRETAS

Integrantes:

Edilberto Celorio Benítez

Jesús Darío Panameño

Estefano Müller Estupiñán

Anderson Jair Velazco Contreras

[pic 1]

R=/ El grafo no tiene ni circuito ni camino de Euler como se aprecia en la imagen, donde se observa que existen cuatro vértices de grado impar (a, b, c y e).

[pic 2]

R=/ En este grafo podemos encontrar un circuito y la vez un camino euleriano conectando los siguientes vértices: d, a, d, c, f, i, h, f, e, d, b, e, h, g, d

[pic 3]

R=/ Todos los grados de vértice son par. Hay un circuito de Euler porque cada vértice tiene un grado par. El circuito es como

sigue: a, b, c, d, e, f, g, h, i, a, h, b, i, c, e, h, d, g, c, a

[pic 4]

R=/ Todos los grados de vértice son par y existe un camino y circuito euleriano con los siguientes vértices: f, a, b, c, d, e, j, o, n, m, l, k, f, m, h, i, n, l, g, b, d, i, j, c, h, g, f

[pic 5]

(a) Cada vértice en Kn tiene grado n-1. Kn tiene un circuito de Euler si n es impar.

(b) Cada vértice en Cn tiene grado 2. Cn tiene un circuito de Euler para cada n.

(c) Todos los vértices excepto el centro de Wn tienen grado tres. Wn tiene un Euler

circuito para cada n.

[pic 6]

R=/

A) Para ningún n que no sea 2 hay un camino de Euler, pero no un circuito de Euler.

B) No hay valores de n que cumplan estas condiciones.

C) Ninguno

[pic 7]

a).

[pic 8]

para los valores de m = 4 y n =4 el grafo bipartito contiendo un circuito euleriano ya que todos sus vértices son de grado par.

b).

[pic 9]

Para valores de m = 2 y n=3 el grado bipartido completo contiene un camino euleriano ya que tiene exactamente 2 vértices de grado impar.

Sección 8.6

2.)[pic 10]

La longitud del camino más corto es de 6.

3.)

[pic 11]

La longitud del camino más corto es de 16.

5.)

       El camino de longitud mínima es {a, b, e, d, z}.

      [pic 12]

6.)

a.) la longitud del camino de longitud mínima entre los vértices a y b es de 6.

[pic 13]        

b.) la longitud del camino de longitud mínima entre los vértices a y f es de 11.

[pic 14]

c.) la longitud del camino de longitud mínima entre los vértices c y f es de 8.

[pic 15]

d.) la longitud del camino de longitud mínima entre los vértices b y z es de 13[pic 16]

Sección 8.8

...