Teora de Grafos

Definiciones y conceptos
Definiciones y Ejemplos

Definicin Sea V un conjunto finito no vaco, y sea EVV.

El par (V, E) es un grafo dirigido (sobre V), o dgrafo,
donde V es el conjunto de vrtices, o nodos y E es su
conjunto de aristas.
Escribimos G = (V, E) para denotar tal dgrafo.
La figura proporciona un ejemplo de un grafo dirigido
sobre V= {a, b, c, d, e} con E= {(a, a), (a, b), (a, d), (b, c)}.
La direccin de una arista se indica al colocar una flecha
dirigida sobre ella, como se muestra. Para cualquier
arista, como (b ,c) decimos que la arista es incidente con
los vrtices b, c; b es adyacente hacia c, mientras que c
es adyacente desde b. Adems, el vrtice b es el origen, o
fuente, de la arista (b, c) y el vrtice c es el trmino o
vrtice terminal. La arista (a, a) es un ejemplo de un lazo
y el vrtice e que no tiene aristas es un vrtice aislado.
Cuando no importa la direccin de las aristas, la
estructura G = (V, E), donde E es ahora un conjunto de
pares no ordenados sobre V, es un grafo no dirigido. En
un grafo no dirigido hay aristas no dirigidas, como las
aristas {a, b}, {b, c} {a, c}, {c, d} de la figura.
Una arista como {a, b} representa {(a, b), (b, a)}.
Aunque (a, b) = (b, a) slo si a = b, tenemos que
{a, b} = {b, a} para todos a, b.

En general si no se especifica que un grafo G es dirigido

o no, supondremos que es no dirigido.
Definicin Sean x, y vrtices (no necesariamente
distintos) de un grafo no dirigido G = (V, E). Un camino
x-y en G es una sucesin alternada finita (sin lazos)
x= x0, e1, x1, e2, x2, e3,...,en-1, xn-1, en, xn=y
de vrtices y aristas de G, que comienza en el vrtice x y
termina en el vrtice y y que contiene las n aristas
ei={xi-1, xi} donde 1in.

La longitud de un camino es n, el nmero de aristas que

hay en el camino (Si n = 0, no existen aristas, x = y, y el
camino se denomina trivial).
Cualquier camino x-y donde x = y (y n > 1) es un camino
cerrado. En caso contrario, el camino es abierto.

C1) {a,b}, {b,d}, {d,c}, {c,e}, {e,d}, {d,b}: se repiten los

vrtices d y b, as como las aristas {b,d}({d,b}.
C2) b c d e c f: se repite el vrtice c.
C3) {f, c}, {c, e}, {e, d}, {d, a}.
Definicin Consideremos un camino x-y en un grafo no
dirigido G = (V, E).
a) Si no se repite alguna arista en el camino x-y, entonces
el camino es un recorrido x-y. Un recorrido x-x es un
circuito.
b) Cuando ningn vrtice del camino x-y se presenta ms
de una vez, el camino es un camino simple x-y. El
trmino ciclo se usa para describir el camino simple
cerrado.
bcdecf es un recorrido b-f pero no un camino
simple b-f.
El camino {f,c},{c,e},{e,d},{d,a} es un recorrido f-a y un
camino simple f-a.
Las aristas {a,b},{b,d},{d,c},{c,e},{e,d} y {d,a} forman
el circuito a-a.
Las aristas {a,b},{b,c},{c,d} y {d,a} forman un ciclo a-a.
Resumen

Vrtice(s) Arista(s)
repetido(s) repetida(s) abierto cerrado Nombre

S S S Camino
S S S Camino (cerrado)

S No S Recorrido
S No S Circuito
No No S Camino simple
No No S Ciclo
Teorema Sea G = (V, E) un grafo no dirigido, con a, b
V, ab. Si existe un recorrido de a a b, entonces existe
un camino simple de a a b.
Demostracin. Como hay al menos un recorrido de a a
b, seleccionamos el que tenga la longitud ms corta,
digamos {a,x1},{x1,x2},...,{xn,b}. Si este recorrido no es
un camino simple, tenemos la situacin
{a,x1},{x1,x2},...,{xk-1,xk},{xk,xk+1},{xk+1,xk+2},...,
{xm-1,xm},{xm,xm+1},...,{xn,b},
donde k<m y xk=xm, posiblemente con k=0 y a(=x0)=xm, o
m=n+1 y xk=b(=xn+1). Pero entonces
{a,x1},{x1,x2},...,{xk-1,xk},{xm,xm+1},...,{xn,b}
es un recorrido simple ms corto de a a b.
Definicin Sea G = (V, E) un grafo no dirigido. Decimos
que G es conexo si existe un camino simple entre
cualquiera dos vrtices distintos de G.

Sea G = (V, E) un grafo dirigido. Su grafo no dirigido

asociado es el grafo obtenido de G si no se tienen en
cuenta las direcciones de las aristas. Si se obtiene ms de
una arista no dirigida de un par de vrtices distintos de G,
entonces slo una de estas aristas se dibuja en el grafo no
dirigido asociado. Cuando este grafo asociado es conexo,
consideramos que G es conexo.

Un grafo que no es conexo se llama disconexo.

El grafo G = (V, E), con V={a, b, c, d, e, f, g},
E={{a,b},{a,c},{a,d},{b,d}{e,f},{f,g}} no es conexo ya
que, por ejemplo, no hay un camino simple de a a e.
Sin embargo, el grafo est compuesto por piezas, que son
grafos conexos.
Por lo tanto, un grafo no dirigido G = (V, E) es disconexo
si y slo si V puede separarse en al menos dos
subconjuntos V1, V2 tales que no haya una arista en E de
la forma {x, y} donde xV1 e yV2.

