GRAFOS ISOMORFOS

Dados G=(V,E) y G´=(V´,E´), se denomina isomorfismo de G a G´ a la

aplicación biyectiva f tal que para a,bV, {a,b}E  se cumple
{f(a),f(b)}E´. Es decir, la aplicación que relaciona biyectivamente pares
de vértices de E con pares de vértices de E´, de modo que los vértices
conectados por aristas siguen estándolo

G y G´ se denominan isomorfos, y son matemáticamente iguales, solo

varia la apariencia, o sea, que se mantienen las adyacencias,
estructura, caminos y ciclos.

Prof. Ofelia Nazario Bao

 a b 1

2 4

c d
3
G G´
Los grafos G y G ‘ son isomorfos pues existe la biyección f: V  V ‘
definida por f(a) = 2, f(b) = 1, f(c) = 3, f(d) = 4 que conserva la
adyacencia.

Ejemplo: ¿ Son grafos isomorfos?

Prof. Ofelia Nazario Bao

Ejemplo: Determinar si los grafos G y H que se muestran son isomorfos-
v3
u1 u2 v1
u5 u6
v2
v6
u3 v5 v4
u4
G H

Solución: Tanto G como H tienen seis vértices y siete aristas. Ambos

tienen cuatro vértices de grado dos y dos vértices de grado 3. Luego
vamos a definir una función f .
Asignamos f( u1)= v6 , f (u2) = v3 , f (u3) = v4 , f (u5) = v1 , f (u6 ) = v2 y
para ver si f preserva o no la adyacencia, examinemos la matriz de
adyacencia de G y H con sus filas y columnas etiquetadas con las
imágenes de los vértices correspondientes de G.

Prof. Ofelia Nazario Bao

 u1 u2 u3 u4 u5 u6 v6 v3 v4 v5 v1 v2

u1 0 1 0 1 0 0 v6 0 1 0 1 0 0
u2 1 0 1 0 0 1 v3 1 0 1 0 0 1
A (G) = A (H) =
u3 0 1 0 1 0 0 v4 0 1 0 1 0 0
u4 1 0 1 0 1 0 v5 1 0 1 0 1 0
u5 0 0 0 1 0 1 v1 0 0 0 1 0 1
u6 0 1 0 0 1 0 v2 0 1 0 0 1 0

Prof. Ofelia Nazario Bao

EJERCICIO. ¿ Los siguientes grafos son isomorfos?

Prof. Ofelia Nazario Bao

 GRAFOS PLANARES

Se dice que un grafo es plano si puede dibujarse en el plano de manera

que ningún par de sus aristas se corte.
Un grafo puede ser plano aunque habitualmente se dibuje con cortes de
aristas, ya que cabe la posibilidad de que se pueda dibujar de manera
diferente sin ningún corte.
Ejemplo:
¿Es K4 un grafo plano?

Prof. Ofelia Nazario Bao

 Q3 es un grafo plano como se muestra en la figura

Ejercicios: ¿Es K5 y K3.3 grafos planares?

Prof. Ofelia Nazario Bao

Una representación planar particular de un multigrafo finito se denomina
mapa.
Un mapa (M) dado divide al plano o esfera en áreas conexas denominadas
regiones

r4 r1 r4
r3 r5
r1 r
2 r2 r3
r7 r6
r8

8 regiones 4 regiones

R4 región externa

Prof. Ofelia Nazario Bao

La frontera de cada región r de un mapa M está formada por una
secuencia de aristas que forman un camino cerrado.
El grado de la región r, g(r) es la longitud del camino cerrado que bordea
r. A veces el camino cerrado es un ciclo. Si no lo es, alguna arista aparece
dos veces en el camino
Teorema 3 :La suma de los grados de las regiones de un mapa M = 2· nº
de aristas.

Toda arista es frontera de 2 regiones o frontera doble de la misma región,

con lo cual cada una se cuenta doble.
Ejemplo de frontera doble :

Prof. Ofelia Nazario Bao

Ejemplo: Identifique para cada mapa las fronteras y el grado de cada
región y verifique el teorema 3
E
A B
r1
C r2
r2 D
D A B
r3 r1
r3

E C
(a) ( b)

(a): r1 = {A,B,C,A} r2 ={A,C,B,E,D,E,A} r3 ={A,B,E,A}

