Teoría de grafos

MATEMÁTICA DISCRETA
ISOMORFISMOS

10

1
 PROPÓSITO
• Resuelve ejercicios relacionados con
ISOMORFISMO de grafos
 isomorfismo de grafos
FUNCIÓN BIYECTIVA

FUNCIÓN INYECTIVA Conocida también como función

univalente o uno a uno, se caracteriza porque cada elemento del rango
es imagen de un único elemento1 del dominio
A B A B
1 3
1 1

4 12 2 7
2
3
3 9 4 9
 isomorfismo de grafos C C C
FUNCIÓN BIYECTIVA

FUNCIÓN SURYECTIVA Conocida también como función

sobreyectiva o epiyectiva, se caracteriza porque el conjunto de llegada
coincide con el rango.
A B A B
1
3 6 1
2
8 2
4 4
5 10 3 3
 isomorfismo de grafos C C C
FUNCIÓN BIYECTIVA
FUNCIÓN BIYECTIVA
La función f: A B es biyectiva si es al vez inyectiva y suryectiva

A B A B
3 6 1
2
8 2
4 4 1
5 10 3 6
 isomorfismo de grafos
• https://www.youtube.com/watch?v=58a6KqEOcoQ
• https://www.youtube.com/watch?v=fvH4JnH1Q6M
• FUNCIÓN BIYECTIVA
FUNCIÓN INYECTIVA Conocida también como función
univalente o uno a uno, se caracteriza porque cada elemento del rango
es imagen de un único elemento del ominio
 ISOMORFISMO DE GRAFOS

• Dos grafos simples son isomorfos, si existe una función entre los
conjuntos de vértices que cumpla:
1. Sea biyectiva.
2. Las imágenes de dos vértices adyacentes son adyacentes.
COROLARIO: En un isomorfismo de grafos, el grado de ambos grafos
son los mismos
ISOMORFISMO DE GRAFOS
 ISOMORFISMO DE GRAFOS

/ ↔
• https://www.youtube.com/watch?v=U0Wt6hNM9oE
 

ES UNA FUNCIÓN BIYECTIVA QUE CONSERVA LA ESTRUCTURA DEL GRAFO

 E
F 1
4

2 3
C

A B
6 5

G H
 G

E
E E

D
D D

C F
C F C F

G
 AUTOMORFISMOS Y NÚMERO DE ISOMORFISMOS

B D 2

A 1

C 3 4
 ISOMORFISMO DE GRAFOS
En teoría de grafos, un isomorfismo entre dos grafos G y H es una biyección
 f entre los conjuntos de sus vértices   que preserva la relación de adyacencia.
Es decir, cualquier par de vértices u y v de G son adyacentes si y solo si lo son
sus imágenes, f(u) y f(v), en H.
A pesar de su diferente aspecto, los dos grafos que se muestran a continuación
son isomorfos:
 EJERCICIOS

Dados los grafos determina si son isomorfos

Grafo F

Grafo G

G
 DEFINICIÓN

Una propiedad P es un invariante siempre que, dados dos grafos G1 y G2

tales que G1 = G2, si G1 cumple P entonces G2 también la cumple
Son propiedades invariantes:
(i) “Tener la misma cantidad de vértices”.
(ii) “Tener la misma cantidad de aristas”.
(iii)“Tener un ciclo simple de longitud k”
¿Como demostrar que dos grafos no son isomorfos? Comprobando que
son distintos respecto a una propiedad invariante.
 PERMUTACIÓN DE FILAS Y COLUMNAS

SI SE HACEN INTERCAMBIOS ENTRE FILAS Y COLUMNAS EN UNA

MATRIZ DE ADYACENCIA SON IGUALES
 Los grafos G1= ( V1, E1) Y G2=( V 2,E2) son isomorfos?

1 2 A B
f (1)=A (1,A)
f (3)=C (3,C)
f (2)=D (2,D)
f (4)=B (4,B)
3 C D
4

G1 G2
MATRICES DE ADYACENCIA
PERMUTACIÓN ENTRE FILAS Y COLUMNAS
 PROBLEMAS
G1= ( V1, E1) G 2=( V2, E2)
e1 D
2 3

