Soluciones Grafos

1.1.
| |B |NY |MM |MD | BC |
|B | |4 | | | |
|NY | | |2 || |
|MM | | | |1 | |
|MD | |1 | | |4 |
|BC |1 |1 || | |


[pic]
1.2.
[pic]

1.3.
[pic]

1.4.





1.5
. [pic]
COSTO MINIMO = 71

1.6
permutación:
5P5 = 120 DIFERENTES CAMINOS[pic]
1.7. SI, un ciclo es un camino cerrado en el que el vértice inicial y final coinciden, por lo tanto es necesario que el grado de los vértices sea 2.

1.8.
NO ES POSIBLELas personas invitadas serán los vértices. V = 20
Las aristas, personas que se conocen.
Como cada persona conoce a un número diferente de invitados no es aceptable que cadapersona se conozca a sí mismo, entonces hablamos de un grafo simple.
Los grados que pueden tomar el grado de un vértice son:
1, 2,3,K,n -1
por lo que no es posible quecada persona en la fiesta conozca a un número diferente de invitados.
Debido a que hablamos de grafo simple Los valores 0 y n-1 para los vértices no pueden presentarsesimultáneamente, pues 0 significa vértice aislado (sin adyacentes) y n-1 significa que un vértice es adyacente a todos los demás. En tal de los casos el vértice de grado n-1 seríaadyacente al vértice de grado 0, lo cual es totalmente incorrecto.

1.9.
Las poblaciones serán los vértices, y los tramos las aristas los caminos corresponderán al grado de losvértices, entonces;
Poblaciones = n = Vértices [v]
Tramos = 25 = aristas [E]
Caminos = 4 = grados de vértice g(v)
g(v)>= 4
∑g(v) >= ∑4
2[E]>=4n
2(25)>= 4n
50>=4n
n