Taller 2 grafo

[pic 1]

1.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:

[pic 2]

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 (aristas) de la autopista una única vez.  ¿Cuál es ese recorrido?  ¿Es la única solución?

(f-c), (c-d), (d-e), (e-f), (f-a), (a-b), (d-f), (f-d) (d-b)

No es la única solución, existen otras

2.Un grafo conexo con 21 aristas, tiene 7 vértices de grado 1, 3 de grado 2, 7 de grado 3, y el resto de grado 4.  ¿Cuántos vértices debe tener? Utilice el teorema de la suma de los grados.  Adicionalmente, dibujar el grafo.

Este grafo no puede ser dibujado o graficadle debido a que la primera limitación el numero de aristas que pide el ejercicio, siendo 21 aristas como máximo y la suma de los vértices es mayor al numero de aristas que son 25 quedando vértices aislados. Haciendo cada grafo por separado me dio un total de 22 vértices.

3.Un departamento de una empresa tiene establecidas dos redes locales de comunicación distintas entre sus ocho terminales.  Las líneas de conexión de cada red están esquematizadas en los siguientes grafos:

                             [pic 3]

1. Comprobar si los grafos de las redes son bipartitos y encontrar un emparejamiento de los conjuntos disjuntos para el mismo.

 Los vértices de ambas redes están divididos en pares e impares

4. Dibujar el dígrafo a partir de la siguiente información.

A = {ai, i ∈N, 1 ≤i ≤10}.  

V = {V1, V2, V3, V4, V5, V6}

La función de incidencia 𝜑(ai)= (Vi, Vj) está definida por:

𝜑(a5) = (V2, V3);

𝜑(a6) = (V3, V5);

𝜑(a8) = (V3, V5);

𝜑(a9) = (V2, V2);

𝜑(a10) = (V6, V6);  

𝜑(a7) = (V3, V5);

𝜑(a1) = (V1, V2);

𝜑(a2) = (V2, V1);

𝜑(a3) = (V2, V6);

𝜑(a4) = (V2, V5);

 [pic 4]

5. Calcule los grados del digrafo anterior y aplique el teorema de la suma de grados.

G(V1)= 2, G(V2)=7, G(V3)=4, G(V4)=0, G(V5)=4, G(V6)=3

Grado de un grafo: suma de los grados del vértice, por tanto:

G= 0+2+7+2+4+4= 20

Teorema de suma de grados: Equivale al doble de numero de arcos, por tanto:

Grado del grafo: 2*10 = 20

6. Encuentre las adyacencias para cada uno de los (Vi) del dígrafo.

...