1 GRAFOS.
1.1 DEFINICIONES.
Un grafo surge en diversas ramas de la matemática …nita.
De…nition 1 Un grafo es una pareja G = (V; E) donde V es un conjunto …nito de vértices o nodos
V = fv1 ; : : : vn g
y E también es un conjunto …nito de de aristas (edges)
E = fe1 ; : : : em g :
Las siguientes generalidades se presentarán con frecuencia.
1. Algunos autores le llaman a n el orden del grafo y m se denomina el grado.
2. Las aristas pueden ser subconjutos (siempre de dos elementos) para los grafos no dirigidos, que
llamaremos simplemente grafos. Por ejemplo ek = fvi ; vj g con lo cual indicamos que si ek 2 E, los
nodos vi y vj son adyacentes.
3. También puede ser que ek = (vi ; vj ), lo cual nos dice que el nodo vi se conecta de manera dirigida con
el nodo vj . Si en G todas sus aristas son pares ordenados, le llamaremos grafo dirigido o digrafo.
Obvio
(vi ; vj ) 6= (vj ; vi ) :
4. La arista fvi ; vj g de un grafo se dice que incide en los nodos vi y vj .
5. La arista (vi ; vj ) de un digrafo tiene por nodo inicial a vi y nodo …nal a vj .
6. Los hay mixtos, es decir, grafos con ambos tipos de aristas.
7. También hay las llamadas aristas múltiples, por ejemplo, la arista fvi ; vj g de un grafo puede tener
multiplicidad n > 1. Tales grafos se denominan multigrafos.
8. También los digrafos pueden ser mútliples.
9. La arista no dirigida fu; ug se llama loop y un grafo que posee un loop se llama pseudografo.
Nos enfocaremos principalmente en los llamados grafos simples, que son los que no tienen aristas
múltiples ni loops.
De…nition 2 En un grafo (simple o múltiple) se de…ne el grado de un vértice como el número de aristas
incidentes en él y se denota con deg (v). Un loop contribuye en dos al grado del nodo.
De…nition 3 En un digrafo, el grado inerterior de un nodo es el número de aristas que tienen al nodo
como nodo …nal; el grado exterior es el número de aristas que tienen al nodo como nodo inicial. El grado
interior se denotad deg (u) y el grado exterior (out) se denota deg+ (u).
1
Denotemos con jAj el número de elementos de un conjunto …nito.
Teoremirijillo 4 (Handshake) Dado un grafo G = (V; E), simple, múltiple o pseudo, entonces
X
deg (v) = 2 jEj :
v2V
Proof. La prueba es simplemente la explicación de que cada arista en E incide en dos nodos si no es un
loop. Por ello, cada arista contribuye en dos a la suma de los grados de los nodos de G; si es un loop,
contribuye en dos en un mismo nodo.
Como sencillo Corolario tenemos que siempre habrá un número par de nodos que tienen grado impar.
Pues si hubiesen 2k + 1 nodos con grado impar, la suma de sus grados sería impar, más los de grado par,
nos daría que 2 jEj es impar.
Ahora es sencillo establecer el Handshake para digrafos.
Teoremirijillo 5 (Handshake) Dado un digrafo G = (V; E), tenemos que
X X
deg (v) = deg+ (v) = jEj :
v2V v2V
Cada arista dirigida contribuye en 1 en cada uno de los grados en cada nodo.
Un nodo de grado se llama nodo colgante (pendant node). Un nodo con grado cero, se llama aislado.
De…nition 6 Un camino (path) en un grafo o digrafo G = (V; E) es una secuencia …nita de aristas en E.
Un grafo conexo es un grafo en el que siempre hay un camino de un nodo a cualquier otro nodo distinto.
Un digrafo se dice fuertemente conexo hay un camino de un nodo a cualquier otro nodo distinto. Si
eliminamos las direcciones, el grafo resultante se llama grafo subyacente del digrafo. Un digrafo es
débilmente conexo si su grafo (no dirigido) subyacente es conexo.
1.2 GRAFOS ESPECIALES.
1. Ciclo (Cycle). Es el grafo simple conexo con n nodos todos ellos de grado 2. Se denota Cn .
2. Rueda (Wheel). Se obtiene el ciclo Cn al agregar un nodo que será adyacente a todos los nodos de
Cn . Por ello tendrá n + 1 nodos y n de ellos tendrán grado 3 mientras que uno solo tendrá grado n.
La notación es Wn para el grafo con n + 1 nodos según Rosen y otros autores. Wolfram denota con
Wn al Wheel con n nodos.
3. Completo. Es el grafo simple cuyos nodos se contectan con todos. Es decir, si tiene n nodos, todos
ellos tienen grado n 1. Se denota con Kn .
4. Bipartita Completo. Cuando en un grafo G = (V; E), el conjunto de nodos se particiona en dos
subconjunos
V = V1 [ V2
de manera que cualquier nodo de Vi no es adyacente con un nodo de Vi el grafo se denomina bipartita.
La adyacencia siempre será entre nodos de distinto subcounjunto. Si los nodos de G son de color
blanco y color negro, nodos del mismo color nunca serán adyacentes. La adyacencia siempre será entre
nodos de distinto color. Si además todo nodo de V1 es adyacente con todo nodo de V2 y viceversa, el
grafo se llama bipartita completo. Si jV1 j = m y jV2 j = n, el bipartita completo se denota Km;n .
Desde luego jV j = m + n.
2
5. n-Cubo. Es el grafo con 2n nodos a los que etiquetamos con las 2n cadenas binarias. Una vez
etiquetados, serán adyacentes si y sólo si su cadenas binarias di…erenen en exactamente un bit. Se
denota Qn . Por ejemplo, los nodos
00001011
00000011
son adyacentes en Q8 mientras que
00001011
10000011
no lo son. Q8 tiene 28 = 256 nodos.
De…nition 7 Dado un grafo G = (V; E), un subgrafo H = (U; F ) de G es un grafo que satisface U V
y F E. Lo denotamos con H G. Si H G y dos nodos u y v están en H, y si son adyacentes en H
siempre que lo son en G, diremos que H es subgrafo induicido.
Entonces, en grafos simples, si H es subgrafo inducido de G, de alguna manera H es subgrafo maximal,
digamos en el número de aristas una vez elegidos los nodos de H.
Teoremirijillo 8 Un grafo conexo G es bipartita (no necesariamente completo) si y sólo si no contiene
un ciclo C2k+1 como subgrafo.
Proof. Primero supongamos que G es bipartita. Entonces cualquier ciclo de longitud impar, que en
realidad es un camino de la forma
x0 ! x1 ! ! x2k ! x0
donde xi 6= xj siempre i 6= j no puedes ocurrir S. P. G. asumamos x0 2 V1 . Tons forzosamente
x1 2 V2
x2 2 V1
..
.
x2k 2 V1
y así x2k y x0 no son adyacentes y no se cierra el ciclo (la 2k + 1-ésima arista no existe).
Recíprocamente supongamos que G es un grafo que no contiene ciclos C2k+1 y sea v un nodo de G.
Construyamos el conjunto
X = fx 2 V : el camino más corto de x a v es de longitud parg :
Se tiene que X 6= ?, pues v mismo está en X ya que su único camino es de longitud cero. El caso de que
X consta únicamente de dos nodos fv; xg nos da como consecuencia que todo nodo y 62 X tiene longitud
mínima a v igual a 1 o 3 ¿porqué? Pues porque si tuviese lonitud 5 o más, habría otro nodo en X además
de x y v, además de que de x a v la longitud es 2, pues si fuese 4,
x ! y2 ! x1 ! y1 ! v
3
nos daría otro nodo en X. En los casos anteriores se tiene las biparticiones
fvg ; V n fvg ;
fv; xg ; V n fv; xg :
Tomemos tres nodos en X, x; v; x1 . Veremos que forzosamente x y x1 no son adyacentes. El conjunto
de nodos en comun en los caminos de v a x y de v a x1 no es vacío, pues al menos v es uno de ellos.
Puede haber varios. Pensemos en los caminos así
v = v 0 ! a1 ! a2 ! ! a2k 1 ! a2k = x;
v = v0 ! b1 ! b2 ! ! b2k 1 ! b2p = x1 :
Si el único nodo común es v, desde ahí se da la bifurcación de caminos. Y no pueden ser x y x1 adyacentes
porque nos daría un ciclo de longitud 2k + 2p + 1, ciclos que no hay en G. Tomemos el nodo común donde
se da la bifurcación para algún subíndice i. Es decir, los caminos son de la forma
v = v 0 ! a1 = b 1 ! a2 = b 2 ! ! ai = b i
y a partir de i + 1 los a’s son distintos de los b’s. Nótese que ai = bi puede ser, S. P. G. x1 , ello no afecta
el argumento, simplemente que de x1 a x hay una longitud también par. Pero este caso no elimina la
posibilidad de que x1 y x sean adyacentes, pues darían otro ciclo impar. Finalmente el caso de que ai = bi
no es ni x ni x1 . Pero ello nos dan dos caminos
ai = b i ! ! a2k = x
ai = b i ! ! b2p = x1
con el primero de longitud 2k i y 2p i respectivamente. Así pues, x y x1 no son adyacentes pues ello
nos daría un ciclo de lontiud
2k 2i + 2p + 1:
Hemos visto que dos nodos cualesquiera de X no pueden ser adyacentes, dando la bipartición de G como
X y V n X = V n X.
1.3 ISOMORFISMO.
Para estudiar la forma de los grafos y decidir que dos grafos son "iguales", precisamos de una caracterización
carente de ambigüedad que nos permita decidir.
De…nition 9 Dado un grafo G con V = fv1 ; : : : vn g construimos la matriz de adyacencia como la
matriz 2 3
a11 a1n
6 .. 7
AG = 4 ... . 5
an1 ann
donde aij es simplemente el número de aristas del nodo vi al nodo vj .
Si es un digrafo, entonces aij es el número de aristas dirigidas de vi a vj .
4
Desde luego, en un grafo, aij = aji . Por lo que toda matriz de adyacencia de un grafo será simétrica.
Si además es un grafo simple, será una matriz binaria: cero si no son adyacentes y uno si lo son. La
simetría no se cumple para los digrafos. No obstante, toda matriz de adyacencia tendrá entradas enteras
no negativas.
De…nition 10 Dos grafos G = (V; E) y H = (U; F ) son isomorfos si hay una función biyectiva
':V !U
de tal manera que v1 y v2 son adyacentes en G si y sólo si ' (v1 ) y ' (v2 ) son adyacentes en H.
Para decidir si dos grafos son isomorfos sin depender de la "dibujancia", precisamos de las matrices de
adyacencia. En realidad una biyección entre conjuntos de n elementos es una permutación 2 Sn . Como
hay un isomor…smo de grupos entre Sn y las matrices de permutación n n (se trata de las matrices que
se obtienen de la identidad por una simple permutación de …las).
Permutar los nodos de un grafo equivale a permutar las entradas de la matriz de adyacencia, pero
debemos tener cuidado de que si permutamos dos …las, debemos permutar las correspondientes columnas
para que en la diagonal sigan prevaleciendo los loops. Tenemos así el siguiente resultado
Teoremirijillo 11 Dos grafos simples G y H con matrices de adyacencia AG y AH de n n respectivamente
son isomorfos si y sólo hay una matriz de permutación P de orden n n
AH = P t AG P
Example 12 Un grafo G con matriz de adyacencia
2 2 3 3
1 0 1 0 0 1 1
6 2 6 1 0 1 0 0 0 7 7
6 6 7 7
6 3 6 0 1 0 1 0 1 7 7
6 6 7 7
AG = 6 4 6 0 0 1 0 1 0 7 7
6 6 7 7
6 5 4 1 0 0 1 0 0 5 7
6 7
4 6 1 0 1 0 0 0 5
1 2 3 4 5 6
se muestra en la …gura. También un grafo H
5
cuya matriz de adyacencia es
2 2 3 3
1 0 1 1 1 0 0
6 2 6 1 0 0 0 0 1 7 7
6 6 7 7
6 3 6 1 0 0 0 1 0 7 7
6 6 7 7
AH = 6 4 6 1 0 0 0 0 1 7 7
6 6 7 7
6 5 4 0 0 1 0 0 1 5 7
6 7
4 6 0 1 0 1 1 0 5
1 2 3 4 5 6
Las matrices de…nitivamente no son iguales. Pero aplicando la matriz de permutación correspondiente a
la permutación
1 2 3 4 5 6
= = 2 4 5 3 6 ;
1 4 6 5 3 2
o bien, con su permutación inversa
1
= 2 6 3 5 4 :
Las matrices de permutación son
2 3 2 3
1 0 0 0 0 0 1 0 0 0 0 0
6 0 0 0 1 0 0 7 6 0 0 0 0 0 1 7
6 7 6 7
6 0 0 0 0 0 1 7 6 0 0 0 0 1 0 7
6 7 o 6 7
6 0 0 0 0 1 0 7 6 0 1 0 0 0 0 7
6 7 6 7
4 0 0 1 0 0 0 5 4 0 0 0 1 0 0 5
0 1 0 0 0 0 0 0 1 0 0 0
Veamos que las matrices de adyacencia se relacionan con una de estas matrices de permutación y su
transpuesta según la ecuación AH = P t AG P . En efecto, usando
2 32 32 3
1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0
6 0 0 0 0 0 1 76 1 0 1 0 0 0 76 0 0 0 1 0 0 7
6 76 76 7
6 0 0 0 0 1 0 76 0 1 0 1 0 1 76 0 0 0 0 0 1 7
t
P AG P = 6 6 76 76 7
0 1 0 0 0 0 76 0 0 1 0 1 0 76 0 0 0 0 1 0 7
6 76 76 7
4 0 0 0 1 0 0 54 1 0 0 1 0 0 54 0 0 1 0 0 0 5
0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0
2 3
0 1 1 1 0 0
6 1 0 0 0 0 1 7
6 7
6 1 0 0 0 1 0 7
= 66 7 = AH :
1 0 0 0 0 1 7
6 7
4 0 0 1 0 0 1 5
0 1 0 1 1 0
La demostración del Teorema es simplemente el isomor…smo de grupos entre Sn y las matrices de
permutación de orden n, y que multiplicar a la izquierda a AG es permutar sus columnas y a la derecha
sus …las.
6
De…nition 13 Dado un grafo (S.P G. simple) un camino es una sucesión de vértices
x0 ! x1 ! ! xn :
El número de aristas será la longitud del camino. Los caminos que no repiten arista se llaman caminos
simples. Los caminos simples que satisfacen x0 = xn se llaman circuitos. Los caminos que no repiten
nodo excepto x0 = xn son los que llamamos ciclos.
Desde luego, en un circuito se pueden repetir nodos. Los caminos con x0 = xn se llaman cerrados.
Por ello los circuitos son caminos simples cerrados. Todo ciclo es un circuito pero no es recíproco.
De…nition 14 Un circuito es de Euler si visita todos los nodos exactamente una vez excepto el inicial y
el …nal. Un grafo que tiene un circuito de Euler se denomina grafo Euleriano.
De…nition 15 Un grafo de orden n que tiene un ciclo Cn se llaman grafo Hamiltoniano y el ciclo se
llama Ciclo de Hamilton.
Teoremirijillo 16 Un grafo (simple o no) tiene circuito de Euler si y sólo si todos sus nodos tienen nodo
par. Tendrá camino de Euler (camino simple no cerrado que recorre todas las arista) si y sólo si todos los
nodos tienen grado par excepto exactamente dos.
n
Teoremirijillo 17 Un grafo simple con n 3 nodos tal que todos sus nodos tienen deg tiene ciclo
2
de Hamilton.
Teoremirijillo 18 Un grafo simple con n 3 nodos tal que dos nodos no adyacentes cualesquiera u y v
satisfacen deg (u) + deg (v) n tiene ciclo de Hamilton.
Teoremirijillo 19 Si dos grafos son isomorfos y uno es Hamiltoniano, tons el otro también lo es.
Pero dos grafos hamiltonianos con el mismo número de nodos no necesariamente son isomorfos.
Algunos criterios para decidir que un grafo G no es hamiltoniano son
1. que G tenga un nodo de grado 1;
2. una vez que elegimos dos aristas de un nodo para visitarlo (in/out), el resto de sus aristas se inutilizan;
Que no podamos hallar un ciclo de Hamilton en un grafo no demuestra que no sea hamiltoniano. Para
dar un argmunento demostrativo que, por ejemplo, Petersen no tiene ciclo de Hamilton, apelamos a su
dibujo clásico, y clasi…camos los nodos como los de la "estrella" o internos y los del "pentágono" o externos.
S. P. G. asumimos que el ciclo comienza en el pentágono. Debemos recorrer los de la estrella. Disponemos
de cinco accesos pentágono-estrella, que para in/out precisamos de dos o cuatro aristas "puentes". Si son
dos, pueden ser consecutivas o no, lo que nos da dos subcasos. Y en estos tres casos, establecer que no
podemos regresar al nodo inicial. Se debe tener presente que este argumento sólo es aplicable a Petersen.
Pero puede ser aplicable a otros casos.
7
1.4 GRAFOS PLANOS.
Planar Graphs es un plano que puede trazarse en R2 sin que sus aristas se intersecten.
Los grafos no planos por excelencia son K3;3 y K5 .
Todo poliedro convexo se puede representar con un grafo plano. Averigüen la validez del recíproco.
Desde los griegos se sabía la propiedad de los poliedros que dice
V +R=E+2
donde V es el número de vértices, R el número de caras (regiones) y E es el número de aristas.
Dado una representación grá…ca de un grafo plano, las aristas, dado que no se intersectan, delimitarán
regiones. Una y sólo una de ellas será no acotada. Si Ri es una región, se denota @Ri a su frontera, que
estará conformada por al menos tres aristas. Toda arista será común a dos regiones (Teorema de los
cuatro colores)
Teoremirijillo 20 Si G es un grafo plano conexo con n = jV j, e = jEj y r = jRj con R el conjunto de
regiones delimitadas por las aristas, entonces
r + n = e + 2: