Unidad 1: Conceptos basicos

Grafos, digrafos y multigrafos

Definicion 1 (Grafo)
Un grafo G es un objeto (V, A) formado por un conjunto V no vaco, cuyos elementos se llaman
vertices, y un conjunto A de subconjuntos de dos elementos de V los cuales se llaman aristas.
Definicion 2 (Digrafo)
Un digrafo D es un objeto (V, E) formado por un conjunto V no vaco, cuyos elementos se llaman
vertices, y un conjunto E de pares ordenados de elementos de V los cuales se llaman arcos.
Definicion 3 (Multigrafo)
Un multigrafo G es un objeto (V, A, J) formado por dos conjuntos disjuntos no vacos V , A y una
funcion J de A al conjunto de subconjuntos de dos elementos de V . La funcion J se llama funcion
de incidencia, y los elementos de V y A se llaman vertices y aristas respectivamente.
Definicion 4 (Vertices extremos, adyacencia e incidencia en un grafo)
Sea G = (V, A) un grafo. Si e = {a, b} A, entonces:
a y b se llaman vertices extremos de la arista e.
a y b se llaman vertices adyacentes.
e y a se llaman incidentes entre s.
Definicion 5 (Aristas adyacentes en un grafo)
Sea G = (V, A) un grafo. Si e, f A tienen un vertice extremo comun, entonces e y f se llaman
adyacentes.
Definicion 6 (Vertices extremos en un digrafo)
Sea D = (V, E) un digrafo. Si e = (a, b) E, entonces a y b se llaman vertices inicial y final del
arco e respectivamente.
Definicion 7 (Aristas paralelas en un multigrafo)
Sea G = (V, A, J) un multigrafo. Si para e, f A ocurre que J(e) = J(f ), entonces e y f se llaman
aristas paralelas.

Representacion de grafos, digrafos y multigrafos

Definicion 8 (Lista de adyacencia de un vertice)
Sean G un grafo y a V . La lista de adyacencia de a, denotada por A(a) es el conjunto de vertices
de G que son adyacentes a a.
Definicion 9 (Matriz de adyacencia de un grafo (multigrafo))
Sea G un grafo (multigrafo) con n vertices. La matriz Ad = (adij ), de orden n n, es llamada
matriz de adyacencia de G, si adij es la cantidad de aristas que unen los vertices i-esimo y j-esimo.

Definicion 10 (Matriz de incidencia de un grafo (multigrafo))

Sea G un digrafo (multigrafo) con n vertices y m aristas. La matriz In = (inij ), de orden n m,
es llamada matriz de incidencia de G, si
 
1 , si el i-esimo vertice es extremo de la j-esima arista
inij =
0 , en cualquier otro caso

Definicion 11 (Matriz de incidencia de un digrafo)

Sea D un digrafo con n vertices y m arcos. La matriz In = (inij ), de orden n m, es llamada
matriz de incidencia de D, si

1 , si el i-esimo vertice es extremo final del j-esimo arco
inij = 1 , si el i-esimo vertice es extremo inicial del j-esimo arco
0 , en cualquier otro caso

Grado en grafos y digrafos

Definicion 12 (Grado de un vertice)
Sean G un grafo y D un digrafo

El grado de un vertice a de G, denotado por deg(a), es la cantidad de aristas incidentes en

este vertice.
El grado de entrada de un vertice a de D, denotado por deg (a), es la cantidad de arcos que
tienen a a como vertice final.
El grado de salida de un vertice a de D, denotado por deg+ (a), es la cantidad de arcos que
tienen a a como vertice inicial.
Lema 1 (Lema del apreton de manos)
En un grafo, el numero de vertices de grado impar es siempre par.

Subgrafos
Definicion 13 (Aristas restringidas a un conjunto)
Sea G = (V, A) un grafo y V 0 V . Con A|V 0 denotamos el conjunto de todas las aristas de A que
tienen ambos extremos en V 0 .
Definicion 14 (Subgrafo)
Sean G = (V, A) y G0 = (V 0 , A0 ) grafos. G0 se llama subgrafo de G, si V 0 V y A0 A|V 0 .

Definicion 15 (Subgrafo inducido)

Sea G = (V, A) un grafo y V 0 V . Se llama subgrafo inducido por V 0 en G, denotado por G|V 0 ,
al grafo G|V 0 = (V 0 , A|V 0 ).

Definicion 16 (Subgrafo de expansion)

