• Author / Uploaded
• Julian Pareja

Citation preview

TALLER DE GRAFOS 1. Dibujar el grafo g no orientado y su matriz de adyacencia según lo que expresan los siguientes conjuntos: -

v(g) = {a, b, c, d, e}

-

a(g) = {ab, bc, be, ed, de, ad} a

Vértices del gafo g

b

a b c d e

0 1 0 1 0

Aristas del gafo g

c 1 0 1 0 1

d 0 1 0 1 0

e 1 0 1 0 1

grado 0 1 0 1 0

2 3 2 3 2

a

e

d

b

c 2. Construir un grafo no orientado de 5 vértices en los que cada uno tenga los siguientes grados: 1,2,2,1,4. a

b

a b c d e

0 0 0 0 1

c 0 1 0 0 1

d 0 0 1 0 1

e 0 0 0 0 1

grado 1 1 1 1 0

1 2 2 1 4

d e

b c a

3. ¿Cuántas aristas tiene un grafo si sus vértices tienen los siguientes grados: 4,3,3,2,2? Dibujarlo. V (g)= {a, b, c, d, e} a (g)= {ab, ac, ad, ae, bc, be, cd}

vertice grado

a

b

c

4

d

3

e

3

2

2

e POSEE 7 ARISTAS

a b d c

4. Decir cuál de los siguientes grafos corresponde a un multígrafo, y cual a un árbol,

Arbol

Diagrafo

Completo

5. Dado el siguiente grafo g: a) Definir el grado de cada uno de los vértices. b) Definir tres caminos y tres circuitos. c) Dibujar tres subgrafos a partir del mismo.

a) v grado

1 1

2 2

3 5

4 6

5 3

6 4

7 7

b) Camino 1: 1, 3, 7,10 Circuito 1: 3, 4, 7, 3 Camino 2: 1, 3, 6, 7, 10 Circuito 2: 6, 7, 9, 6 Camino 3: 1, 3, 9, 7, 10 Circuito 3: 7, 5, 8, 7 No se repiten ni vértices ni aristas El vértice inicial es el mismo del final

8 3

9 4

10 1

2

3

4

c) 6

4

4

5 7

9

7

8

9

6. Dado el siguiente grafo g, encontrar en él: a) Un camino que conecta a v1 y v4. V1 Y V4: (V1, V2), (V2, V3), (V3, V4) b) Un camino simple de longitud 5 entre v1 y v4. V1 Y V4: (V1, V2), (V2, V7), (V7, V6), (V6, V5), (V5, V4) c) Un camino de longitud 6 entre v1 y v4. V1, V4: (V1, V6), (V6, V7), (V7, V2), (V2, V3), (V3, V5), (V5, V4) d) Un ciclo de longitud 3, otro de longitud 4 y otro de longitud 6. LONG 3: (V3, V4), (V4, V5), (V5, V3) LONG 4: (V2, V1), (V1, V6), (V6, V7), (V7, V2) LONG 6: (V1, V2), (V2, V3), (V3. V4), (V4, V5), (V5, V6), (V6, V1) e) Un circuito de longitud 9. LONG 9: (V3, V4), (V4, V5), (V5, V6), (V6, V7), (V7, V2), (V2, V1), (V1, V6), (V6, V2), (V2, V3) 7. Dado el siguiente grafo, escribir el grado de entrada y de salida para cada vértice:

Grado de entrada Grado de salida v1: 0 v1: 2 v2: 2 v2: 2 v3: 1 v3: 1 v4: 1 v4: 1 v5: 3 v5: 1

8. ¿Cuándo un grafo es euleriano? Decir si los siguientes grafos son eulerianos:

Un grafo conexo y no dirigido es eulariano si cada vértice tiene un grado par. Por otro lado un grafo no dirigido es eulariano si es conexo y se puede descomponer en uno con los vértices disjuntos. Eulariano

No Eulariano

Eulariano

Semi-Eulariano

No Eulariano

9. ¿Cuándo un grafo es Hamiltoniano? Decir si los siguientes grafos son Hamiltonianos: Un grafo es Hamiltoniano cuando es posible hacer un recorrido en un grafo que pase por cada vértice una vez y termine en el vértice original. También Cuando un grafo tiene un ciclo cerrado que contenga a todos sus vértices. Hamiltoniano Hamiltoniano

10. Determinar cuáles de los siguientes grafos se pueden dibujar en papel sin levantar el lápiz, y sin dibujar dos veces la misma arista. ¿Qué tipo de grafos son? Todos se pueden dibujar sin levantar el lápiz.

Hamiltoniano

Eulariano

Eulariano

11. Una compañía de autopistas ha contratado a una empresa de seguridad para que patrulle la red de autopistas cuyo mapa está esquematizado en el siguiente grafo:

La empresa de seguridad quiere realizar el servicio con un solo vehículo y quiere determinar la existencia de un recorrido de manera que se vigilen los tramos de la autopista una única vez. ¿Cuál es ese recorrido? ¿Es la única solución? El recorrido seria: { (b, a), (a, d), (d, b), (b, e), (e, d), (d, c), (c, f) } Cabe resaltar que existen otros posibles caminos. 12. Para armar una red, tenemos 6 computadoras y 9 cables de conexión. Queremos que cada computadora se conecte con otras 3. ¿Existe alguna forma de conectarlos? ¿Es única? Vértices = # de computadores = 6 Aristas= # cables de conexión = 9 V= 6 Card A= 9 Si cada computadora se conecta con otras 3, entonces el grado de cada vértice es 3 y se verifica la expresión: