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

[pic 17]

R=/

Si hay un camino de Euler, entonces a medida que lo seguimos a través del grafo, cada vértice excepto el vértice inicial y final debe tener igual grado de entrada y salida, El vértice inicial debe tener un grado de salida 1 mayor que su grado de entrada, ya que después de que hayamos comenzado, usando una arista que sale de este vértice, se aplica el mismo argumento. Del mismo modo, el vértice final debe tener un grado 1 mayor que su grado de salida, ya que se debe usando la arista que conduce a este vértice, se aplica el mismo argumento. Tenga en cuenta que la propia ruta de Euler garantiza una conectividad débil; dados dos vértices, es un camino desde el que ocurre primero a lo largo del camino de Euler hasta el otro, a través del camino de Euler.

...