UNIDAD III: RELACIONES Y GRAFOS.

TAREA 2: RESUELVA EL PROBLEMA 5 (PAG 76) DE LA APLICACION EN LOS SISTEMAS DE BASE DE DATOS.

Puesto que G es simple el grado maximo de cualquier vertice en n-1. hance. S es un subconjunto del conjunto de enteros {0,1,2.....,n-1} sin embargo S no puede contener 0 y n-1 de lo contrario un vertic de grado n-1 seria adyacente a todos los otros vertics i8ncluyendo el de grado 0, lo que es un contradiccion.

Por lo tanto S=<n-1, considera la posibilidad de la funcion f:V-S asigna que cada vertice a su grado. dado que V>S y por eso, por principio del palomar, almenos dos vertics tienen el mismo grad.

La grafica G muestra la matriz en orden de 1,2,3,4,5 y 6 describir la matriz de adyecencia del grafo completo Kn

El algoritmo del vecino mas cercano para encontrar ciclos hamiltonianos en la grafica ponderada en la figura 7.24 a partir del (a) el vertice A, y (b) el vertice D.

R= (a) el algoritmo general la ACBDEA camino de la longitud total 4+2+3+2+8=19

(b) El algoritmo genera DEBCAD camino de longitud total 2+4+2+4+5=17