Un grafo es conexo si y slo si tiene solamente una

componente.

Definicin Para cualquier grafo G = (V, E), el nmero de

componentes de G se denota con (G).
 EJEMPLO (G)=2 para el grafo de la figura.

Definicin Un grafo G=(V, E) es un multigrafo si existen

a,b V, ab, con dos o ms aristas de la forma:
1) (a, b) para un grafo dirigido;
2) {a, b} para un grafo no dirigido.
La figura muestra un ejemplo de un multigrafo dirigido.
Existen tres aristas de a a b, por lo que podemos decir
que (a, b) tiene multiplicidad 3. Las aristas (b, c) y (d, e)
tienen multiplicidad 2. Adems, la arista (e, d) y
cualquiera de las aristas (d, e) forman un circuito
(dirigido) de longitud 2 en el multigrafo.
Subgrafos, Complementos e
Isomorfismos de Grafos
Qu tipo de subestructura nos sirve para analizar un
grafo?
Es posible trazar dos grafos que parezcan distintos pero
que tengan la misma estructura subyacente?

Definicin Si G = (V, E) es un grafo (dirigido o no),

entonces G1 = (V1, E1) es un subgrafo de G si V1 V
y E1 E, donde cada arista de E1 es incidente con los
vrtices de V1.
La figura nos muestra un grafo no dirigido G y dos de
sus subgrafos G1 y G2. Los vrtices a, b son aislados en
el subgrafo G1. La parte b) de la figura nos muestra un
ejemplo de grafo dirigido. Aqu el vrtice w es aislado en
G.
Definicin Dado un grafo (dirigido o no) G = (V, E), sea
G1=(V1, E1) un subgrafo de G. Si V1 = V, entonces G1 es
un subgrafo recubridor de G.

Los subgrafos G3 y G4 son subgrafos recubridores del

grafo G en la parte a) de la figura anterior. Los grafos
dirigidos G y G son dos grafos recubridores de G en
la parte b).
Definicin Sea G = (V, E) un grafo (dirigido o no). Si U
V, el subgrafo de G inducido por U es el subgrafo cuyo
conjunto de vrtices es U y que contiene todas las aristas
(de G) de la forma:
1) (x, y), para x, y U, si G es dirigido o;
2) {x, y} para x, y U, si G no es dirigido

Denotaremos a este subgrafo como U.

Un subgrafo G de un grafo G = (V, E) es un subgrafo

inducido si existe U V tal que G = U.
Para los subgrafos de la figura, vemos que G2 es un
subgrafo inducido de G pero el subgrafo G1 no es un
subgrafo inducido ya que no aparece la arista {a, d}.
EJEMPLO Sea G el grafo de la figura.
Los subgrafos G1 y G2 de la figura son inducidos.
G1=U1 para U1 ={b, c, d, e}.
G2=U2 para U2={a, b, e, f}.
G3 no es un subgrafo inducido; los vrtices c, e estn en
G3, pero la arista {c, e} de (G) no est presente.
Definicin Sea un vrtice en un grafo G = (V, E)
(dirigido o no). El subgrafo de G denotado G , tiene el
conjunto de vrtices V1=V {} y el conjunto de aristas
E1 E, tal que E1 contiene todas las aristas de G excepto
las incidentes con el vrtice . (Por lo tanto G es el
subgrafo de G inducido por V1).

De forma similar si e es una arista del grafo G = (V, E)

(dirigido o no), obtenemos el subgrafo G e =(V1, E1) de
G, donde el conjunto de aristas es E1=E {e}, y el
conjunto de vrtices no cambia (es decir, V1=V).
Sea G el grafo no dirigido de la figura.
G1 es tal que G1 = G c; G1 es el subgrafo de G
inducido por el conjunto de vrtices U1={a,b,d,f,g,h}, y
G1 =V {c} = U1.
G2 es tal que G2= G e, y e es la arista {c, d}.
Podemos eliminar ms de un vrtice (arista).
G3=(Gb)f = (Gf)b = G{b, f} = U3, para
U3={a, c,d,g,h}.
Definicin Sea V un conjunto de n vrtices. El grafo
completo sobre V, que se denota con Kn, es un grafo no
dirigido sin lazos tal que para todos a, b V, a b, existe
una arista {a, b}.

La figura anterior proporciona los grafos completos Kn,

para 1n4.
Definicin Sea G un grafo no dirigido sin lazos con n
vrtices. El complementario de G, ( G ) es el subgrafo
de Kn formado por los n vrtices de G y todas las aristas
que no estn en G. (Si G = Kn, G es un grafo con n
vrtices y ninguna arista. A este grafo se le llama grafo
nulo).

En a) aparece un grafo no dirigido de cuatro vrtices. Su

complementario se muestra en la parte b).
En el complementario el vrtice a est aislado.
Definicin Sean G1=(V1, E1) y G2=(V2, E2) dos grafos no
dirigidos. Una funcin f: V1 V2 es un isomorfismo de
grafos si:
1) f es biyectiva
2) a, b V1, {a, b} E1 si y slo si {f(a), f(b)} E2.

Cuando existe tal funcin, G1 y G2 son grafos isomorfos.

Para los grafos de las partes a) y b) de la figura, la
funcin f definida por f(a)=w, f(b)=x, f(c)=y, f(d)=z
da como resultado un isomorfismo. (De hecho cualquier
correspondencia uno a uno entre {a, b, c, d} y {w, x, y, z}
ser un isomorfismo, ya que ambos grafos son
completos). En consecuencia en lo que se refiere a la
estructura estos grafos se consideran iguales, cada uno es
isomorfo al grafo K4.
Para los grafos c) y d) de la figura se necesita un poco
ms de cuidado. La funcin g definida por:
g(m)=r, g(n)=s, g(p)=t, g(q)=u