e8 e5
e2 e3
e4
B

e6
A
1 4
e7

C
 PROBLEMAS
e1 D
2 3
f(3)=A (3,A)
f(4)=C (4,C) e5
e8
e2 e3 f(2)=B (2,B)
e4
f(1)=D (1,D)
B

e6
A
1 4
e7

G1 G2 C
MATRICES DE ADYACENCIA

G1= G2=
 Los grafos G Y H son isomorfos
U1 V1 V3
U2
f(U1)=V6

f(U2)=V3

U5 f(U3)=V4 V2 V6

U6 f(U4)=V5

f(U5)=V1

f(U6)=V2
U4 V5 V4
U3
H
G
f(U3)=V4
 Los grafos G y H son isomorfos?
t
s
a b

w
x
f
e

h z y
g

d c v U
 ISOMORFISMOS DE GRAFOS DIRIGIDOS

1 f(2)=B A

f(4)=A
B
2
f(3)=C
3 4
f(1)=D C D

G H
 V1 V2
U1 U2

V3
U3 U4 V4
 Los grafos G y H son isomorfos?
V3
U1

V4
U4

V5
U3 V2 H
U2
G
GRAFO BIPARTIDO
 En teoría de grafos, un grafo bipartito es un grafo cuyos
vértices se pueden separar en dos conjuntos disjuntos, de
GRAFO BIPARTIDO
manera que las aristas no pueden relacionar vértices de
un mismo conjunto.
GRAFO BIPARTIDO. Un vértice de un subconjunto solo
se conecta con subconjuntos de otro.
PROPIEDADES

2E
2m
EJEMPLO
 EJEMPLO

V={A,B,C,D,E,F}
E={(A,F),(A,D),(A,C),(F,B),(B,E),(F,E)}

G tiene un ciclo de longitud impar, por lo tanto no es bipartito

 CAMINOS
o
RUTAS

Los grafos son usados con frecuencia para representar redes de comunicación o transporte. En un grafo que representa una de estas redes es importante conocer la existencia de caminos que recorren
todas las aristas o todos los vértices y que en cierto modo séan los más “económicos”. Para ello comenzaremos dando una serie de definiciones básicas
 CAMINO O RUTA

Un camino o ruta de un grafo G es un secuencia (finita )en las que aparecen en forma alternadamente de
vértices y lados de G.

Forma simplificada:

EXTREMOS

:
CAMINO .Es una ruta que se debe seguir para llegar de un punto a otro.
Lo representaremos por :

Entre un punto y otro puede haber más de un camino

 La longitud de un camino es el número de aristas o arcos que contiene.

Entre un punto y otro puede haber más de un camino

 TIPOS DE CAMINOS

CAMINO ELEMENTAL.
Es aquel camino que nunca pasa más de una vez por un mismo punto.

Por lo tanto es un CAMINO COMPUESTO

 TIPOS DE CAMINOS

Un camino se dice que cerrado si sus extremos coinciden, es decir si empieza o termina en el mismo vértice. Es
aquel camino que vuelve a su punto de origen.

En caso contrario se dice que es un camino abierto.

 CIRCUITO Y CICLO

Un circuito es un camino cerrado en el cual todos los lados (aunque no necesariamente los vértices ) son
distintos).

Un ciclo es un camino cerrado en el cual todos los vértices (excepto el inicial y el final) son distintos y, como
consecuencia ,todos los lados también son distintos.
CAMINO ELEMENTAL O SIMPLE Es aquel camino que nunca pasa más de una vez por un mismo punto.

CAMINO COMPUESTO: Es aquel camino que utiliza más de una vez un mismo punto. En la figura anterior:
 CIRCUITO
Es aquel camino que vuelve a su punto de origen.
 CIRCUITO ELEMENTAL

Es un camino elemental que vuelve a su punto de partida.

 CIRCUITO COMPUESTO

Es aquel camino compuesto que vuelve a su punto de partida. .

 CAMINO HAMILTONIANO

Es el camino elemental que pasa por todos los vértices del grafo.
 CIRCUITO HAMILTONIANO

Es un camino que vuelve a su punto de partida pasando por todos los vértices del grafo.
 EN RESUMEN