Sea G = (V, A) un grafo. Si G0 = (V 0 , A0 ) es un subgrafo de G con V 0 = V , entonces G0 es llamado
subgrafo de expansion de G.
Ejercicio 1
1. Sea G = (V, A) un grafo sin lazos ni aristas multiples, con |V | 2. Mostrar que G tiene al
menos dos vertices con el mismo grado.
 2. Sea G = (V, A) un grafo sin lazos ni aristas multiples, cuyos vertices tienen grado k o k + 1.
Demuestre que la cantidad de vertices de grado k en G es (k + 1)|V | 2|A|.
3. A una fiesta asisten 20 invitados. Es posible que cada uno de ellos conozca a un numero
diferente de otros invitados?
4. En un mapa de una region aparecen 25 tramos de carretera. Sabiendo que los cruces de
carretera se producen siempre en una poblacion, y que de cada poblado parten al menos
cuatro caminos, que puede decirse del numero de poblaciones que aparecen en el mapa?
5. Disponemos de 6 ordenadores y 9 cables de conexion. Queremos que cada ordenador se
conecte con otros 3 ordenadores. Existe alguna forma de conectarlos? Es unica?
6. Una empresa adquiere una red de ordenadores. Cada ordenador se conecta con, a lo sumo,
cinco ordenadores y el numero total de conexiones es 40. Que puede decirse del numero de
ordenadores que se han comprado?
7. Determinar si la sucesion dada corresponde a la sucesion de grados de los vetices de un grafo.
a) 3,3,3,3,2
b) 1,2,3,4,4
c) 3,4,3,4,3
d ) 5,5,4,4,3,3,3,1,0,0
e) 3,3,2,2,2,2,1,1
f ) 6,4,4,4,3,3,3,3
g) 5,3,3,3,2,2,1,1

Tipos particulares de grafos

Definicion 17 (Grafo completo)
Un grafo G se llama completo si cada par de vertices distintos del grafo estan unidos exactamente
por una arista. Kn denota al grafo completo de n vertices.
Definicion 18 (Grafo r-partito)
Un grafo G = (V, A) es r-partito, si V admite una particion en r clases tal que toda arista de G
tiene sus extremos en clases diferentes.
Definicion 19 (Grafo r-partito completo)
Un grafo r-partito G se llama completo, si cualquiera dos vertices de clases diferentes de la particion
son adyacentes.
Definicion 20 (Grafo r-regular)
Si todos los vertices de un grafo G tienen el mismo grado r, entonces G se llama r-regular.

Definicion 21 (Grafo triangular)

Llamamos grafo triangular Tn , n N, al grafo cuyos vertices son los subconjuntos de dos elementos
de {1, . . . , n}, siendo adyacentes dos vertices si y solo si, la interseccion de sus subconjuntos es no
vaca.
Definicion 22 (Complemento de un grafo)
Dado un grafo G = (V, A). Si V (2) denota el conjunto de todos los pares de vertices de V con
componentes distintas, llamamos complemento de G al grafo G = (V, V (2) \ A).

Definicion 23 (Apareamiento)
Dado un grafo G = (V, A). M A se llama apareamiento en G, si cualquiera dos aristas distintas
en M son no adyacentes en G.
Definicion 24 (k-factor)
Se llama k-factor de un grafo G a cualquier subgrafo de expansion de G que sea k-regular.

Definicion 25 (k-factorizacion)
Dado un grafo G = (V, A). Si existen G1 = (V, A1 ),. . . ,Gn = (V, An ) cada uno de los cuales es un
k-factor de G, siendo A1 , . . . , An una particion de A, entonces G1 ,. . . ,Gn se llama k-factorizacion
de G.
Ejercicio 2
Muestre que si un grafo G tiene una 1-factorizacion, entonces G tiene un numero par de
vertices.
Muestre que Tn es (2n 4)-regular.
Dibuje los grafos Tn para n = 3, 4, 5, y muestre que Tn tiene parametros a = 2n 4, c = n 2
y d = 4, donde a es el grado de cualquier vertice, c es el numero de vertices adyacentes a
ambos x e y, cuando x e y son adyacentes, y d es es el numero de vertices adyacentes a ambos
x e y, cuando x e y son no adyacentes.
Muestre que el grafo Kn es (n 1)-regular.
Muestre que el grafo Km,n es n-regular, solo si m = n.
Dados un grafo G y su complemento G. Muestre que dos vertices de V son adyacentes en G
si, y solo si ellos no son adyacentes en G.

Conectividad de grafos
Definicion 26 (Estructuras en un grafo)
Sea G un grafo

Una sucesion alternada de vertices y aristas de G, v0 , e1 , v1 , . . . , vn1 , en , vn , para la cual vale