es uno a uno y sobre. Sin embargo, aunque {m, q} es una

arista del grafo de la parte c), { g(m), g(q)} = {r, u} no es
una arista del grafo de la parte d). En consecuencia, la
funcin g no define un isomorfismo de grafos.
Para mantener la correspondencia de aristas se considera
la funcin uno a uno y sobreinyectiva h tal que:
h(m)=s, h(n)=r, h(p)=u, h(q)=t

En este caso tenemos las correspondencias de aristas

{m,n} {h(m),h(n)} = {s,r}; {m,p} {h(m),h(p)} = {s,u}
{m,q} {h(m),h(q)} = {s,t}; {n,q} {h(n),h(q)} = {r,t}
{p,q} {h(p),h(q)} = {u,t}

entonces h es un isomorfismo de grafos.

Tenemos dos grafos, cada uno con diez vrtices, no se ve
de inmediato si estos grafos sean isomorfos.
aq cu er gx iz
bv dy fw ht js

C1: a f h c b g j e d i
C2: q w t u v x s r y z
C1 se corresponde con C2
Grados de un vrtice recorridos
y circuitos Eulerianos
Como hemos visto el nmero de aristas incidentes en un
vrtice podra utilizarse para mostrar que dos grafos no
dirigidos no son isomorfos. Ahora veremos que esta idea
puede todava ayudarnos ms.

Definicin Sea G un grafo o multigrafo no dirigido. Para

cualquier vrtice de G, el grado de , que se denota
grad(), es el nmero de aristas en G que son incidentes
con . En este caso, un lazo en un vrtice se considera
como dos aristas incidentes en .
EJEMPLO Para el grafo de la figura, grad(b)=grad(d)=
=grad(f)=grad(g)=2, grad(c)=4, grad(e)=0 y grad(h)=1.
Para el vrtice a se tiene grad(a)=3 ya que contamos el
lazo dos veces. Como h tiene grado 1, se le llama vrtice
colgante.
Teorema Si G = (V, E) es un grafo o multigrafo no
dirigido, entonces vV grad (v) 2 E .

Demostracin. Al considerar cada arista {a, b} del grafo

G, encontramos que la arista contribuye con una unidad a
grad(a) y a grad(b) y, en consecuencia, con dos unidades
a vV grad (v) .
As, 2 E cuenta grad(v), para todo vV y
vV
grad (v) 2 E .
Corolario Para cualquier grafo o multigrafo no dirigido,
el nmero de vrtices de grado impar debe ser par.

EJEMPLO Un grafo (o multigrafo) no dirigido donde los

vrtices tienen el mismo grado se denomina grafo
regular. Si grad(v) = k para todos los vrtices v, entonces
el grafo es k-regular.

Es posible tener un grafo 4-regular con 10 aristas?.

Del teorema anterior tenemos que 2 E = 20 = 4 V , por lo
que tenemos cinco vrtices de grado 4. La figura
proporciona dos ejemplos no isomorfos que satisfacen lo
solicitado.
Si deseamos que cada vrtice tenga grado 4, con 15
aristas en el grafo, entonces 2 E = 30 = 4 V , por lo que
resulta imposible tener dicho grafo.
Ahora veamos la razn por la que Euler desarroll la idea
de grado de un vrtice: para resolver el problema de los
siete puentes de Knigsberg.
Se deca que los habitantes hacan paseos dominicales
tratando de encontrar una forma de caminar por la ciudad
cruzando cada puente exactamente una vez y regresando
al punto donde haban iniciado el paseo.
Con el fin de determinar si exista o no dicho circuito,
Euler represent las cuatro zonas de la ciudad y los siete
puentes con el multigrafo que se muestra en la figura.

Encontr cuatro vrtices con grado(a)=3 grado(c)=3

grado(d)=3 y grado(b)=5. Tambin encontr que la
existencia de tal circuito dependa del nmero de vrtices
de grado impar del grafo.
Definicin Sea G = (V, E) un grafo o multigrafo no
dirigido sin vrtices aislados. Entonces G tiene un
circuito Euleriano si existe un circuito en G que recorra
cada arista del grafo exactamente una vez. Si existe un
recorrido abierto de a a b en G que recorre cada arista de
G exactamente una vez, este recorrido se llamar
recorrido Euleriano.

El problema de los siete puentes quedar resuelto si

caracterizamos los grafos que tienen un circuito
Euleriano.
Teorema Sea G = (V, E) un grafo o multigrafo no dirigido
sin vrtices aislados. Entonces G tiene un circuito Euleriano
si y slo si G es conexo y todo vrtice de G tiene grado par.

Demostracin Si G tiene un circuito Euleriano, entonces para cualquier

a, b V existe un recorrido de a a b ; a saber, la parte del circuito que
comienza en a y termina en b, por lo tanto de un teorema anterior se
sigue que G es conexo.
Sea c el vrtice inicial del circuito Euleriano. Para cualquier otro vrtice
v de G, cada vez que el circuito llega a v entonces partir de ese vrtice .
As, el circuito pasa por dos aristas (nuevas) incidentes con v o por un
lazo (nuevo) en v. En cada caso, se contribuye con dos unidades a
grad(v). Como v no es el punto inicial y cada arista incidente a v se
recorre una sola vez, obtenemos dos unidades cada vez que el circuito
pasa por v, de modo que grad(v) es par. Para el vrtice inicial c, la
primera arista del circuito debe ser distinta de la ltima, y como
cualquier otro paso por c produce dos unidades para grad(c), tenemos
que grad(c) es par.
Demostracin
Recprocamente, sea G un grafo conexo tal que todos los vrtices tienen
grado par. Si el nmero de aristas de G es 1 o 2 , entonces G debe ser
como los grafos de la figura. Los circuitos Eulerianos son inmediatos en
estos casos.

