grafos _isomorfismo

Vista previa del material en texto

UNSL MATEMATICA DISCRETA 2018
TRABAJO PRACTICO
Grafos
Isomorfismo
1. Determinar si los grafos de cada pareja de la figura 1 son isomorfos. En caso de serlo, explicitar un
isomorfismo, de lo contrario, dar un argumento que muestre la imposibilidad de conseguirlo.
a b
c d
e f
1 2
3
4
5 6
a b c
d
e
f
g h i
1 2 3
4
5
6
7 8 9
a b
c d
e f
g h
1 2
3 4
5 6
7 8
a b
c
d
e f
1 2
3
4
5 6
a
b
c
d e
f
g
h
i j
1
23
4
5 6
7
8
9
10
a
b
c
d
e
f
g
1
2
3
4
5
6
7
Figura 1
2. En cada ı́tem, determine si la propiedad dada es una invariante para grafos simples. En caso
afirmativo, dé un argumento que lo pruebe; en caso contrario, exhiba un contraejemplo.
(a) Tiene v vértices.
(b) Tiene e aristas.
(c) Tiene un ciclo simple de longitud k.
(d) Tiene n vértices de grado k.
(e) Tiene un ciclo de Euler.
(f) Tiene un vértice dentro de algún ciclo simple.
(g) Es conexo.
(h) Es bipartito.
(i) Tiene una arista tv, wu tal que degpvq � j y degpwq � k.
1
UNSL MATEMATICA DISCRETA 2018
3. Demostrar que la relación “es isomorfo a”, entre grafos simples, es una relación de equivalencia.
4. Representar gráficamente todos los grafos simples de 2, 3 y 4 vértices. Agruparlos de acuerdo a la
clase de equivalencia a la que pertenezcan según la relación de isomorfismo.
Definición: Dado un grafo simple G con conjunto de vértices V(G) y conjunto de aristas E(G), el
grafo complementario a G, denotado G, es aquel que tiene V pGq � V pGq y EpGq � ttv, wu | v, w P
V pGq y v � w y tv, wu R EpGqu.
5. Calcular el complemento de los grafos P5, C5, K5, K5,2.
6. Demostrar que el grafo P4 es autocomplementario, i.e., P4 es isomorfo a P4.
7. ¿Para qué valores de n es autocomplementario Cn?
8. Sean G y H grafos. Demostrar que si G es isomorfo a H entonces G es isomorfo a H.
9. Dar un ejemplo de 2 grafos no isomorfos de orden 6 y tamaño 6, 2-regulares.
10. Determinar todos los grafos autocomplementarios de orden menor o igual a 5.
11. Para cada entero k ¥ 2, dar un ejemplo de 2 grafos no isomorfos k-regulares que tengan el mismo
orden y tamaño.
12. Sea G un grafo simple autocomplementario de orden n, con n ¡ 1.
(a) ¿Cuántas aristas tiene G?
(b) Probar que n �4 0 o n �4 1.
13. (a) Hallar un grafo G, tal que tanto G como G sean conectados.
(b) Sea G un grafo simple de orden n, con n ¥ 2. Si G no es conectado, entonces G es conectado.
14. ¿Cuáles de los siguientes enunciados sobre grafos G y H son verdaderos? Justificar las respuestas.
(a) G y H son isomorfos si y sólo si para cada aplicación f : V pGq Ñ V pHq y para cada par de
vértices u, v P V pGq se tiene tu, vu P EpGq ô tfpuq, fpvqu P EpHq.
(b) Si existe una biyección h : EpGq Ñ EpHq entonces G y H son isomorfos.
(c) Si existe una biyección f : V pGq Ñ V pHq tal que para cada vértice u P V pGq : degGpuq �
degHpfpuqq, entonces G y H son isomorfos.
(d) Si G y H son isomorfos entonces existe una biyección h : EpGq Ñ EpHq.
15. Sea G un grafo autocomplementario de orden n con n �4 1. Probar que G contiene al menos un
v P V pGq tal que degGpvq � pn� 1q{2.
Definición: Un homomorfismo de un grafo G1 a un grafo G2 es una función f : V pG1q Ñ V pG2q con
la propiedad de que si v y w son adyacentes en G1 entonces fpvq y fpwq son adyacentes en G2. Se dice
que los grafos G1 y G2 son homomorfos.
16. Para cada pareja de grafos de la figura 2, dé un ejemplo de un homomorfismo de G1 a G2.
2
UNSL MATEMATICA DISCRETA 2018
a
bc
d
e f
1 2
34
a b c d
1
2
3
a
b
c
d
e
f
g
1 2 3
4
5
a
bc
d
e f
1 2 3 4
Figura 2
3