gr (r1) = 3 g( r2 ) = 6 g ( r3) = 3
Suma= 3+6+3 = 12 , puesto que hay 6 aristas

Prof. Ofelia Nazario Bao

FORMULA DE EULER

Teorema 4:Sea M un mapa conexo con V vértices, E aristas y

R regiones.

R=E–V+2
Ejemplo: Supongamos que un grafo plano y conexo tiene 20
vértices, cada uno de los cuáles tiene grado 3¿En cuántas regiones
divide el plano una representación plana de ese grafo?

Corolario: Sea G un grafo plano simple y conexo con e aristas, v

vértices y v  3 . Entonces e  3v  6

Prof. Ofelia Nazario Bao

Ejemplo: Verifique el corolario anterior para los grafos siguientes:

(a)
(b)

(a) v = 4 , e = 5 y e  3v  6

5  3(4)  6

56

Prof. Ofelia Nazario Bao

e  3v  6
Prof. Ofelia Nazario Bao
Grafos no planares Teorema de Kuratowski
Hemos visto que K5 y K3.3 son grafos no planos.
Cualquier grafo que contenga como subgrafo a uno de estos dos
grafos tampoco serán planos

•Grafos homeomorfos: 2 grafos son homeomorfos si uno de ellos se

puede obtener a partir del otro mediante la inserción o eliminación de
nuevos vértices.

Un grafo no es plano si y solo si, tiene un subgrafo homeomorfo al

grafo completo K5 o al grafo bipartido completo K3.3

Prof. Ofelia Nazario Bao

El grafo de Petersen NO ES PLANO, ya
que contiene una subdivisión de K3,3.

Prof. Ofelia Nazario Bao

 Coloreado de grafos

Introducción
Los problemas relacionados con colorear mapas de regiones, como los
mapamundis, han generado muchos resultados de la teoría de grafos. Al
colorear un mapa, se suele asignar colores distintos a las regiones que
tienen una frontera común.
Nos planteamos el problema de determinar el menor número de colores que
deben utilizarse para colorear un mapa de modo que dos regiones
adyacentes no tengan el mismo color.

Prof. Ofelia Nazario Bao

Prof. Ofelia Nazario Bao
 Coloración de grafos

Definición

Dado un conjunto de colores C, una coloración por vértices de un grafo

G = (V, E) es una función f : V C tal que si u v  E entonces f (u)  f (v).

En otras palabras, una coloración por vértices de un grafo es una asignación de

colores a los vértices de manera tal que a vértices adyacentes les correspondan
colores diferentes. En realidad los elementos del conjunto C pueden ser objetos
de cualquier naturaleza, y en última instancia lo único que interesa es su
número, pero se usa la metáfora de los colores porque es intuitiva y fácil de
comprender.

Prof. Ofelia Nazario Bao

Grafo k-colorable

Definición
Un grafo G es k-colorable si admite una coloración con k colores. Al
menor k tal que G es k-colorable se le llama número cromático de G y se
denota  (G).
Obviamente todo grafo de orden n es n-colorable. K n no se puede
colorear con menos de n colores, pues como todos sus vértices son
adyacentes cada uno debe pintarse de un color diferente. Por lo tanto
 (Kn) = n.

•El número cromático de un grafo sin aristas es 1.

•Un camino de longitud n > 2 tiene número cromático 2, ya que sus

vértices pueden pintarse con dos colores en forma alternada, comenzando
por un extremo.

Prof. Ofelia Nazario Bao

Algoritmo de Welch-Powell para colorear un grafo

Ejemplo: Colorear el siguiente grafo:

v1 v2

v3 v4 v5

v6 v7

1. Ordenar los vértices del grafo según grado decreciente. Esa

ordenación puede no ser única puesto que algunos vértices
pueden tener el mismo grado
Vértice: v1 v4 v5 v6 v2 v3 v7
Grado: 5 4 4 4 3 3 3
Prof. Ofelia Nazario Bao
2. Use un color para colorear el primer vértice y para colorear en
orden secuencial, cada vértice de la lista que no es adyacente a un
vértice pintado previamente con este color.
Vértice: v1 v4 v5 v6 v2 v3 v7
Grado: 5 4 4 4 3 3 3
Color: a a
3. Comience de nuevo en la parte superior de la lista y repita el
proceso pintando con un segundo color los vértices no coloreados
previamente.
Vértice: v1 v4 v5 v6 v2 v3 v7
Grado: 5 4 4 4 3 3 3
Color: a b b a
4. Continué repetidamente usando colores adicionales hasta que
haya pintado todos los vértices
Vértice: v1 v4 v5 v6 v2 v3 v7
Grado: 5 4 4 4 3 3 3
Color: a b c c b d a
Prof. Ofelia Nazario Bao
 Ejercicio: Repita el proceso usando los siguientes grafos y halle