Ahora procederemos por induccin y supondremos que el resultado es

valido para todas las situaciones con menos de n aristas.
Demostracin (Continuacin...)
Si G tiene n aristas, seleccionamos un vrtice c en G como punto inicial
para construir un circuito Euleriano. Como el grafo G es conexo y cada
vrtice tiene grado par, podemos construir al menos un circuito C que
contenga a c. (Verifique esto examinando el recorrido ms largo en G
que comienza en c). Si el circuito contiene todas las aristas de G, hemos
terminado. Si no, eliminamos las aristas del circuito de G,
asegurndonos de eliminar cualquier vrtice que haya quedado aislado.
El subgrafo restante K tiene todos los vrtices de grado par, pero puede
no ser conexo. Sin embargo, cada componente de K es conexa y tendr
un circuito Euleriano. Adems, cada uno de estos circuitos Eulerianos
tiene un vrtice que est en C. En consecuencia, podemos partir de c y
recorrer C hasta llegar al vrtice c1 que est en el circuito Euleriano de
una componente C1 de K. Entonces se recorre este circuito Euleriano y
al regresar a c1, continuamos en C hasta llegar a un vrtice c2 que est
en el circuito Euleriano de la componente C2 de K. Como el grafo G es
finito, podemos continuar este proceso hasta construir un circuito
Euleriano para G.
Si G es conexo y no tiene demasiados vrtices de grado
impar, podemos hallar al menos un recorrido Euleriano en
G.

Corolario Si G es un grafo o multigrafo no dirigido sin

vrtices aislados, entonces podemos construir un recorrido
Euleriano en G si y slo si G es conexo y tiene exactamente
dos vrtices de grado impar.
Demostracin Si G es conexo y a y b son los vrtices de G
de grado impar, aadimos una arista adicional {a, b} a G.
Ahora tenemos un grafo G1 conexo tal que todos sus
vrtices son de grado par. Por lo tanto, G1 tiene un circuito
Euleriano C; cuando eliminamos la arista {a, b} de C,
obtenemos un recorrido Euleriano para G. (As, el recorrido
Euleriano comienza en uno de los vrtices de grado impar y
termina en otro vrtice de grado impar).
Si regresamos ahora al problema de los siete puentes de
Knigsberg.

Nos damos cuenta que el grafo es un multigrafo conexo,

pero tiene cuatro vrtices de grado impar. En
consecuencia, no tiene ni un recorrido Euleriano ni un
circuito Euleriano.
Definicin Sea G = (V, E) un grafo o multigrafo dirigido.
Para cualquier v V,
El grado de entrada de v es el nmero de aristas de G
que llegan a v y se denota con ge(v).
El grado de salida de v es el nmero de aritas de G que
parten de v y se denota con gs(v).

Si el grafo o multigrafo dirigido tiene uno o ms lazos,

cada lazo de un vrtice dado v contribuye con una unidad
a ge(v) y a gs(v).

Teorema Sea G = (V, E) un grafo o multigrafo dirigido

sin vrtices aislados. El grafo G tiene un circuito
Euleriano dirigido si y slo si G es conexo y ge(v)=gs(v)
para todo vV .
Grafos Planos
En un mapa de carreteras, las lneas que indican las
carreteras y autopistas se intersecan por lo general
solamente en puntos de confluencia o en poblaciones.
Pero hay ocasiones en que las carreteras parecen
intersecarse cuando una se localiza sobre otra, en este
caso, las carreteras estn en diferentes niveles o planos.

Definicin Un grafo (o multigrafo) G es plano si

podemos dibujar G en el plano de modo que sus aristas se
intersequen slo en los vrtices de G. Este dibujo de G se
conoce como una inmersin de G en el plano.
EJEMPLO Los grafos de la figura son planos. El primero
es un grafo 3-regular, ya que cada vrtice tiene grado 3 ;
es plano pues ningn par de aristas se intersecan, excepto
en los vrtices. El grafo b) parece un grafo no plano; las
aristas {x, z} y {w, y} se cruzan en un punto distinto de
un vrtice. Sin embargo, podemos trazar nuevamente este
grafo, como se muestra en la parte c) de la figura. En
consecuencia K4 es plano.
EJEMPLO Al igual que K4, tambin K1, K2 y K3 son
planos.
En la figura se muestra un intento de representar K5 en el
plano.
Definicin Un grafo G = (V, E) es bipartito si V = V1
V2 , V1 V2 = y cada arista de G es de la forma {a, b}
con a V1 y b V2. Si cada vrtice de V1 est unido con
los vrtices de V2, se tiene un grafo bipartito completo.
En este caso, si V1 =m, V2 =n, el grafo se denota con Km,n.

El grafo a) satisface la definicin con V1={a, b} y V2={c,

d, e}. Si se aaden las aristas {b, d} y {b, c}, el resultado
es el grafo bipartito completo K2,3, que es plano.
El grafo b) de la figura es K3,3. Sea V1 ={h1, h2, h3} y V2
={u1, u2, u3}; interpretamos V1 como un conjunto de casa
y V2 como un conjunto de servicios. Entonces K3,3 es el
grafo de servicios. Podemos unir las casa con los
servicios, evitando que haya superposicin de las lneas
de servicio?. En la figura parece que esto no es posible y
que K3,3 no es plano.
Definicin Sea G = (V, E) un grafo no dirigido sin lazos,
tal que E . Una subdivisin elemental de G resulta
cuando eliminamos una arista e ={u, w} de G y entonces
las aristas {u, v}, {v, w} se aaden a G e, donde vV.

