Parcial de grafos matematicas discretas

SOLUCIÓN TERCER PARCIAL MATEMÁTICAS DISCRETAS

1) Determine, si existe, un circuito de Hamilton para los grafos

a. Para el grafo a si existe un circuito de Hamilton de los cuales unopodría ser:




a-b-c-g-h-j-f-e-i-d-a




b. Para el grafo b. Existe un camino de Hamilton pero no existe el circuito de Hamilton.




2) Determine si existe un circuito deEuler para los grafos

a. Para el grafo del circuito a como todos sus vértices son de grado par entonces por teorema de Euler, si existe un circuito que pasa por todos los nodos y recorretodos los caminos y este podría ser:




a-b-f-g-j-e-f-j-h-i-e-d-i-c-b-d-c-h-a

[pic]

b. Para este grafo también como todos sus vértices son de grado par entonces porteorema de Euler, existe un circuito que pasa por todos los nodos y recorre todos los caminos y este podría ser:




a-b-d-e-f-i-j-k-i-h-e-g-f-h-g-d-c-b-c-a

[pic]3) Esquematice el grafo representado por la matriz de adyacencia





















4) Suponga que un grafo tiene la forma A= x 00. x

¿Cómo debe ser el esquema del grafo??

Sea m el numero de vértices entonces el esquema tendríamos seria el de m vértices con bucles y que no se unen con ningún otrovértice sino consigo mismo.

5) ¿Son los grafos isomorfos?

En los dos primeros aunque tienen el mismo numero de vértices m=8, no son isomorfos por que no tienen el mismo número de segmentoso caminos, lo mismo sucede con los dos últimos grafos a pesar de que tienen el mismo numero de vértices no tienen el mismo numero de caminos lo que implica que los grafos dados no son isomorfos entreellos.













Es la propiedad tener un circuito de Euler un invariante

El tener un circuito de Euler no necesariamente implica que exista un isomorfismo y esto...