que ei = {vi1 , vi }, i = 1, . . . , n, se llama paseo en G.
Un paseo en G en el que todas las aristas son distintas se llama sendero.
Un sendero en G con vertices v1 , . . . , vn distintos entre s se llama camino.
Un paseo en G cuyos vertices satisfacen v0 = vn se llama paseo cerrado.
Un sendero en G cuyos vertices satisfacen v0 = vn se llama sendero cerrado o tour.
Un camino en G cuyos vertices satisfacen v0 = vn se llama camino cerrado o ciclo.
Definicion 27 (Grafo conectado)
Un grafo G se llama conectado si entre cualquier par de vertices distintos de G existe un camino
que los une.
Lema 2
Un grafo es bipartito si y solo si el no contiene ciclos de longitud impar.

Arboles
Definicion 28 (Bosque y arbol)
Un grafo sin ciclos se llama bosque.
Un grafo conectado sin ciclos se llama arbol.
Lema 3
Todo arbol es un grafo bipartito, pero no todo grafo bipartito es un arbol.

Lema 4
Dado un grafo T = (V, A), las siguientes proposiciones son equivalentes:
T es un arbol.
Cualquiera dos vertices distintos de T estan conectados mediante un unico camino.
T esta minimalmente conectado. Esto es T es conectado, pero para cualquier arista e A,
T 0 = (V, A {e}) es no conectado.
T es maximalmente aciclico. Esto es T es aciclico, pero para cualquier par de vertices no
adyacentes a, b V , T 0 = (V, A {a, b}) es ciclico.
Lema 5
Un grafo conectado con n vertices es un arbol si y solo si el tiene n 1 aristas.

Ejercicio 3
Pruebe:
1. Cualquier paseo cerrado de longitud impar contiene un ciclo.
2. Si G es un grafo con n vertices, cada uno de los cuales tiene grado al menos (n 1)/2,
entonces G es conectado.
3. Un grafo G = (V, A) es conectado si y solo si para cualquier biparticion de V existe una
arista en A que tiene extremos en clases distintas de la particion.
4. Si G es no conectado, entonces su complemento G es conectado.
5. Un grafo acclico de n vertices tiene a lo mas n 1 aristas.
6. Si G es un grafo con n vertices de grados estrictamente mayor que cero, y n 1 aristas ,
entonces G tiene al menos dos vertices de grado uno.
Solucion 1
1.
2. Por contradiccion asumamos que los n vertices de G tienen grado mayor o igual que (n1)/2
y que G no es conectado.
Sean x e y dos vertices que no estan conectados en G.
Llamemos x0 = x y xn1 = y y dado que deg(x0 ) (n1)/2, sean x1 , . . . xd(n1)/2e los vertices
que seguramente son adyacentes a x0 . As, si consideramos la lista de todos los vertices de G,
x0 , x1 , . . . , xd(n1)/2e , xd(n1)/2e+1 , . . . , xn2 , xn1 = y, por ser x e y no conectados, ocurre que
 y es adyacente a lo mas a xd(n1)/2e+1 , . . . , xn2 . Entonces deg(xn1 ) n 2 d(n 1)/2e
1 + 1 = n 2 d(n 1)/2e (n 1)/2 1. Por otro lado, por hipotesis deg(xn ) (n 1)/2,
resultando la contradiccion (n 1)/2 (n 1)/2 1.
3. Asumamos que G es conectado con n vertices y probemos que para cualquier biparticion de
V existe una arista de G que tiene extremos en clases distintas de la biparticion.
Sean {V1 , V2 } una biparticion de V , y a V1 , b V2 . Por la conectividad de G existe un
camino a = x0 , x1 , . . . , xn = b. Como a V1 , b V2 , en este camino existe el mas pequeno
ndice i tal que xi1 V1 , xi V2 con {xi1 , xi } A.
Asumamos ahora que G con n vertices tal que para cualquier biparticion de V existe una
arista de G que tiene extremos en clases distintas de la biparticion y probemos que G es
conectado.
Construimos inductivamente el grafo G como sigue:
Partimos de x0 V y particionamos V en V1 = {x0 } y V1 c . Por hipotesis existe x1 V1 c
talque {x0 , x1 } A, de tal forma que G|{x0 , x1 } es conectado.
Para i = 2, . . . , n 2 construimos particionamos V en Vi = {x0 , . . . , xi1 } y Vi c , con Vi es co-
nectado. Por hipotesis existe un vertice xi Vi c tal que {xj , xi } A para algun 0 j i1.
De tal manera que G|{x0 , . . . , xi } es conectado.
Despues de esto resulta que G es conectado.