Los grafos no dirigidos sin lazos G1=(V1, E1) y G2=(V2,

E2) son homeomorfos si son isomorfos o si ambos
pueden obtenerse del mismo grafo no dirigido sin lazos H
por una sucesin de subdivisiones elementales.
Consideremos los grafos G, G1, G2 y G3 de la figura. En
este caso G1 se obtiene de G por medio de una subdivisin
elemental: se elimina la arista {a, b} de G y se aaden las
aristas {a, w} y {w, b}. El grafo G2 se obtiene de G
mediante dos subdivisiones elementales. Por lo tanto G1 y
G2 son homeomorfos. As mismo, G3 puede obtenerse de G
con cuatro subdivisiones elementales, por lo que G3 es
homeomorfo a G1 y G2.
Sin embargo G1 no puede obtenerse de G2 (o G2 de G1) por
una sucesin de subdivisiones elementales. Adems, el
grafo G3 puede obtenerse de G1 o G2 por una sucesin de
subdivisiones elementales: tres para G1 y dos para G2. Pero
ni G1 ni G2 pueden obtenerse de G3 por una sucesin de
subdivisiones elementales.
Podra pensarse que los grafos homeomorfos son isomorfos
excepto, posiblemente, por los vrtices de grado 2. En
particular, si dos grafos son homeomorfos, son
simultneamente plano (o no planos).

Teorema (de Kuratowski) Un grafo no es plano si y slo

si contiene un subgrafo que es homeomorfo a K5 o K3,3.

Demostracin Si un grafo G tiene un subgrafo

homeomorfo a K5 o K3,3, est claro que G no es plano.
Sin embargo, el reciproco de este teorema es ms difcil
de demostrar.
EJEMPLO La figura es un grafo conocido llamado grafo
de Petersen. La parte b) de la figura proporciona un
subgrafo del grafo Petersen que es homeomorfo a K3,3
La figura muestra cmo se obtiene el subgrafo de K3,3 por
una sucesin de cuatro subdivisiones elementales. Por lo
tanto, el grafo de Petersen no es plano.
Cuando un grafo o multigrafo es plano y conexo obtenemos la
siguiente relacin descubierta por Euler, para la cual necesitamos
contar el nmero de regiones determinadas por un grafo o
multigrafo conexo plano, el nmero (de estas regiones) se define
slo cuando se tiene una inmersin plana del grafo. Por ejemplo,
la inmersin plana de K4 en la parte a) de la figura demuestra
cmo esta representacin de K4 determina 4 regiones en el plano:
3 de rea finita, R1, R2 y R3, y la regin infinita R4 . Cuando
observamos la figura b) podra pensarse que K4 determina 5
regiones, pero esta representacin no es una inmersin plana de
K4. As, el resultado de la figura a) es el nico que nos interesa.
Teorema Sea G = (V, E) un grafo o multigrafo plano
conexo con V v y E e . Sea r el nmero de regiones en
el plano determinadas por una inmersin (o representacin)
plana de G; una de estas regiones tiene un rea infinita y se
conoce como regin infinita. Entonces v e + r = 2.
Demostracin La demostracin se hace por induccin sobre e. Si
e = 0 o 1, entonces G es isomorfo a uno de los grafos de la figura.
El grafo de la parte a) tiene v = 1, e = 0 y r = 1; entonces v e + r
= 2. Para el grafo b), v = 1, e = 1 y r = 2. El grafo c) tiene v = 2, e
= 1 y r = 1. En ambos casos, v e + r =2.
Demostracin (Continuacin...)
Ahora sea kN y supongamos que el resultado es verdadero
para cualquier grafo o multigrafo plano conexo con e
aristas, donde 0 e k. Si G = (V, E) es un grafo o
multigrafo plano conexo con v vrtices, r regiones y e = k+1
aristas, sean a, bV con {a, b} E.
Considere el subgrafo H de G obtenido al eliminar la arista
{a, b} de G (Si G es un multigrafo y {a, b} es una de un
conjunto de aristas entre a y b, entonces la eliminamos slo
una vez). En consecuencia, se puede escribir H = G {a, b}
o G = H + {a, b}. Consideremos los dos casos siguientes,
que dependen de si H es conexo o disconexo.
Demostracin (Continuacin...)
Caso1: Los resultados de las partes a), b), c) y d) de la figura
muestran cmo un grafo G puede obtenerse de un grafo conexo
H cuando se dibuja el lazo (nuevo) {a, a} como en las partes a) y
b) o cuando la arista (nueva) {a, b} une dos vrtices distintos en
H como en las partes c) y d). En todas estas situaciones, H tiene v
vrtices, k aristas y r 1 regiones, ya que una de las regiones de
H se divide en dos regiones para G. La hiptesis de induccin
aplicada al grafo H indica que v k + (r 1) = 2 y de esto se
sigue que 2 = v (k + 1) + r = v e + r. As, en este caso el
teorema de Euler es cierto para G.
Demostracin (Continuacin...)
Caso2: Ahora consideremos el caso en que G {a, b} = H es un
grafo disconexo como se muestra en la figura e) y f). En este
caso, H tiene v vrtices, k aristas y r regiones. As mismo, H tiene
dos componentes H1 y H2, donde Hi tiene vi vrtices, ei aristas y ri
regiones, para i = 1, 2. Adems, v1 + v2 = v, e1 + e2 = k (= e 1) y
r1 + r2 = r + 1 ya que H1 y H2 determinan, cada uno, una regin
infinita. Cuando se aplica la hiptesis de induccin a H1y H2
vemos que v1 e1 + r1=2 y v2 e2 + r2=2.En consecuencia, (v1 +
v2) (e1 + e2) + (r1 + r2) = v (e 1) + (r + 1) = 4, y de esto se
sigue que v e + r = 2, y as establecemos el teorema de Euler
para G.
Para cualquier regin R en una inmersin plana de un grafo
o multigrafo, el grado de R, que se denota con grad(R), es el
nmero de aristas recorridas en un camino cerrado (el ms
corto) por (las aristas de) la frontera de R.