Bucle
Es la conexión de un vértice consigo mismo por medio de un Lazo
arco Es la conexión de un vértice consigo mismo por
medio de un arista

H
 GRAFO CONEXO

• Un grafo G=(V,E) se denomina conexo si existe un camino simple entre cualquier par de vértices. Se dice que
un grafo G es conexo, si existe un camino simple entre cualesquiera dos vértices diferentes de G. En caso contrario el grafo
es disconexo
b e c f

g
a b d e
d

c a h

GRAFO CONEXO GRAFO DISCONEXO

CAMINOS Y CICLOS
CAMINOS Y CICLOS
CAMINOS Y CICLOS
 CAMINOS DE EULER Y DE HAMILTON
CAMINO DE EULER. Camino que recorre todas las aristas exactamente una vez

CAMINO DE HAMILTON .Camino que recorre todos vértices exactamente una vez
CAMINOS DE EULER Y DE HAMILTON
CAMINO DE EULER. Camino que recorre todas las aristas
exactamente una vez

CAMINO DE HAMILTON .Camino que recorre todos vértices

exactamente una vez
 CICLOS DE EULER Y HAMILTON
CICLO DE EULER. Ciclo que recorre todas las aristas exactamente una vez.
CICLO DE HAMILTON. Ciclo que recorre todos los vértices exactamente una vez.

CICLO DE EULER CICLO DE HAMILTON

Determine que tipo de ciclo es:
Dado un grafo conexo hallar un ciclo euleriano, esto es encontrar si es posible encontrar un
camino que permita partir de un vértice del grafo y regresar a él recorriendo todas las
aristas del grafo una sola vez.
Demostrar que el siguiente grafo es euleriano
 Eulerización
En los grafos donde existan vértices con grado impar no es posible un circuito euleriano, pero se puede
introducir una nueva arista para transformarlo en un circuito euleriano. Este método sirve para resolver uno de
los problemas que se presentará a continuación, lo cual se denomina “eulerizar un grafo”.
En las figuras se muestra una Eulerización posible y la trayectoria final.
 EL PROBLEMA DEL CARTERO CHINO

• La ruta ideal de un cartero inteligente que desea hacer bien su trabajo será aquella calle sólo debe recorrer
una vez. Si al recorrido de calles se asocia el grafo correspondiente entonces lo ideal es buscar el circuito
Euleriano. Pero si no existe, deberán repetirse algunas calles procurando hacer las mínimas repeticiones.
Esto fue estudiado por el matemático Chino Meigu Guan en 1962, se ha popularizado con el nombre de “El
problema del cartero chino”.
 En la segunda figura puede notar que con el truco de introducir tan sólo una nueva arista
ya tiene un circuito Euleriano con la trayectoria indicada, en la que únicamente una calle
se recorre dos veces (5 y 6).

Este método se puede utilizar en otros contextos como en las empresas que deben distribuir sus
productos y quieren minimizar los recorridos y los tiempos empleados en estas labores, entre otros.
• ¿Se puede hallar un recorrido, partiendo de un vértice, en que a través de algunas aristas permita pasar por
todos los vértices una sola vez y regresar al vértice de partida?
Si este recorrido es posible se le denomina circuito Hamiltoniano.

En la figura anterior el trayecto DABCED sería Hamiltoniano, los circuitos Hamiltonianos lo que no
puede repetirse son los vértices, cosa que el circuito Euleriano si se puede.
A pesar de la dificultad que presentan los grafos grandes para determinar circuitos Hamiltonianos, el
problema es de gran interés para la organización de viajes, para las recogidas de todo tipo, para la
distribución de mercaderías en los supermercados, etc.
 TEORÍA DE GRAFOS