4. Sea G un grafo no conectado, y v, w V . Probemos que v, w estan conectados en G.

Si G es no conectado, G se descompone en al menos dos componentes. Por otro lado:
Si v, w estan en diferentes componentes de G, entonces {v, w}
/ A, as {v, w} A, y
v, w estan conectados en G.

Si v, w estan en la misma componente de G, y z es cualquier vertice en otra componente

de G, entonces {v, z}, {z, w}
/ A. As {v, z}, {z, w} A por lo que v, z, w es un camino
en G que conecta v y w.
5. Probemos por induccion la proposicion n 2 : cualquier grafo acclico con n vertices tiene
a lo mas n 1 aristas.
Para n = 2, el conjunto de aristas puede ser {x0 , x1 } o . En ambos casos vale la afirmacion
del enunciado.
Asumamos que el enunciado es valido para n = 2, . . . , k y probemos que entonces es valido
para n = k + 1.
Sea G grafo acclico con k + 1 vertices. Tomemos x V con deg(x) = r, y x1 , . . . , xr los
vertices distintos adyacentes a x.
Definamos Vi como el conjunto de vertices de G, distintos de x, que conectan con xi . Ocurre
que Vi Vj = , para i 6= j, pues en caso contrario si y Vi y y Vj , entonces existen
caminos c1 y c2 que conectan xi con y y y con xj respectivamente, de tal manera que se
forma el ciclo x, xi , c1 , y, c2 , xj , x, lo que genera una contradiccion.
Consideremos los grafos Hi = (Vi , A|Vi ), i = 1, . . . , r. Notemos que cada Hi es acclico y con
|Vi | (k + 1) 1 = k vertices, y por la hipotesis de induccion con |Vi | P
1 aristas.
r
De la relacion entre P los Hi y G se obtiene que las aristas de G son i=1 |A|Vi | + r
P r r
i=1 (|Vi | 1) + r = i=1 |V i | = k = (k + 1) 1.
6. Sea G un grafo con n vertices de grados mayor que cero y n 1 aristas. Denotemos con x el
 numero de vertices de grado uno en G.

Si x = 0, todos los vertices tienen grado mayor o igual a dos, y por el lema de estrechon
de manos 2(n 1) = deg(x1 ) + + deg(xn ) 2n, lo cual es una contradiccion.
Si x = 1, sea x1 el unico vertice de grado uno. Por el lema de estrechon de manos
2(n 1) = 1 + deg(x2 ) + + deg(xn ) 1 + 2(n 1), lo cual es una contradiccion.
De lo anterior resulta que hay por lo menos dos vertices de grado uno.

Grafos eulerianos
Definicion 29 (Estructuras eulerianas)
Un sendero euleriano en un multigrafo G es un sendero que contiene todas las aristas de G.
Un tour euleriano en un multigrafo G es un sendero euleriano cerrado.
Un multigrafo se llama euleriano si el contiene un tour euleriano.
Teorema 1 (Teorema de Euler)
Sea G un multigrafo conectado. Las siguientes proposiciones son equivalentes:

1. G es euleriano.
2. Cada vertice de G tiene grado par.
3. El conjunto de aristas de G puede ser particionado en ciclos.
Corolario 1
Sea G un multigrafo conectado con exactamente 2k vertices de grado impar. G contiene un sendero
euleriano si y solo si k = 0 o k = 1.
Ejercicio 4
Si G es un multigrafo conectado con exactamente 2k vertices de grado impar y k 6= 0,
entonces el conjunto de aristas de G puede ser particionado en k senderos.
El grafo linea L(G) de un grafo G tiene como vertices las aristas de G; dos aristas de G son
adyacentes en L(G) si y solo si ellos tienen un vertice comun en G.
De una formula para el grado de un vertice de L(G), usando los grados en G.
Sea G un grafo conectado. Encuentre una condicion necesaria y suficiente para que L(G)
sea euleriano.

Grafos hamiltonianos
Definicion 30
Un ciclo en un grafo G se llama hamiltoniano, si el contiene todos los vertices de G.
Un grafo se llama hamiltoniano si el tiene un ciclo hamiltoniano.
Ejemplo 1
El grafo completo Kn es hamiltoniano.
Definicion 31 (Clausura de un grafo)
Sea G un grafo con n vertices. Llamamos clausura de G, denotado por [G], al grafo que se construye
progresivamente a partir de G, agregando una arista {u, v} en G cada vez que existan vertices u
y v no adyacentes con deg(u) + deg(v) n.
Teorema 2
Un grafo es hamiltoniano si y solo si su clausura es hamiltoniano.