Si G = (V, E) es el grafo de la figura, entonces esta

inmersin plana de G tiene cuatro regiones donde: grad(R1)
= 5, grad(R2) =3, grad(R3) =3, grad(R4) =7.
En este caso grad(R4)=7, como lo determina el camino
cerrado abghgfda.
La figura muestra una segunda inmersin plana de G, otra
vez con cuatro regiones, y en este caso grad(R5) = 4,
grad(R6) = 3, grad(R7) = 5, grad(R8) = 6.
El camino cerrado bghgfb da grad(R7)=5.
grad ( Ri ) 18 i 5 grad ( Ri ) 2 9 2 E .
4 8
Se ve que i 1

Esto es cierto en general ya que cada arista de la inmersin

plana es parte de la frontera de dos regiones
Corolario Sea G = (V, E) un grafo plano conexo sin lazos
con V v , E e 2 y r regiones.
Entonces 3r 2e y e3v 6.

Demostracin Como G no tiene lazos ni es un multigrafo,

la frontera de cada regin (incluyendo la regin infinita)
contiene al menos tres aristas, por lo tanto cada regin tiene
grado 3. En consecuencia, 2e=2 E = la suma de los grados
de las r regiones determinadas por G y 2e 3r. Del teorema
de Euler, 2 = v e + r v e + (2/3)e = v (1/3)e, por lo
que 6 3v e o e 3v 6.
Consideremos ahora lo que este corolario implica y lo que
no implica. Si G =(V, E) es un grafo conexo sin lazos con
|E|2, entonces si e3v 6, se sigue que G no es plano. Sin
embargo, si e 3v 6, no se puede concluir que G sea
plano.

EJEMPLO El grafo K5 no tiene lazos y es conexo con 10

aristas y cinco vrtices. En consecuencia, 3v6 = 156 = 9
10 = e. Por lo tanto, por el corolario vemos que K5 no es
plano.
EJEMPLO El grafo K3,3 no tiene lazos y es conexo con
nueve aristas y seis vrtices. En este caso, 3v 6 = 18 6 =
12 9 = e. Sera un error concluir a partir de esto que K3,3
es plano; cometeramos el error de estar argumentando al
revs.
Sin embargo, K3,3 no es plano. Si K3,3 fuera plano, entonces
como cada regin del grafo est limitada por al menos
cuatro aristas, tendramos 4r 2e. Del teorema de Euler
tenemos, v e + r = 2 o r =e v + 2 = 9 6 + 2 = 5, y 20 =
4r 2e =18. De esta contradiccin se tiene que K3,3, no es
plano.
Caminos y ciclos
Hamiltonianos
En 1859, el matemtico irlands Sir William Rowan
Hamilton (1805-1865) desaroll un juego que vendi a un
fabricante de juguetes de Dubln. El juego era un
dodecaedro regular de madera con 20 esquinas (vrtices) en
las que aparecan inscritos los nombres de las ciudades ms
importantes. El objetivo del juego era encontrar un ciclo
alrededor de las aristas del slido, de modo que cada ciudad
estuviera en el ciclo (exactamente) una vez.
Definicin Si G = (V, E) es un grafo o multigrafo tal que
|V| 3, decimos que G tiene un ciclo Hamiltoniano si existe
un ciclo en G que contenga cada vrtice de V. Un camino
Hamiltoniano es un camino simple (y no un ciclo) de G
que contiene todos los vrtices.

Dado un grafo con un ciclo hamiltoniano, la eliminacin de

cualquier arista en el ciclo produce un camino hamiltoniano.
Sin embargo, es posible que un grafo tenga un camino
hamiltoniano sin que tenga un ciclo hamiltoniano.
Podra parecer que la existencia de un ciclo (camino)
Hamiltoniano y la existencia de un circuito (recorrido)
Euleriano para un grafo son problemas similares.
El ciclo (camino) Hamiltoniano tiene como objetivo pasar
por cada vrtice de un grafo una sola vez; el circuito
(recorrido) recorre el grafo pasando por cada arista
exactamente una vez.
Por desgracia, no existe una relacin til entre las dos ideas
y, a diferencia de los circuitos (recorridos) Eulerianos, no
existen condiciones necesarias y suficientes en un grafo G
que garanticen la existencia de un ciclo (camino)
Hamiltoniano.
EJEMPLO Si G es el grafo de la figura, las aristas {a,b},
{b,c}, {c,f}, {f,e}, {e,d}, {d,g}, {g,h}, {h,i} forman un
camino hamiltoniano para G. Pero tiene G un ciclo
Hamiltoniano?.
Como G tiene nueve vrtices, si existe un ciclo
Hamiltoniano en G, ste debe contener nueve aristas.
Comencemos en un vrtice b y tratemos de construir un
ciclo Hamiltoniano.

Con las aristas {c, f} y {f, i} en