DEFINICIONES BÁSICAS
Definición 1. Un grafo no dirigido G, consiste en un conjunto de vértices y
un conjunto E de aristas, tal que cada arista e que pertenece a E está
asociado a un par no ordenado de vértices. Si una arista e está asociada a un
único par no ordenado de vértices v y w,  e = (v, w) o bien e = (w, v).
Definición 2. Un grafo dirigido G, consiste en un conjunto de vértices y un
conjunto E de aristas, tal que cada arista e que pertenece a E está asociado a
un par ordenado de vértices. Si una arista e está asociada a un único par
ordenado de vértices v y w,  e = (v, w)
• https://www.youtube.com/watch?v=tIeGC2Fa5P4
• Definición 3. Sean x e y vértices no necesariamente diferentes de un grafo no dirigido.
Un camino de x hacia y en G es una sucesión alternada finita y sin bucles de V y E de G,
que empiezan en x y terminan en y.
• La longitud de un camino es n (# de aristas), donde n  1.
• Cualquier camino de x – y es un camino abierto.
• Cualquier camino de x – x es un camino cerrado.
• Si en el camino de x – y no se repiten aristas, el camino se llama RECORRIDO.
• Si en el camino de x – x no se repiten aristas, el camino se llama CIRCUITO.
• Si en el camino de x – y no se repiten vértices, el camino se llama CAMINO SIMPLE.
• Si en el camino de x – X no se repiten vértices, el camino se llama CICLO (Nº de
vértices  3).
• Definición 4. Se dice que un grafo G es conexo, si existe un camino simple
entre cualesquiera dos vértices diferentes de G. En caso contrario el grafo es
disconexo.b e c f

g
a b d e
d

c a h

GRAFO CONEXO GRAFO DISCONEXO

Definición 5. Si G = (V, E) es un grafo, entonces:
G1 = (V1, E1) es un subgrafo de G; si V1  V y E1  E, donde cada arista de E1 es incidente con los
vértices de V1.

Definición 6. Dado un grafo G = (V, E), sea G1 = (V1, E1) un subgrafo de G.

Si V1 = V, entonces G1 es un subgrafo recubridor de G.

Definición 7. Sea V un conjunto de n vértices. Un grafo simple que tiene n vértices y cada vértice
es adyacente a todos los demás se denomina GRAFO COMPLETO y se denota por Kn.

Definición 8. Sea G un grafo no dirigido sin bucles con n vértices. El complemento de G denotado
como G’ es el subgrafo de Kn formado por todos los vértices de G y todas las aristas que no estén
en G.
• 
Definición 9. Un grafo G = (V, E) es un multígrafo, si existe a, b  V con a  b;
con 2 o mas aristas de la forma:
a) (a, b) para un grafo dirigido
b) {a, b} para un grafo no dirigido
GRADO O VALENCIA DE UN VÉRTICE
Definición 10. Sea G un grafo o multígrafo no dirigido, para cualquier vértice v
de G, el grado de v que se denota como grad(v), es el numero de aristas en G que
son incidentes con v. En este caso, un bucle en un vértice v se considera como dos
aristas incidentes en v.
Teorema: Si G = (V, E) es un grafo o multígrafo no dirigido, entonces:
Definición 11. Para cualquier grafo o multígrafo no dirigido, el numero de
vértices de grado impar siempre es par.
Definición 12. Un grafo o multígrafo no dirigido donde los vértices tienen el
mismo grado se denomina grafo regular y se denota como el grafo K-regular
(donde K es el grado del vértice)
Definición 13. Sea G = (V, E), un grafo o multígrafo no dirigido sin vértices
aislados, entonces G tiene un circuito Euleriano si G es conexo y todo vértice
de G es de grado par
Definición 14. Sea G = (V, E), un grafo o multígrafo dirigido, para cuaLuier vértice v que
pertenece a V:
Definición 15. Sea G = (V, E), un grafo o multígrafo dirigido, para cualquier vértice v que
pertenece a V:
a) El grado de entrada de v denotado como ge(v) es el numero de aristas de G que llegan a v
b) El grado de salida de v denotado como gs(v) es el numero de aristas de G que salen de v.
Definición 16. Sea G = (V, E), un grafo o multígrafo dirigido sin vértices aislados. EL grafo
G tiene un circuito Euleriano dirigido si y solo si G es conexo y el ge(v) = gs(v), v  V
Definición 17. Sea G = (V, E), un grafo o multígrafo con v  3, se dice que G tiene un
ciclo Hamiltoniano, si existe un camino que comienza y termina en el mismo vértice
pasando exactamente una vez por cada vértice.