Corolario 2
Sea G un grafo con n 3 vertices. Si para todo par de vertices no adyacentes u y v vale deg(u) +
deg(v) n, entonces G es hamiltoniano.
Corolario 3
Sea G un grafo con n 3 vertices. Si cada vertice de G tiene grado al menos n/2, entonces G es
hamiltoniano.
Ejercicio 5
1. Determine si el grafo dado puede particionarse en senderos eulerianos. En caso afirmativo
obtenga la particion usando el algoritmo de Fleury.

2. Cual es el mnimo numero de veces que hay que levantar el lapiz del papel para trazar los
siguientes dibujos sin repintar?

3. En la casa de la figura Es posible entrar y salir de tal manera que cada puerta se use
exactamente una vez?

4. Para que valores de n el grafo completo con bucles de n vertices es un grafo euleriano?
5. Un cartero sale de correos con las cartas, recorre las calles de su zona y vuelve a la central,
de tal manera que sea mnimia la distancia recorrida. Resuelva este problema si las calles
que debe recorrer son las representadas en los siguientes grafos:

6. Cuales de los siguientes grafos son hamiltonianos?

a) El grafo completo bipartito Kr,s
b) El grafo de Petersen
c) Los grafos del tetraedro, cubo y octaedro
7. Usa que un grafo bipartido con un numero impar de vertices no puede ser hamiltoniano, para
 demostrar que el siguiente grafo no puede ser hamiltoniano.

8. Elena y Dora invitan a 10 amigos a cenar. En el grupo de 12, todos conocen al menos a 6
personas. Demuestra que se pueden sentar los 12, alrededor de una mesa circular, de modo
que todos conozcan a las dos personas que estan sentadas a su lado.
9. Demuestra que en Kn , con n 3 e impar, hay (n 1)/2 ciclos con todas sus aristas distintas.
10. Siete personas que asisten a un congreso deberan comer juntas, en una mesa circular, los tres
das que dura el congreso. Para conocerse mejor deciden sentarse de modo que cada persona
tenga a cada lado a una persona distinta cada da. Pueden llevar a cabo su proposito? Y
si el congreso durara cinco das?
11. Sea G un grafo con n vertices y m aristas, y asuma que m (n 1)(n 2)/2 + 2. Pruebe
que G es hamiltoniano.
12. Pruebe que si G es euleriano, entonces L(G) es hamiltoniano. Es cierto el converso?
13. Determine el numero mnimo de aristas que debe tener un grafo G con seis vertices, si [G]
es el grafo completo K6 .

Grafos planares
Definicion 32 (Grafos isomorfos)
Dos grafos G = (V, A) y G0 = (V 0 , A0 ) se llaman isomorfos, si existe una biyeccion : V V 0
para la cual vale a, b A : {a, b} A {(a), (b)} A0 .
Ejercicio 6
Muestre que si un grafo G tiene una 1-factorizacion, entonces G tiene un numero par de vertices.

Solucion

Sea G = (V, A) un grafo con |V | = n. Si G tiene una 1-factorizacion, entonces existen subgrafos de
expansion de G, G1 = (V, A1 ), . . . , Gk = (V, Ak ), cada uno de ellos 1regular, tales que A1 , . . . Ak
forman una particion de A. Para cada Gi = (V, Ai ) vale el lema de estrechon de manos, por lo cual
n = 2|Ai |. Esto es n es par.

Muestre que Tn es (2n 4)-regular.

Dibuje los grafos Tn para n = 3, 4, 5, y muestre que Tn tiene parametros a = 2n 4, c = n 2 y
d = 4, donde a es el grado de cualquier vertice, c es el numero de vertices adyacentes a ambos x e
y, cuando x e y son adyacentes, y d es es el numero de vertices adyacentes a ambos x e y, cuando
x e y son no adyacentes.
Muestre que el grafo Kn es (n 1)-regular.

Solucion

Dado un subconjunto de dos elementos {i, j} con i 6= j, los subconjuntos de dos elementos que
tienen interseccion no vacia con el son:
{i, k}, para k satisfaciendo 1 k n y k 6= i, k 6= j.
{j, r}, para r satisfaciendo 1 r n y r 6= j, r 6= i.

De la cuenta de ellos obtenemos que el grado de cada vertice es 2n 4

Muestre que el grafo Km,n es n-regular, solo si m = n.

Dados un grafo G y su complemento G. Muestre que dos vertices de V son adyacentes en G si, y
solo si ellos no son adyacentes en G.