el número cromático para cada uno de los casos.

v1 A H

v2 v3 B G

C F
v4 v5

v6 D E

Prof. Ofelia Nazario Bao

Colores y mapas

Se dice que dos regiones de un grafo multiplanar son adyacentes si

tiene una arista en común.
Colorear un mapa M se entiende asignar colores a las regiones de M
tal que las regiones adyacentes tengan colores distintos.
Un mapa es n-coloreable si existe una coloración de M que usa n
colores.
Todo mapa en el plano se puede representar por medio de un grafo.
Para establecer una correspondencia, cada región del mapa se
representa mediante un vértice. Una arista conecta dos vértices si las
regiones representadas por dichos vértices tiene frontera en común.
Dos regiones que se tocan en un solo punto no se consideran
adyacentes.
Al grafo resultante se le llama grafo dual del mapa.

Prof. Ofelia Nazario Bao

Prof. Ofelia Nazario Bao
Mapa de los Estados de Venezuela

Prof. Ofelia Nazario Bao

Prof. Ofelia Nazario Bao
Coloración del grafo de Venezuela con 4 colores

Prof. Ofelia Nazario Bao

Prof. Ofelia Nazario Bao
Ejercicio:¿Cuáles son los grafos duales para los siguientes mapas y
cuál es el número cromático para cada uno de ellos?

Prof. Ofelia Nazario Bao

Ejercicio de aplicación :
¿Cómo se puede programar los 7 exámenes finales de una universidad de
modo que ningún estudiante tenga dos exámenes al mismo tiempo?
Considere las siguientes parejas de asignaturas tienen alumnos en común:
1y2 , 1y3, 1y4, 1y7, 2y3, 2y4, 2y5, 2y7, 3y4, 3y6, 3y7, 4y5, 4y6, 5y6, 5y7,
6y7.

Prof. Ofelia Nazario Bao

Prof. Ofelia Nazario Bao
Prof. Ofelia Nazario Bao
Un ejemplo de esto es encontrar el tiempo más óptimo para ir de una
ciudad a otra en un mapa. En este caso, los vértices representarían las
ciudades y las aristas las carreteras que las unen, cuya ponderación
viene dada por el tiempo que se emplea en atravesarlas.

Prof. Ofelia Nazario Bao

Ejemplo: Encontrar el camino mínimo entre P y Q del siguiente grafo:

Consiste en buscar un camino de longitud mínima entre P y Q

siendo la longitud del camino la suma de las longitudes de sus
aristas,
El camino mínimo debe ser un camino simple.
Un camino mínimo entre P y Q es:
(P, A1 ,A2,A5, A3Prof.
,A6Ofelia
,Q) Nazario
que tiene
Bao longitud 14
Algoritmo de la distancia mínima: Dijkstra

El algoritmo de Dijkstra, también llamado algoritmo de caminos

mínimos, es un algoritmo para la determinación del camino más corto,
desde un vértice origen, hacia el resto de los vértices en un grafo que
tiene pesos en cada arista.

Teorema: El algoritmo de Dijkstra realiza operaciones (sumas y

comparaciones) para determinar la longitud del camino más corto entre
dos vértices de un grafo simple, conexo y no dirigido con n vértices

La idea en este algoritmo consiste en ir explorando todos los caminos

más cortos que parten del vértice origen y que llevan a todos los demás
vértices; cuando se obtiene el camino más corto desde el vértice origen
hasta el resto de los vértices que componen el grafo, el algoritmo se
detiene.

Prof. Ofelia Nazario Bao

Ejercicio:
Sea G el grafo ponderado siguiente. Halle el camino mínimo entre P y Q

Prof. Ofelia Nazario Bao

Ejemplo: Dada la siguiente red, donde se muestran las distancias entre los
vértices en kilómetros, se quiere determinar la ruta más corta entre el
origen O y el destino T