el ciclo, no podemos tener la
arista {e, f} en el ciclo. Una
vez en e, ya no podemos
continuar. Por lo tanto, este
grafo no tiene un ciclo
Hamiltoniano.
Sugerencias tiles para tratar de encontrar un ciclo
Hamiltoniano en un grafo G = (V, E).
1) Si G tiene un ciclo Hamiltoniano, entonces para vV,
grad(v) 2.
2) Si aV y grad(a) = 2, entonces las dos aristas incidentes
con el vrtice a deben aparecer en cualquier ciclo
Hamiltoniano de G.
3) Si aV y grad(a) 2, cuando tratamos de construir un
ciclo Hamiltoniano, una vez que hemos pasado por el
vrtice a, dejamos de tener en cuenta las aristas no
utilizadas incidentes con a.
4) Al construir un ciclo Hamiltoniano para G, no podemos
obtener un ciclo para un subgrafo de G a menos que
contenga todos los vrtices de G.
EJEMPLO En la figura tenemos un grafo conexo G y
queremos saber si G contiene un camino Hamiltoniano. La
parte b) de la figura proporciona el mismo grafo con un
conjunto de etiquetas x, y.

Ahora, como V 10 , si G tuviera un ciclo Hamiltoniano

debera haber una sucesin alternativa de 5 letras x y 5
letras y. Solamente tenemos 4 vrtices etiquetados con x. De
ah que G no tenga un camino (o ciclo) Hamiltoniano.
Porqu funciona este argumento? En la figura se ha vuelto a
dibujar el mismo grafo y vemos que es bipartito. Un grafo
bipartito no puede tener un ciclo de longitud impar. Tambin es
cierto que si el grafo no tiene un ciclo simple de longitud impar,
entonces es bipartito. En consecuencia cuando un grafo conexo
no tiene ciclo de longitud impar (y es bipartito), el mtodo
descrito anteriormente puede ser til para determinar si el grafo
no tiene un camino Hamiltoniano.
EJEMPLO En el campamento que el profesor Alfredo ha
organizado con su grupo de antropologa, 17 estudiantes
comen juntos en una mesa circular. Como intentan conocerse
mejor, tratan cada tarde de sentarse con dos compaeros
distintos. Durante cuntas tardes pueden hacer esto? Cmo
pueden hacerlo?.

Para resolver este problema, consideremos el grafo Kn, donde

n 3 y n es impar. Este grafo tiene n vrtices (uno para cada
estudiante) y n nn 1 / 2 aristas.
2

Un ciclo Hamiltoniano corresponde a una disposicin de
lugares. Cada uno de estos ciclos tiene n aristas, por lo que se
tiene como mximo 1 / n n n 1 / 2 ciclos Hamiltonianos
2

sin que dos de ellos tengan una arista en comn.
Consideremos el crculo de la figura a) y el subgrafo de Kn que
consta de n vrtices y n aristas {1,2}, {2,3}, ... , {n1, n}, {n,
1}. Mantenemos los vrtices en la circunferencia fijos y
rotamos este ciclo Hamiltoniano en el sentido de las
manecillas del reloj, hasta el ngulo [1/(n1)](2). Esto
produce el ciclo Hamiltoniano (ver b)) formado por las aristas
{1,3}, {3,5},{5,2},{2,7}, ... , { n, n3},{n3, n1}, {n1, 1}.
Este ciclo Hamiltoniano no tiene aristas en comn con el
primer ciclo.
Si n 7 y seguimos rotando de esta manera el ciclo de la figura
a), hasta los ngulos [k/(n1)]( 2), donde 2 k (n3)/2
obtenemos un total de (n1)/2 ciclos Hamiltonianos, sin que haya
dos aristas en comn.
Por lo tanto, los 17 estudiantes que participan en el campamento
pueden comer durante [(17-1)/2] = 8 das antes de que tengan que
sentarse junto a otro estudiante por segunda vez. Usando la figura
a) con n=17, podemos obtener ocho de estas posibles
disposiciones.
 El n-cubo ( hipercubo)

La computadora tradicional llamada en

serie, se ejecuta una instruccin a la vez .

Los algoritmos que tambin ejecutan una

instruccin a la vez son llamados
algoritmos en serie.
 En los ltimos aos, al disminuir el costo del hardware, se
han construido Computadoras Paralelas con muchos
procesadores, los cuales pueden ejecutar varias
instrucciones a la vez Frecuentemente, se utilizan a los
grafos para ilustrar la topografa de estas maquinas
paralelas .Los algoritmos asociados con estos equipos son
algoritmos paralelos .Muchos problemas se pueden
resolver mas rpidamente en computadoras paralelas que
en computadoras seriales, aunque no todos los problemas.

Una maquina paralela muy utilizada actualmente es

conocida como el n-cubo o hipercubo .El n-cubo tiene 2
procesadores, n > o = 1, cada procesador se representa
mediante un nodo.
 Cada procesador tiene su propia memoria
local .Una arista conecta dos vrtices si la
representacin binaria de sus etiquetas
difieren en exactamente un bit .

Durante una unidad de tiempo, todos los

procesadores de el n-cubo pueden ejecutar
una instruccin de manera simultnea y
luego comunicarse con el procesador
adyacente.
1-cubo
2 procesadores 0,1

2-cubo
4 procesadores
00,01,10,11
 3-cubo

8 procesadores
000 001
000,001,010,011,100,101,
110,111

010 011

100 110
111
101
4-cubo
16 procesadores
Ejemplo de 16 procesadores
Una grafica se llama plana si puede dibujarse en un plano sin
que haya cruce en sus aristas
Una grafica completa de n-vrtices denotada por kn , es un grafica con n vrtices
donde cada nodo se conecta con todos los otros nodos del grafo

K2
1 2

K3
1
NOTA : K5
no es plano
2 3
K5
1
K4

1 2 2
3

3 4
4 5
 RECORRIDO A LO PROFUNDO DE UN GRAFO

Es un procedimiento para visitar cada nodo y cada arista de un grafo

