Si las gráficas son isomorfas, encuentre funciones f y g para la definición
8.6.1; de otra manera, dé una invariante que las gráficas no
compartan.
11. Demuestre que si M es una rejilla de p1
× p2
× · ·· × pk, donde
pi
≤ 2ti, para i = 1, . . . , k, entonces el cubo-(t1
+ t2
+ · ·· + tk)
contiene una subgráfica isomorfa a M.
En los ejercicios 12 al 16, muestre que la propiedad indicada es una invariante.
12. Tiene un ciclo simple de longitud k
13. Tiene n vértices de grado k
14. Es conexa
15. Tiene n ciclos simples de longitud k
16. Tiene una arista (v, w), donde δ(v) = i y δ(w) = j
17. Encuentre una invariante que no esté dada en esta sección o en los
ejercicios 12 al 16. Pruebe que su propiedad es invariante.
En los ejercicios 18 al 20, diga si cada propiedad es una invariante.
Si es una invariante, pruebe que lo es; de otra manera, dé un contraejemplo.
18. Tiene un ciclo de Euler
19. Tiene un vértice dentro de algún ciclo simple
20. Es bipartita
21. Dibuje todas las gráficas simples no isomorfas de tres vértices.
22. Dibuje todas las gráficas simples no isomorfas de cuatro vértices.
23. Dibuje todas las gráficas no isomorfas, sin ciclos y conexas que
tienen cinco vértices.
24. Dibuje todas las gráficas no isomorfas, sin ciclos y conexas que
tienen seis vértices.
25. Demuestre que las gráficas G1 y G2 son isomorfas si sus vértices
se puede ordenar de manera que sus matrices de adyacencia sean
iguales.
El complemento de una gráfica simple G es la gráfica simple G con
los mismos vértices que G. Una arista existe en G si y sólo si no existe
en G.
26. Dibuje el complemento de la gráfica G1 del ejercicio 1.
27. Dibuje el complemento de la gráfica G2 del ejercicio 1.
28. Demuestre que si G es una gráfica simple, G1 o bien G es conexa.
29. Una gráfica simple es autocomplementaria si G y G son isomorfas.
a) Encuentre una gráfica autocomplementaria que tenga cinco
vértices.
b) Encuentre otra gráfica autocomplementaria.
30. Sean G1 y G2 gráficas simples. Muestre que G1 y G2 son isomorfas
si y sólo si G 1 y G 2 son isomorfas.
31. Dadas dos gráficas G1 y G2, suponga que existe una función f uno
a uno y sobre de los vértices de G1 a los vértices de G2, y una función
g uno a uno y sobre de las aristas de G1 a las aristas de G2, de
manera que si una arista e incide en v y w en G1, la arista g(e) incide
en f (v) y f (w) en G2. ¿Son isomorfas G1 y G2?
Un homomorfismo de una gráfica G1 a una gráfica G2 es una función f
del conjunto de vértices de G1 al conjunto de vértices de G2 con la propiedad
de que si v y w son adyacentes en G1, entonces f (v) y f (w) son
adyacentes en G2.
32. Suponga que G1 y G2 son gráficas simples. Demuestre que si f es
un homomorfismo de G1 a G2 y f es uno a uno y sobre, G1 y G2
son isomorfas.
En los ejercicios 33 al 37, para cada par de gráficas, dé un ejemplo de
un homomorfismo de G1 a G2.
Get 8.6.33 exercise solution
36. G1= G1 del ejercicio 33
misma es la función identidad.