Prof. Ofelia Nazario Bao

Ejercicio:
Usted está reamueblando su casa y ha decidido comprar las cosas
siguientes, cada una en una tienda distinta:
(A) Un sofá, (B) mesa de café, (C) alfombra, (D) T.V. y (E) lámpara de pie.
Hay unas pocas restricciones en el orden de compra de los productos.
Primero la alfombra se debe comprar antes del sofá y la mesa de café (
debido a que los muebles deben hacer juego con la alfombra). Segundo, la
lámpara debe comprarse en último lugar porque, sino queda dinero, es de lo
que más se puede prescindir.
Usted ha determinado el tiempo de viaje (en minutos) entre tiendas y ha
organizado su información en el grafo siguiente. Halle el orden de las
compras que minimiza el tiempo de viaje
A
20 30
B C
10 40 40
35 30 30 50

D 15 Nazario
Prof. Ofelia E Bao
 Árboles

Introducción

En este capítulo nos centraremos en un tipo particular de grafo

denominado árbol, llamado así porque tales grafos se asemejan a los
árboles. Por ejemplo , los árboles genealógicos son grafos que
representan relaciones de parentesco. Los árboles genealógicos utilizan
los vértices para representar los miembros de una familia y las aristas
representan las relaciones entre padres e hijos.

Prof. Ofelia Nazario Bao

Definición 1: Un árbol libre es un grafo no dirigido, conexo y aciclico (sin ciclos).

Teorema 1: Sea G un grafo. Entonces las siguientes expresiones son equivalentes:

• G es un árbol.
• Cada par de vértices distintos está conectado por uno y sólo un camino simple.
• G es conexo, pero si eliminamos una arista deja de serlo.
• G no tiene ciclos, pero si añadimos una arista se forma exactamente un ciclo.
• G no tiene ciclos y tiene n - 1 aristas.
• G es conexo y tiene n - 1 aristas.

Prof. Ofelia Nazario Bao

Teorema 2: Todo árbol con más de un vértice posee, al menos, dos vértices de
grado 1.
El árbol formado por un único vértice y sin aristas se denomina árbol
degenerado

Prof. Ofelia Nazario Bao

Definición 2: Un bosque F es un grafo sin ciclos; por tanto cada una de las
componentes conexas de F es un árbol.
Los árboles y por lo tanto los bosques son 2-coloreables

Prof. Ofelia Nazario Bao

Definición 3: Sea G un grafo, decimos que T es un árbol de expansión
(spanning tree) de G si T es un subgrafo que incluye todos los vértices de G
(spanning subgraph) .
•Si G tiene n vértices, entonces cualquier árbol de expansión T de G debe tener
n-1 aristas
•Un grafo con n vértices puede llegar a contener nn-2 subárboles

Prof. Ofelia Nazario Bao

Ejercicios: Halle todos los árboles de expansión de los grafos siguientes.¿Deben
tener todos los árboles de expansión T de G el mismo número de aristas?

Prof. Ofelia Nazario Bao

 Árboles de expansión mínima
Si G es un grafo cuyas aristas tienen asignadas longitudes, es decir es un
grafo ponderado, se denomina árbol de expansión mínima ( minimun span
ing tree – MST) T de G, aquel que tienen la mínima suma de longitudes.
(también llamado árbol recubridor mínimo)

Algoritmos (Dijkstra) para hallar un árbol de expansión

mínima
Algoritmo 1. La entrada es un grafo G con m vértices
a. Ordene las aristas de G por longitudes decrecientes
b. Proceda secuencialmente borrando cada arista que no desconecte el
grafo hasta que quede m-1 aristas.
c. El resultado son las aristas restantes ( ya que forman un árbol de
expansión mínimo)

Prof. Ofelia Nazario Bao

Algoritmo 2. La entrada es un grafo G con m vértices
a. Ordene las aristas de G por longitudes crecientes
b. Proceda secuencialmente añadiendo una arista cada vez a los m vértices
de G tal que no se formen ciclos hasta que se han añadido m-1 aristas.
c. El resultado son las m-1 aristas que han sido añadidas ( ya que forman un
árbol de expansión mínimo)
A 4 B
A B 7
8 8
7 3 7
C D
7 5 D 7
C 4 4
6 4 12 8 E
9 6
9 5
E F
4 10
F G H

Prof. Ofelia Nazario Bao