EJERCICIOS CORRESPONDIENTES A LA UNIDAD IV

INSTITUTO TECNOLOGICO DE TEHUACAN

ING. EN SISTEMAS COMPUTACIONALES

MATEMATICAS DISCRETAS

EJERCICIOS CORRESPONDIENTES A LA UNIDAD IV

1. Determine | V | para los siguientes grafos o multigrafos G.

1. G tiene nueve aristas y todos los vértices tienen grado 3.
2. G tiene 10 aristas con dos vértices de grado 4 y los demás de grado 3.

1. Para el siguiente grafo indique cuántos caminos simples existen del vértice a al vértice h, ¿Cuántos caminos son de longitud 5?[pic 1]

1. De un ejemplo de un grafo conexo G tal que al eliminar cualquier arista de G se obtenga un grafo disconexo.
2. Escriba la matriz de adyacencia e incidencia para los siguientes grafos:

1. El grafo completo de cinco vértices K5.
2. El grafo bipartido completo K2,3.

1. Esquematice el grafo representado por cada una de las matrices de adyacencia dadas:

1.                                                                               b)[pic 2][pic 3][pic 4][pic 5]

1. Sea G el grafo no dirigido de la siguiente figura:

1. ¿Cuántos subgrafos conexos de G tiene cuatro vértices e incluyen un ciclo?

[pic 6]

[pic 7]

[pic 8][pic 9][pic 10]

[pic 11][pic 12]

[pic 13][pic 14][pic 15][pic 16][pic 17]

[pic 18]

[pic 19][pic 20]

[pic 21][pic 22][pic 23][pic 24][pic 25]

[pic 26][pic 27][pic 28]

1. Para los grafos de los ejercicios 1 y 2 determine si tienen circuitos o recorridos eulerianos y ciclos hamiltonianos o caminos hamiltonianiano, o ninguno de ellos.

1. Encuentre un cilco de Hamilton, camino de Hamilton, circuito euleriano y recorrido euleriano para el siguiente grafo:[pic 29]

LSTA II

1. Esquematice el grafo representado por cada una de las matrices de incidencia dadas, e indique si son multigrafos

[pic 30]

a        1        0        0         0        0        1

                          b      0          1       1       0      1      0        

c     1      0        0      1       0      0

d     0      1        0      1       0      0

e     0      0         1      0      1       1

        [pic 31]

a        0        1        0        0        1        1

                          b      0          1       1      0       1      0        

c    0        0       0      0       0      1 

d    1        0       0     1       0       0

e    1        0       0      1       0       0

1. Demuéstrese que cada uno de los grafos dados enseguida, son planos rehaciendo el dibujo de modo que los lados no se crucen:[pic 32]

[pic 33]

[pic 34]

3.- Para el grafo ponderado de las notas, hallar un camino para ir de un vértice elegido por ustedes a otro y muestre los resultados del algoritmo paso a paso como en el ejercicio resuelto en clase.

...