G=(V,E), de forma ordenada y sin repetir elementos visitados .El
siguiente algoritmo realiza esta bsqueda a lo profundo
int. dfinic ( )
{
/* Asignar color blanco (inicial) a los nodos */
for i =1 to |v|
color [i]:=blanco
/*visitar en orden los nodos*/
for i=1 to |v|
if (color[i]==blanco)dfs(i)
else continue;
return
}
/*funcin que visita en profundidad al grafo*/
int dfs(v)
{
color [v]:=gris;
/*procedimiento en preorden del vrtice v*/
Remad;:=Adyacentes (v)
While (remadj<>Nil)
{
W:=first (remadj);
if (color [w]==blanco)dfs (w);
else /*encontr arista de retroceso*/
remadj =resto (remadj);
}
/*Proceso en post-orden de v
color [v]:=Negro;
return
 Aplicar la bsqueda a lo profundo

a b f

e i g
d c

a= {b,d}
c= {b,d,e}
f retroceso
b= {d} f= {g} cruce
a b
c g i
retroceso
g= {h,i} d
e h
cruce cruce
 retroceso
cruce
8 1 retroceso
R
e
5 6
t 9 r
cruce 2
r e
o t
10 cruce
c r 7 4
3
e o
s c
o e cruce
s
o
 BOSQUE ABARCADOR EN PROFUNDIDAD PARA
GRAFOS DIRIGIDOS

Durante un recorrido en profundidad se tienen diferentes clases de

aristas .Los arcos que nos llevan a vrtices sin visitar se llaman
ARCOS DE RBOL y forman un bosque abarcador en profundidad
del grafo de entrada .Los arcos de rbol deben formar un bosque
abarcador en profundidad del grafo de entrada .Los arcos de rbol
deben formar realmente un bosque.

Un ARCO DE RETROCESO va de un nodo a uno de sus

antecedentes en el bosque abarcador .Observe que un arco que va de
un vrtice hacia si mismo es un arco de retroceso

Un arco que no es parte del bosque abarcador que va de un vrtice a

un descendiente propio se llama ARCO DE AVANCE

Los arcos que van de un vrtice a otro que no es antecesor ni

descendiente, se conoce como ARCOS CRUZADOS
 rboles abarcadores
f 6
1 c 4
a
BOSQUE
ABARCADOR
g 7
b 2 d 3 e 5 8
9
Tree 1 tree2 h i

tree3

F B A

G D C
 #0
A
retroceso retroceso ARBOL
#1 A
B

#3 B
#2
C D C D
cruce
cruce tree1
#4
E cruce E

F G
F #5 G #6

tree2
 Suponga que se numeran los vrtices de un grafo dirigido
de acuerdo con el orden en que se marcaron los nodos
visitados durante la bsqueda en profundidad .Esto es ,se
puede asignar un arreglo que contabiliza los nodos.
Color [v]:=grey
Numero [v]:=cont; /*lneas de adicionar */
Cont:=cont+1;
Estas dos lneas nos permiten numerar los nodos del grafo
en profundidad .As la bsqueda en profundidad asigna a
todos los descendientes de nodo v, nmeros mayores al
asignado a v. De hecho un descendiente de v si y solo si
numero (v)<=numero (w).
Los arcos de avance irn de los vrtices de baja
numeracin a los de alta numeracin y los arcos de
retroceso van de los vrtices de alta numeracin a los de
baja numeracin
Todos los arcos cruzados van de vrtices de alta
numeracin a los de baja numeracin
RECORRIDOS EN UN GRAFO
En una gran cantidad de problemas con grafos, es
necesario visitar sistemticamente los vrtices y
aristas del grafo .La bsqueda en
PROFUNDIDAD Y EN AMPLITUD, son dos
tcnicas importantes de recorrido del grafo.
Analicemos ahora el recorrido en Amplitud se
basa en a partir del nodo actual visitar a todos sus
nodos adyacentes en forma tan amplia como sea
posible.
 Al igual que en la bsqueda en profundidad, la bsqueda
en amplitud construye un rbol abarcador del grafo de
entrada .La gran diferencia en el orden de visitar los
nodos entre la bsqueda a lo profundo y bsqueda en
amplitud, consiste en la estructura utilizada para guardar
los nodos a visitar; en la bsqueda a lo profundo se utiliza
una pila o stack de procedimiento recursivo mientras que
en la bsqueda en amplitud se utiliza una cola para
guardar tales nodos a visitar.
Los rboles abarcadores generados son diferentes por
cada recorrido. En el caso de la bsqueda a lo profundo se
trata de construir un rbol con la mayor altura, dando
control de la bsqueda al nodo hijo que no haba sido
visitado .Mientras que un rbol generado por la bsqueda
a lo ancho es un rbol frondoso, dando preferencia a la
vista de todos los nodos adyacentes no visitados que son
guardados en una estructura cola, para dar posteriormente
control de la bsqueda al primer nodo de la cola.
Ejemplo :Recorrer el grafo G en profundidad y en amplitud ,generando
sus rboles abarcadores

1 4

5 2
3

8
10
RECORRIDO A LO PROFUNDO
cruce

5 1 8
2 3
cruce cruce a
cruce
v
c
9 a
r
4 n
u
cruce c
c
10 e
e

6 7

cruce
Recorrido a lo ancho

1 8

9 10
4
cruce

6 7

Expansin a lo ancho
 Ejemplo 2
1 4

5 2
3

8
10
Recorrido a la profundo
1
r
e 8
t 4
r avance avance
o 9
6
c cruce
e retroceso
s 5 10
o
retroceso
3
7

2
 Recorrido a lo ancho
COLA
retroceso
1
4 6 7 5 3 2
4
6
8 9 10
7
r
e cruce
5 9 10
t
r retroceso
o cruce
c 3 cruce
e
s
o
2