M3.Fundamentos de Ngrafos

Fundamentos de
grafos
PID_00267019
Joaquim Borges
Robert Clarisó
Ramon Masià
Jaume Pujol
Josep Rifà
Joan Vancells
Mercè Villanueva
Tiempo mínimo de dedicación recomendado: 5 horas

CC-BY-NC-ND • PID 00267019 Fundamentos de grafos
Joaquim Borges Robert Clarisó Ramon Masià Jaume Pujol
Josep Rifà Joan Vancells Mercè Villanueva
La revisión de este recurso de aprendizaje UOC ha sido coordinada por el profesor: Robert Clarisó (2019)
Cuarta edición: Septiembre 2019

Autoría: Joaquim Borges, Robert Clarisó, Ramon Masià, Jaume Pujol, Josep Rifà,
Joan Vancells, Mercè Villanueva
Licencia CC BY-SA de esta edición, FUOC, 2019
Av. Tibidabo, 39-43, 08035 Barcelona
Realización editorial: FUOC
Los textos e imágenes publicados en esta obra están sujetos –excepto que se indique lo contrario–
a una licencia de Reconocimiento-NoComercial-SinObraDerivada (BY-NC-ND) v.3.0 España
de Creative Commons. Podéis copiarlos, distribuirlos y transmitirlos públicamente siempre que
citéis el autor y la fuente (FUOC. Fundació per a la Universitat Oberta de Catalunya), no hagáis
un uso comercial y no hagáis una obra derivada. La licencia completa se puede consultar en
http://creativecommons.org/licenses/by-nc-nd/3.0/es/legalcode.es
Índice
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1. Caracterización de un grafo . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1. Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2. Vértices y aristas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3. Subestructuras de un grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4. Fórmula de los grados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5. Algunos grafos importantes . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5.1. Grafos elementales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.2. Los grafos bipartitos . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6. Secuencias gráficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.6.1. Algoritmo de Havel-Hakimi . . . . . . . . . . . . . . . . . . . 26
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2. Estructura y manipulación de grafos . . . . . . . . . . . . . . . 31

2.1. Transformar un grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2. Combinar dos o más grafos . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.3. Grafos isomorfos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.4. Extensiones del concepto de grafo (simple) . . . . . . . . . . 42
2.4.1. Multigrafos y pseudografos . . . . . . . . . . . . . . . . . . . . 42
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4.2. Grafos orientados o dirigidos . . . . . . . . . . . . . . . . . . 44
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.5. Representación y almacenamiento . . . . . . . . . . . . . . . . . . . 45
2.5.1. La matriz de adyacencias . . . . . . . . . . . . . . . . . . . . . . 45
2.5.2. La lista de adyacencias . . . . . . . . . . . . . . . . . . . . . . . . 48
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Ejercicios de autoevaluación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Bibliografı́a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
CC-BY-NC-ND • PID 00267019 5 Fundamentos de grafos
Introducción
Este módulo es una iniciación a la teorı́a de grafos, en la que se

presentan las definiciones básicas, se demuestran los primeros re-
sultados (entre los que se encuentra la fórmula de los grados), se
ven algunos grafos importantes, se analizan algunas operaciones
que pueden llevarse a cabo con grafos, se estudia el problema de la
existencia de un grafo y, finalmente, se trata el tema del almacena-
miento de grafos, problema de gran interés para la algorı́tmica y la
programación.
Es posible que esta disciplina os sea completamente nueva, dado

que los puntos de conexión con otras disciplinas matemáticas más
usuales son pocos. En todo caso, antes de iniciar su estudio, serı́a
conveniente repasar los contenidos elementales de la combinato-
ria, el cálculo matricial, las técnicas de demostración inductiva y,
naturalmente, tener cierta madurez matemática.
1. Caracterización de un grafo
.
En muchas situaciones, se establecen una serie de relaciones en- Grafo

tre diversos objetos; un grafo es la estructura constituida por estos
Un grafo está formado
objetos y las relaciones que pueden establecerse entre ellos. Los ob- por vértices (que pueden
jetos se denominan vértices y las relaciones, aristas. representar objetos) y
aristas (que pueden
representar las relaciones
Los grafos se pueden representar gráficamente en el plano. Uno de entre estos objetos).
los métodos más utilizados consiste en representar los vértices por
punto del plano y las relaciones que puedan establecerse entre estos
vértices mediante arcos de curva (aristas) que los unan (eventual-
mente segmentos de recta).
.
En esta representación gráfica, la posición de un vértice o la longi-

tud de una arista no son relevantes. Únicamente nos fijaremos en
qué vértices aparecen y si están conectados entre sı́ o no. Esto sig-
nifica que hay muchas formas diferentes de dibujar el mismo grafo.
Ası́ pues, una situación que involucre objetos, entre los cuales se
puede establecer algún tipo de interconexión, se puede describir
mediante un grafo: las comunicaciones, las reuniones, la fabrica-
ción de circuitos y la coloración de mapas.
1.1. Grafo
.. Notación
Definición 1 Si no se especifica lo
contrario, cuando
hablamos de grafos
Un grafo (simple) G = (V,A) es un par ordenado (V,A) donde haremos referencia
V es un conjunto finito no vacı́o, cuyos elementos son los siempre a grafos simples.
vértices, y A es un subconjunto del conjunto de parejas no
.
ordenadas (es decir, subconjunto de dos elementos diferentes)
de elementos de V; el conjunto A es el conjunto de aristas.
Ejemplo 1
Se considera el grafo que se representa de la manera siguiente.
.
v3 v2
v1
v4
En este caso es G = (V,A), donde el conjunto de vértices es V = {v1 ,v2 ,v3 ,v4 }
y el conjunto de aristas es A = {{v1 ,v2 },{v2 ,v3 },{v1 ,v3 },{v1 ,v4 }} Notación
Si a = {u,v} ∈ A, para
Fijaos en que, según esta definición, un vértice no puede estar re- simplificar la notación se
lacionado consigo mismo, ni puede haber más de una arista entre escribe también a = uv
o, de forma equivalente,
dos vértices concretos y los dos vértices conectados por una arista a = vu.
tienen la misma importancia. Este es el modelo de grafo simple.
Más adelante veremos familias de grafos más generales (dirigidos,
pseudografos, multigrafos) donde estas restricciones se relajan para
poder describir relaciones más complejas.
Ejercicios
1. Proponed un modelo en términos de teorı́a de grafos (y haced una repre-

sentación gráfica) de la situación que se describe a continuación. Se conside-
ran las siguientes personas de una clase: Juan, José, Jorge y Pablo. Jorge conoce
a Pablo, y Pablo, Juan y José se conocen mutuamente.
2. Proponed un modelo de grafos representativo de las comunicaciones por

carretera entre diversas ciudades y pueblos, y un segundo modelo representa-
tivo de la ausencia de comunicaciones por carretera (es decir, existe una arista
entre dos centros si, y sólo si, no están comunicados por una carretera); la
situación puede ser ficticia o real.
3. Considerad una empresa donde hay diversas personas, P1 ,P2 ,P3 , y una se-
rie de trabajos que se han de realizar, T1 , . . . ,T6 , con la posibilidad de que una
persona pueda hacer más de una tarea, según sus capacidades. Formulad (y
dibujad) un modelo en términos de teorı́a de grafos que recoja la situación de

individuos que pueden hacer diferentes tareas, y tareas que puedan ser reali-
zadas por diferentes individuos.
Soluciones
1. Un esquema posible serı́a el siguiente.
.
Pablo
Juan
Jorge
José
2. Realmente no hay “una” solución. Un posible esquema indicativo, ficticio

y trivial, podrı́a ser el siguiente (naturalmente, un modelo real es mucho más
complejo).
.
Sabadell
Rubı́
Barcelona
Terrassa
3. Un posible esquema es el del grafo siguiente. Éste corresponde a un tipo

de grafo importante, como se verá más adelante: el de los grafos bipartitos,
que se dan en muchas situaciones de este tipo de asignaciones de tareas. Las
personas y las tareas se indican con vértices de colores diferentes.
.
1.2. Vértices y aristas
..
Definición 2
Los vértices u,v ∈ V son adyacentes si, y sólo si, existe la

arista uv, es decir, si, y sólo si, {u,v} ∈ A. La adyacencia de los
vértices u, v se denota u ≈ v. En este caso se dice que la arista
a = uv une o conecta los vértices, que son sus extremos. Otras
denominaciones que indican que los vértices son adyacentes
pueden ser:
• Los vértices u, v y la arista uv son incidentes.

• Los vértices u y v son vértices vecinos.
Igualmente, se dice que dos aristas son adyacentes si compar-

ten un extremo.
Ejemplo 2
Se considera el grafo siguiente.
.
v1
a3
a1 v5 a2
a7 a8
v2 v6 v8 v4
a9 a10
a4 v7 a5
a6
v3
Los vértices v5 , v6 son adyacentes; no lo son los vértices v6 , v8 . Los vértices

v1 , v2 son los extremos de la arista a1 , que se describe como a1 = {v1 ,v2 } =
= v1 v2 = v2 v1 . Las aristas a4 , a5 , a6 son incidentes con v3 . Las aristas a2 , a5
son adyacentes.
Las propiedades y algoritmos que relacionan el número de vértices

y aristas de un grafo son muy importantes. Para enunciarlas son
necesarias algunas definiciones.
..
Definición 3
• Dado un grafo G = (V,A), el orden del grafo es el cardi-

nal del conjunto, es decir, el número de vértices del grafo.
Evidentemente se cumple que n = |V | ≥ 1.
• La medida del grafo es el cardinal del conjunto de aristas
o, en otros términos, el número de aristas del grafo. Puede
suceder que un grafo no tenga ninguna arista, de manera
que m = |A| ≥ 0.
No es difı́cil deducir la siguiente proposición.
.. Número
combinatórico
Proposición 1
Recordad
`n´ que el número
r se denomina

n n(n – 1) número combinatórico
0≤m≤ =
2 2 o binomial. Se puede
calcular
`n´ con la fórmula,
n!
.
r = r!(n–r)! `
El número nr nos indica
´
El número máximo de aristas se consigue teniendo una arista entre la cantidad de maneras
de seleccionar r
cada par de vértices del grafo.
elementos de un
conjunto que tiene n.
Alternativamente, el
Ejemplo 3
número nr indica la
` ´
cantidad de r-muestras
Un grafo con diez vértices puede tener un máximo de 102·9 = 45 aristas:
no ordenadas sin
cada uno de los vértices está conectado con los nueve vértices restantes, y
repetición que se
es necesario recordar que aunque una arista conecta dos vértices sólo se ha
pueden construir en un
de contabilizar una única vez.
conjunto de n
elementos.
..
Definición 4
Dado un vértice v ∈ V del grafo G = (V,A) se define el grado

g(v) del vértice v como el número de aristas que son incidentes
al vértice; de acuerdo con nuestra definición de grafo, el grado
coincide con el número de vértices que le son adyacentes, en
otros términos
g(v) = |{u ∈ V | v ≈ u}| = |{u ∈ V | {u,v} ∈ A}|
Los vértices de grado cero se denominan vértices aislados.
Ejemplo 4
Consideremos un grupo de personas que se encuentran en una reunión.

Mientras van entrando, algunas de estas personas se saludan. Podemos
formular un grafo que describa esta situación: los vértices serán los asis-
tentes a la reunión y las aristas representarán los saludos mutuos. De esta
manera, el grado de cada vértice es el número de personas que ha saluda-
do. Es posible que haya personas que no saluden a nadie, cuyo grado será,
evidentemente, 0.
Resulta evidente que:
..
Proposición 2
0 ≤ g(v) ≤ |V | – 1, ∀v ∈ V
Este resultado se puede utilizar para descartar la existencia de grafos

con una secuencia de grados concreta.
Ejemplo 5
Se observa que no puede existir ningún grafo con la secuencia de grados

2,2,2,3,3,4,8. En efecto, si existiese dicho grafo G = (V,A), se cumplirı́a que
|V | = 7 y, si hubiese un vértice v0 de grado 8, en virtud de la desigualdad
anterior, |V | ≥ g(v0 ) + 1 ≥ 8 + 1 = 9, cosa que es imposible.
A partir del grado de los vértices de un grafo, puede definirse el

grafo regular:
..
Definición 5
Un grafo es regular si todos los vértices son del mismo gra-

do; si el grado común es r, entonces se dice que el grafo es
r-regular.
Ejemplo 6
A continuación se presentan diversos ejemplos de grafos regulares.
El primer grafo es 1-regular y el resto son 3-regulares.

Ejercicios
4. Considerad el grafo del esquema adjunto. Describid formalmente el con-

junto de vértices y de aristas.
.
v3 v2
v4
v1
5. Representad gráficamente un grafo de vértices V = {v1 , v2 , v3 , v4 , v5 } y

conjunto de aristas A = {{v1 ,v2 },{v1 ,v4 },{v1 ,v5 },{v2 ,v3 },{v3 ,v5 },{v3 ,v4 }}. Hacer
diversas representaciones.
6. Un grafo 4-regular es como mı́nimo de orden 5. ¿Es esto cierto?
7. ¿Qué grafos son 0-regulares?
8. ¿Qué medidas son posibles, para los grafos de orden 3?
Soluciones
4. Es el grafo G = (V,A), con V = {v1 ,v2 ,v3 ,v4 } y A = {{v1 ,v2 }, {v2 ,v3 }, {v1 ,v3 },
{v1 ,v4 }}.
5. A continuación se presentan diversas soluciones.
.
v1
v1 v2 v3
v4 v2 v5
v4 v5 v3
v2
v1 v4 v3
v5
6. Cierto, ya que |V | ≥ g(v) + 1 ≥ 4 + 1 ≥ 5. En general, si un grafo es r-regular,

ha de ser de orden como mı́nimo r + 1.
7. Los grafos 0-regulares son los grafos sin aristas.
`3´
8. Por la proposición 1 tenemos que 0 ≤ |A| ≤ 2 = 3. Por lo tanto, las
posibles medidas son: 0,1,2,3.
1.3. Subestructuras de un grafo
..
Definición 6
Dado un grafo G = (V,A), un subgrafo de G es un grafo H =

(V ′ ,A′ ) en el que V ′ ⊆ V,A′ ⊆ A, de manera que las aristas del
subgrafo unen vértices del subgrafo.
Ası́, el nuevo conjunto de vértices es un subconjunto del original, y

análogamente para las aristas. Esto significa que, si dos vértices son
adyacentes en H, entonces también lo son mediante una arista per-
sistente en G y, por lo tanto, también son adyacentes en G. En otros
términos, si dos vértices de H no son adyacentes en G, tampoco lo
son en H, pero es posible que dos vértices de H sean adyacentes en
G, y no lo sean en H.
..
Definición 7
• Dado un grafo G = (V,A), se considera un subconjunto

S ⊆ V; se define el subgrafo generado o inducido por
S en G como el grafo hSi = (S,A′ ), de tal manera que
{u,v} ∈ A′ ⇔ {u,v} ∈ A y u,v ∈ S. Ası́, el conjunto de las
aristas de hSi son las que, siendo de G, conectan vértices
de S.
• Sean G = (V,A) y H = (V ′ ,A′ ) dos grafos; se dice que H
es subgrafo generador o de expansión de G si V ′ = V y
A′ ⊆ A.
El grado de un vértice u relativo a un subgrafo H se escribe gH (u).
Ejemplo 7
Considerad el grafo representado en la figura siguiente.

.
1
2 5
3 4
Un ejemplo de subgrafo puede ser el siguiente: H = (V ′ ,A′ ), V ′ = {1,2,4,5},

A′ = {{2,4},{4,5}}. El grado del vértice 4 en el grafo G es 4 y, en cambio, en
el subgrafo H el mismo vértice tiene grado 2.
Un subgrafo generador serı́a, por ejemplo, H = {{1,2,3,4,5},{{3,4},{2,4}}}.
El subgrafo generado por el conjunto de vértices S = {2,3,4,5} es el grafo

cuyo conjunto de vértices es S y el conjunto de aristas es A′ = {{2,3},{3,4},
{2,4},{3,5}, {4,5}}.
1.4. Fórmula de los grados
..
Fórmula de los grados. Teorema 3
Dado un grafo G = (V,A), se cumple que

X
g(v) = 2|A|
v∈V
es decir, la suma de los grados de un grafo es el doble del

número de aristas.
Demostración: Tan solo es necesario contar el número de aristas del grafo a

partir de las aristas que aporta cada vértice. Cada vértice v aporta al cómputo
global de aristas la cantidad de g(v) aristas (cantidad que iguala el P grado del
vértice), de manera que globalmente el número de aristas serı́a v∈V g(v) si
cada arista no fuese compartida por los dos vértices extremos y, en P conse-
cuencia, cada arista es contada dos veces. PorPlo tanto, la expresión v∈V g(v)
cuenta el doble del número de aristas, o sea, v∈V g(v) = 2|A|.
Ejemplo 8
Se considera un grafo con secuencia de grados 2,2,2,2,2,2,3,1. Se puede

calcular fácilmente el número de aristas del grafo sin otra información, y
aplicando la fórmula de los grados:
1X 1
|A| = g(v) = (2 + 2 + 2 + 2 + 2 + 2 + 3 + 1) = 8.
2 2
v∈V
Con mucha frecuencia, la fórmula de los grados se utiliza en la

resolución de problemas de teorı́a de grafos. También se utiliza un
resultado que es muy fácil de demostrar a partir del lema.
..
Proposición 4
En un grafo cualquiera G = (V,A), el número de vértices de

grado impar es par.
Demostración: En efecto, sea P el conjunto de vértices de grado par y S

el conjunto de vértices de grado impar, de manera que se tiene la partición
V = P ∪ S. En consecuencia, se puede escribir a partir de la fórmula de los
grados:
X X X X X X
2|A| = g(v) = g(v) = g(v) + g(v) = 2kv + (2kv + 1).
v∈V v∈P∪S v∈P v∈S v∈P v∈S
Esto se debe a que los números pares son de la forma 2k y los números impares,
de la forma 2k + 1, para un k adecuado, dependiendo del número.
Entonces, a partir de las fórmulas anteriores, se puede escribir

! !
X X X X X
2|A| = 2 kv + kv + 1=2 kv + kv + |S|,
v∈P v∈S v∈S v∈P v∈S
de donde resulta que el cardinal del conjunto de vértices de grado impar puede
escribirse como la diferencia de dos números pares y, en consecuencia, es par:
!
X X
|S| = 2|A| – 2 kv + kv .
v∈P v∈S
Ejemplo 9
No puede existir ningún grafo con esta secuencia de grados: 1,3,3,2,2,2,4.

En efecto, si existiese, habrı́a un número impar de vértices de grado impar,
cosa que contradirı́a la proposición 4, consecuencia de la fórmula de los
grados.
Ejemplo 10
En una reunión, el número de las personas que saludan a un número impar

de personas ha de ser par; es una consecuencia directa de la proposición 4.
Se supone que el saludo es mutuo (esto se garantiza en el caso de los apre-
tones de manos).
Ejemplo 11
En una clase, el número de alumnos que conocen a un número impar de

alumnos (con conocimiento mutuo) es par.
Ejercicios
9. En una reunión de ocho personas se producen algunos saludos entre los

asistentes. Se supone que dos personas saluden a otras tres, otra persona no
salude a nadie, dos personas saluden sólo a una, una persona salude a cuatro,
y dos personas saluden a dos. ¿Cuántos saludos se producirı́an?
10. Un asistente a una reunión da la siguiente descripción de ésta: habı́a

seis personas; una no conocı́a a nadie y tampoco saludó a nadie; cada una de
las personas restantes saludó a tres asistentes. ¿Puede ser correcta esta descrip-
ción?
11. ¿Pueden existir grafos G = (V,A) r-regulares con r impar, de orden |V |

impar?
12. En un grafo 2-regular, el número de aristas y de vértices coinciden. ¿Es

esto posible?
13. Un grafo con catorce aristas, tres vértices de grado 1, dos vértices de
grado 4, un vértice de grado 3 y el resto de grado 2 ha de tener exactamente
trece vértices. ¿Es esto cierto?
Soluciones
9. Aplicando la fórmula de los grados, podemos ver que se producirı́an 8

saludos.
10. La descripción no puede ser cierta, ya que si ası́ lo fuera, el grafo corres-
pondiente a la reunión tendrı́a secuencia de grados 0, 3, 3, 3, 3, 3, es decir,
habrı́a un número impar de vértices de grado impar, en contradicción con la
proposición 4, consecuencia de la fórmula de los grados.
11. Se aplica la fórmula de los grados: 2|A| =

P
v∈V g(v) = r |V |. Se observa
claramente una contradicción, ya que el término de la izquierda es par, mien-
tras que el de la derecha es impar, de acuerdo con las hipótesis. Por lo tanto,
no puede existir ningún grafo de estas caracterı́sticas.
12.
P Es cierto, P ya que, por la fórmula de los grados se puede escribir 2|A| =
v∈V g(v) = v∈V 2 = 2|V |, de donde resulta que |A| = |V |.
13. Se comprobará la veracidad de la afirmación aplicando la fórmula de los

grados, suponiendo que el número de vértices de grado 2 es x. En efecto, se
puede escribir 3 + 2 × 4 + 1 × 3 + 2x = 2|A| = 28, de donde x = 7. Por lo tanto, el
número de vértices es 13.
1.5. Algunos grafos importantes
1.5.1. Grafos elementales
Es necesario conocer alguno de los tipos de grafos más importantes.

Los más elementales son:
..
Definición 8
• El grafo nulo Nn de orden n ≥ 1 es el grafo de n vértices y

0 aristas; de manera que Nn = (V,∅), con |V | = n. El grafo N1
se denomina grafo trivial. El orden del grafo nulo Nn es n
y la medida 0. Es el más simple de todos los grafos.
• El grafo ciclo de orden n ≥ 3 es Cn = (V,A), don-
de V = {v1 , . . . ,vn } y A = {{v1 ,v2 },{v2 ,v3 }, . . . ,{vn ,v1 }} =
= {{vi ,vi+1 } | i = 1, . . . ,n – 1} ∪ {{vn ,v1 }}.
• El grafo trayecto Tn = (V,A) de orden n ≥ 2 es el grafo para
el que V = {v1 , . . . ,vn } y A = {{v1 ,v2 },{v2 ,v3 }, . . . ,{vn–1 ,vn }} =
= {{vi ,vi+1 } | i = 1, . . . ,n – 1}. El grafo Tn se puede obtener de
la eliminación de una arista del grafo ciclo Cn ; si, en cam-
bio, se añade una arista a Tn que conecte el primer vértice
y el último se obtiene el ciclo Cn .
• El grafo completo de orden n es el grafo de n vértices con
todas las aristas posibles; es decir, Kn = (V,A), con |V | = n y
|A| = n2 = 21 n(n – 1).

Ejemplo 12
Se puede ver en esta figura los grafos ciclo C3 , C4 , C5 . El último grafo es T5 .
Ejemplo 13
En las figuras que hay a continuación se puede observar algunas represen-

taciones de los grafos completos K3 , K4 , K5 . Observar que K3 = C3 .
.
Ejercicios
14. ¿Qué grafos ciclos son grafos completos?
15. Los únicos grafos 2-regulares son los ciclos Cn . ¿Es esto cierto?
16. ¿Hay grafos r-regulares para todo r?
17. ¿Cuál es la medida máxima de un grafo de orden 14? ¿Cómo se denomi-

na este grafo?
18. ¿Podéis dar un ejemplo de un grafo tal que cada vértice sea incidente
con cada arista?
Soluciones
14. Únicamente el grafo C3 = K3 .
15. Falso, como se puede ver en el contraejemplo siguiente (grafo de 6 vértices

y 6 aristas, que no es ciclo):
16. Sı́, puesto que el grafo completo Kr+1 es r-regular.
`14´
17. La medida máxima es |A| = 2 = 91 y corresponde al grafo completo K14 .
18. Por ejemplo, el grafo trayecto, T2 .
1.5.2. Los grafos bipartitos
Los grafos bipartitos merecen una atención especial.
..
Definición 9
Un grafo G = (V,A) es bipartito si existe una partición del

conjunto de vértices, es decir si V = V1 ∪ V2 , con V1 ∩ V2 = ∅,
.
de manera que las aristas existentes sólo conectan vértices de
V1 con vértices de V2 : es decir, {u,v} ∈ A implica que u ∈ V1 ,
v ∈ V2 o v ∈ V1 , u ∈ V2 . De manera equivalente, si {u,v} ∈ A,
u ∈ V1 ⇔ v ∈ V2 .
En particular, esto significa que no hay aristas que conecten vértices

de V1 ni aristas que conecten vértices de V2 .
Ejemplo 14
Este gráfico es un ejemplo de grafo bipartito. Se han indicado con colores

diferentes los vértices de cada bipartición.
La idea se puede generalizar a los grafos k-partidos. En este caso se

tiene una partición (V1 , . . . ,Vk ) del conjunto de vértices, de manera
que las aristas que hay conectan vértices que pertenecen a conjun-
tos diferentes de la partición y no hay aristas conectando vértices
de un mismo conjunto Vi .
..
Definición 10
El grafo bipartito completo Kn,m es un grafo G = (V,A) que

es bipartito, siendo |V1 | = n, |V2 | = m, con todas las aristas
posibles conectando vértices de V1 con vértices de V2 .
Esto significa en particular que todos los vértices de V1 son adya-

centes a todos los vértices de V2 . En otras palabras, A = {{u,v} | u ∈
V1 , v ∈ V2 }. El orden del grafo es |V | = n+m y su medida es |A| = nm.
Los vértices de V1 son todos de grado m y los de V2 son de grado n.
Los grafos bipartitos completos Km,m son m-regulares.
Ejemplo 15
Se indican en colores diferentes los vértices de la bipartición, de manera

que se tiene V1 = {v1 ,v2 ,v3 } y V2 {v4 ,v5 ,v6 }.
.
v6 v5 v4
v3 v2 v1
Estas figuras son representaciones de K3,3 , K4,4 (de izquierda a derecha).
..
Definición 11
En el caso de un grafo k-partido completo se tiene una parti-

ción del conjunto de vértices en k subconjuntos, de cardina-
les respectivos n1 ,n2 , . . . ,nk , y existen todas las aristas posibles,
con la condición de que no haya ninguna arista que conecte
vértices de un mismo subconjunto. El grafo correspondiente
se representa por Kn1 ,...,nk .
Ejemplo 16
La ilustración corresponde al grafo K3,4,2 .
.
..
Definición 12
El grafo estrella En de orden n (n ≥ 3) es un caso particular de

grafo bipartito completo, En = K1,n–1 .
El orden del grafo es n y la medida, n – 1.
Ejemplo 17
Este gráfico corresponde a E10 = K1,9 .
..
Definición 13
El grafo rueda Rn de orden n (n ≥ 4) tiene un único vértice de

grado n – 1 y, si se elimina este vértice y sus aristas incidentes,
se obtiene un ciclo de orden n – 1.
El orden del grafo rueda es n y su medida es 2(n – 1).
Ejemplo 18
Este es el grafo rueda de orden 15: R15 .
.
Ejercicios
19. Estudiad si el grafo siguiente es bipartito y, en caso afirmativo, repre-

sentadlo “en forma bipartida”, es decir, en forma que deje ver claramente la
estructura bipartida.
20. Considerad el grafo siguiente, probad que es bipartito y dibujadlo en

forma bipartida.
21. Considerad un grafo k-partido completo o, más concretamente conside-

rad un (n1 , . . . ,nk )-partido completo. ¿Cuál es el orden y la medida del grafo, y
cuáles son los grados de los diferentes vértices? ¿Para qué valores es regular el
grafo?
22. ¿Son bipartitos los grafos ciclo Cn ?
23. Los grafos trayecto, ¿son todos bipartitos?
24. Indicad algún grafo completo Kn que sea bipartito.
25. El grafo trayecto T3 es un caso especial de grafo estrella. ¿Cierto o falso?
26. Buscad un recorrido cerrado sobre el grafo rueda que visite todos los
vértices exactamente una vez.
Soluciones
19. El grafo es efectivamente bipartito, como se puede ver si se asignan dos

colores diferentes a los vértices, de manera que no haya vértices del mismo co-
lor adyacentes (ésta es una manera fácil de comprobar si un grafo es o no
bipartito); entonces las dos clases de la bipartición son los subconjuntos de
vértices del mismo color. Asignando etiquetas a los vértices, también se puede
ver una representación que muestra claramente la estructura bipartida.
.
2 1
6 5 3 6 1 8
7 8
3 4 2 7 5 4
20. Se propone la distribución bipartida de los vértices, que se pone de ma-

nifiesto en la bicoloración del esquema siguiente:
21. El orden del grafo es n = n1 + n2 + · · · + nk . La medida del grafo es
1
(n (n – n1 ) + n2 (n – n2 ) + . . . + nk (n – nk )).
2 1
El grafo es regular si ni = nk , es decir, cuando todas las ni son iguales. Por lo

tanto, el orden del grafo tiene que ser divisible por k.
22. Depende de la paridad de n (con esta indicación podéis completar la res-

puesta).
23. Cierto (acabar de justificar la respuesta).
24. El grafo K2 es bipartito. Para n > 2, los grafos Kn no lo son.
25. Cierto, puesto que T3 = E3 = K1,2 .

26.
1.6. Secuencias gráficas
Uno de los primeros problemas que se puede plantear es si, dada

una secuencia de números enteros, es posible construir un grafo
que la tenga como secuencia de grados. A partir de la fórmula de
los grados, es fácil darse cuenta de que esto no siempre es posible.
..
Definición 14
Una secuencia de números enteros no negativos, s : d1 ,

d2 , . . . ,dn se denomina secuencia gráfica si existe un grafo
G = (V,A) de orden n tal que s es la secuencia de grados de G.
Ejemplo 19
La secuencia s : 4,3,2,2,1 es una secuencia gráfica. Corresponde al grafo

siguiente.
Ejemplo 20
La secuencia s : 4,3,3,2,1 no es una secuencia gráfica, puesto que no cumple

la proposición 4, consecuencia de la fórmula de los grados.
De la definición de grado de un vértice y de la fórmula de los gra-

dos, se pueden establecer dos condiciones necesarias para la exis-
tencia de un grafo dada una secuencia de enteros no negativos
s : d1 ,d2 , . . . ,dn :
1) di ≤ n – 1, por 1 ≤ i ≤ n.
2) ni=1 di tiene que ser par.
P
Ahora bien, estas condiciones no son suficientes.
Ejemplo 21
La secuencia s : 4,4,4,2,1,1 tendrı́a que corresponder a un grafo de orden 6.

Cumple las dos condiciones anteriores. En cambio, no hay ningún grafo
que tenga esta secuencia de grados. Esto demuestra que las condiciones
anteriores son necesarias pero no suficientes.
..
Caracterización de Havel-Hakimi. Teorema 5
Una secuencia s : d1 ,d2 , . . . ,dn de números enteros no negati-

vos, con d1 ≥ d2 ≥ . . . ≥ dn , es una secuencia gráfica si, y sólo
si, la secuencia d2 – 1,d3 – 1, . . . ,dd1 +1 – 1,dd1 +2 , . . . ,dn es gráfica.
Demostración: Podéis ver la obra de Gimbert, Moreno, Ribó y Valls (1998).
Ejemplo 22
Según esta caracterización, la secuencia del ejemplo s : 4,4,4,2,1,1, será

gráfica si lo es la secuencia que resulta de eliminar el primer término (4)
y restar 1 a los cuatro siguientes. Por lo tanto, la secuencia s : 4,4,4,2,1,1
se transforma en s′ : 3,3,1,0,1. Debemos establecer ahora si s′ es gráfica,
es decir, reordenando, si s′ : 3,3,1,1,0 es gráfica. El primer término es 3,
por lo tanto, debemos restar 1 a los tres siguientes términos; la secuencia
resultante es s′′ : 2,0,0,0. Pero esta secuencia no se corresponde con ninún
grafo, y por ello ni s′′ , ni s′ ni, tampoco, la secuencia s son gráficas.
1.6.1. Algoritmo de Havel-Hakimi
El teorema de Havel-Hakimi permite, de manera recursiva, recono-

cer si una secuencia es gráfica.
Formulación del algoritmo de Havel-Hakimi
Entrada: una secuencia de números enteros s : d1 ,d2 , . . . ,dn
Salida: dice si la secuencia es gráfica.

Algoritmo:
Si existe di > n – 1, entonces la secuencia no es gráfica, fin.

mientras no haya ningún di < 0 y s no sea idénticamente 0.
Clasificar s en orden decreciente.
Eliminar d1 de s y restar 1 unidad a los d1 elementos siguientes.
finmientras
Si existe di < 0, entonces la secuencia no es gráfica, fin.
Si la secuencia resultante es la secuencia idénticamente 0,
entonces s es una secuencia gráfica.
Implementación del algoritmo de Havel-Hakimi
Para implementar el algoritmo se observa que en cada iteración la

longitud de la secuencia disminuye en una unidad. La secuencia
será gráfica si tras n – 1 iteraciones se obtiene solamente un 0.
algoritmo Havel-Hakimi (s)

inicio
grafica ← FALSO
clasificar descendente (s)
si (max(s) ≤ n – 1) entonces
para i ← 1 hasta n – 1
pivote ← d1
s ← s– < d1 >
para j ← 1 hasta pivote
dj ← dj – 1
finpara
si (pivote < LONGITUD(s))
entonces intercalar descendente (s,pivote)
finsi
finpara
si (s = 0)
entonces grafica ← CIERTO
finsi
finsi
retorno (grafica)
fin
Se observa que,
1) La función clasificar descendente(s) ordena s en orden descenden-

te.
2) La función intercalar descendente(s,d1 ) ordena s fusionando dos
subsecuencias ya ordenadas. Como las dos subsecuencias que
forman s ya están ordenadas, se trata de intercalarlas.
3) Tras n – 1 iteraciones la secuencia contendrá un solo elemento.
Ejemplo 23
La tabla siguiente muestra la simulación del algoritmo para la secuencia

s : 2,2,4,3,3,2,3,5.
Iteración Secuencia Operación

Inicialmente 2,2,4,3,3,2,3,5
5,4,3,3,3,2,2,2 Clasificación
1 3,2,2,2,1,2,2 Primera subsecuencia
3,2,2,2,2,2,1 Se intercalan subsecuencias
2 1,1,1,2,2,1 Segunda subsecuencia
2,2,1,1,1,1 Se intercalan subsecuencias
3 1,0,1,1,1 Tercera subsecuencia
1,1,1,1,0 Se intercalan subsecuencias
4 0,1,1,0 Cuarta subsecuencia
1,1,0,0 Se intercalan subsecuencias
5 0,0,0 Quinta subsecuencia
Fin
Por lo tanto, la secuencia es gráfica. Un grafo que tiene esta secuencia de

grados es:
Análisis del algoritmo de Havel-Hakimi
Para analizar este algoritmo, hay que observar que en cada iteración
del bucle la longitud de la secuencia disminuye en una unidad. El
número total de iteraciones será n – 1.
Las principales operaciones que se hacen son:
1) Clasificar la secuencia en orden descendente. Esto se puede hacer

con los algoritmos clásicos de ordenación como el quick sort o el
merge sort con una complejidad O(n log n).
2) En el cuerpo del bucle se hacen dos tipos de operaciones:
– Restar una unidad d1 (d1 ≤ n – 1) veces.

– Intercalar dos subsecuencias.
Aunque normalmente no se hará una intercalación en cada ite-

ración, se puede suponer el peor de los casos. Es decir, en cada
iteración se restan k–1 unidades (k es la longitud de la subsecuen-
cia) y se realiza una intercalación. Las intercalaciones se pueden
hacer con una complejidad lineal, O(n) y el número de restas
será
1
(n – 1) + (n – 2) + . . . + 2 + 1 = n(n – 1)
2
que da una complejidad O(n2 ).
Resumiendo, se puede concluir que este algoritmo tiene, en el peor

de los casos, una complejidad O(n2 ).
Ejercicios
27. Usando el algoritmo de Havel-Hakimi, decidid si las secuencias siguien-

tes son gráficas.
a) s : 5,5,7,6,4,2,4,5
b) s : 2,3,4,5,6,7,8,8,8,8,8,8,8,8,8,8
c) s : 2,3,4,5,6,7,8,8,8,8,8,8,8,8,8,9
28. ¿Puede pasar que grafos con estructuras diferentes tengan la misma se-
cuencia de grados?
29. Demostrad que la secuencia de números enteros 2,2,2,2,2,2,3,1 es la se-

cuencia de grados de un grafo. Proponed dos ejemplos diferentes de grafos
que tengan esta secuencia de grados.
Soluciones
27. a) Sı́ que es gráfica:
Iteración Secuencia Operación

Inicialmente 5,5,7,6,4,2,4,5
7,6,5,5,5,4,4,2 Clasificación
1 5,4,4,4,3,3,1 Primera subsecuencia
2 3,3,3,2,2,1 Segunda subsecuencia
3 2,2,1,2,1 Tercera subsecuencia
2,2,2,1,1 Se intercalan subsecuencias
4 1,1,1,1 Cuarta subsecuencia
5 0,1,1 Quinta subsecuencia
1,1,0 Se intercalan subsecuencias
6 0,0 Sexta subsecuencia
7 0 Séptima subsecuencia
Fin
b) No es gráfica (aplicad el algoritmo para obtener este resultado).

c) Esta sı́ que es una secuencia gráfica (aplicad el algoritmo para obtener este
resultado).
28. Sı́; por ejemplo, considerad un grafo ciclo y el grafo constituido por la
reunión de 2 ciclos.
29. Se aplicarı́a el algoritmo de Havel-Hakimi para demostrar que la secuencia

es gráfica. Dos posibles grafos que tienen esta secuencia de grados son:
.
2. Estructura y manipulación de grafos

.
Muy a menudo es interesante conocer el conjunto de grafos iso-

morfos entre sı́, que son grafos que tienen esencialmente la misma
estructura. También es útil conocer modelos de grafos más gene-
rales que los que se han presentado hasta ahora, y que surgen de
manera natural; es el caso de los multigrafos y pseudografos, y tam-
bién de los grafos orientados.
Por otro lado, es conveniente disponer de herramientas que per-

mitan manipular grafos, básicamente con el fin de transformar un
grafo o de combinar dos o más. Finalmente, se estudiará uno de los
grandes problemas prácticos: la representación y el almacenamien-
to de un grafo en términos de estructuras de datos.
2.1. Transformar un grafo
Dado un grafo G = (V,A) se pueden realizar manipulaciones di-

versas:
1) Eliminar un vértice u ∈ V. Ası́ se obtiene el grafo G′ = G – u,

que es el grafo (V ′ ,A′ ), donde V ′ = V \{u} y A′ es el conjunto de
aristas de G no incidentes con u. Esta operación se puede generalizar
trivialmente a un conjunto W ⊆ V: G′ = G – W = (V \W,{{a,b} |
a,b 6∈ W }). Esta operación sólo tiene sentido si el grafo no es el
trivial.
2) Eliminar la arista a ∈ A. Ası́ se obtiene un grafo, con los mismos
vértices, definido por G′ = G – a = (V,A\{a}). La operación se puede
generalizar trivialmente a un subconjunto de aristas B ⊆ A, en cuyo
caso G – B = (V,A\B).
3) Añadir los vértices de un conjunto W tal que W ∩ V = ∅. Ası́ se
obtiene un nuevo grafo definido por G′ = G + W = (V ∪ W,A); en el
caso particular de un vértice, la notación se simplifica y se sustituye
por G+u. Como se verá, esta operación se puede definir en términos
de unión con el grafo nulo. Con la adición de vértices no se añaden
aristas nuevas.
4) Añadir una arista {u,v}, siendo u y v dos vértices no adyacentes.
Ası́ se obtiene el grafo G′ = (V,A∪{{u,v}}). Este nuevo grafo se puede
representar por G + uv. El proceso se puede generalizar a conjuntos
de más de una arista.
La condición de no adyacencia de los vértices es fundamental, pu-

esto que de lo contrario se crearı́a una arista múltiple y, por lo tanto,
no se estarı́a en el dominio de los grafos simples, tal y como se ha
definido.
Ejemplo 24
Sobre el primer grafo se efectúan operaciones de eliminación de vértices y

aristas, y de adición de aristas. El cuarto grafo es el resultado de eliminar
del original el vértice 2. El segundo grafo resulta de eliminar la arista {1,2}
y el tercer grafo se genera con la adición de la nueva arista {3,4}.
.
1 2
1 4
3 6
2 5
3 4
5) Hacer la contracción de la arista a = {u,v}. En este caso se eli-

mina la arista a, se identifican en un único nuevo vértice w los dos
vértices extremos u, v, que desaparecen y, finalmente, el vértice w
hereda exclusivamente las adyacencias de los vértices u, v.
La operación de contracción se puede aplicar a todo un conjunto

de aristas.
Ejemplo 25
Observad en esta figura el resultado de hacer la contracción de una arista
del grafo de la izquierda:
.
Ejemplo 26
Observad las figuras siguientes, que presentan la contracción de algunas
aristas del denominado grafo de Petersen, de manera que se deriva el grafo
completo K5 (en la segunda ilustración se marcan las aristas que se con-
traen):
◦ ◦
◦ ◦
6) Subdivisión elemental de la arista a = {u,v}. En este caso se in-

serta un vértice de grado 2; es decir, dado w 6∈ V, se realizan las
operaciones siguientes: eliminación de la arista a, adición del nue-
vo vértice w y adición de las nuevas aristas {u,w} y {w,v}. También
se puede describir como G – a + w + uw + wv.
Ejemplo 27
Observad el resultado una operación de subdivisión elemental en una aris-
ta del grafo K3,3 .
..
Definición 15
Dado el grafo G = (V,A), se define el complementario de este

grafo, Gc , como el grafo que se construye sobre el mismo con-
junto de vértices, de tal modo que dos vértices son adyacentes
en Gc si, y sólo si, no lo son en G.
Naturalmente, se cumple que el complementario del complemen-

tario es el original: (Gc )c = G.
Ejemplo 28
La figura siguiente muestra el grafo C5 y su complementario (que vuelve a

ser C5 ).
Y ésta, K4 y su complementario, N4 .
Ejercicios
30. ¿Cuál es el orden y la medida del grafo complementario Gc en términos

del orden n y la medida m del grafo original?
31. Si G es un grafo de orden n con secuencia de grados g1 ,g2 , . . . ,gn , ¿cuál

será la secuencia de grados de su complementario, Gc ?
32. Hay veces en las que es necesario estudiar si existen grafos con una de-
terminada secuencia de grados. Un procedimiento que se puede aplicar es
considerar la secuencia de grados que tendrı́an los grafos complementarios, si
hubiera algún grafo con la secuencia de grados dada. Proponer algún ejemplo
donde este procedimiento no aportarı́a nada nuevo, es decir, donde la secu-
encia de grados del grafo complementario es la misma que la dada.
33. El complementario de un grafo regular, ¿es regular? ¿Se puede afirmar

que un grafo es regular si, y sólo si, lo es el complementario?
Soluciones
`n´
30. El orden es el mismo y la medida es 2 – m.
31. La secuencia será, n – 1 – g1 ,n – 1 – g2 , . . . ,n – 1 – gn .
32. Un grafo con secuencia de grados 2, 2, 2, 2, 2 tiene como complementario

un grafo con secuencia 2, 2, 2, 2, 2.
33. Sı́ (acabad de justificar la respuesta).

2.2. Combinar dos o más grafos
Las operaciones que se presentan a continuación se generalizan

fácilmente a más de dos grafos.
..
Definición 16
Dados los grafos G1 = (V1 ,A1), G2 = (V2 ,A2 ), su unión es:
G1 ∪ G2 = (V1 ∪ V2 ,A1 ∪ A2 )
Ejemplo 29
Si G es un grafo de orden n, entonces G ∪ Gc = Kn .
Ejemplo 30
El grafo siguiente se puede describir como K2 ∪ K2 ∪ K2 ∪ K2 .
Ejemplo 31
El grafo siguiente se puede describir como G = C3 ∪ C3 .
..
Definición 17
Dados los grafos G1 = (V1 ,A1 ), G2 = (V2 ,A2 ), su suma es el

grafo que tiene los vértices y las aristas de los grafos originales,
.
más las aristas que conecten todos los vértices del primero con
todos los vértices del segundo:
G1 + G2 = (V1 ∪ V2 ,(A1 ∪ A2 ∪ {{u,v} | u ∈ V1 , v ∈ V2 }))
Ejemplo 32
En el gráfico siguiente se puede ver la suma del 3-ciclo (en negro) con el
2-trayecto (en blanco):
Ejemplo 33
Los grafos rueda y estrella se pueden expresar como grafos suma; en efecto,
se puede escribir: Rn = N1 + Cn–1 y En = N1 + Nn–1 .
..
Definición 18
Dados los grafos G1 = (V1 ,A1 ), G2 = (V2 ,A2 ), se define el pro-

ducto G1 × G2 = (V1 × V2 ,A) de manera que los vértices (u1 ,v1 ),
(u2 ,v2 ) son adyacentes si, y sólo si, se cumple alguna de las
condiciones siguientes:
1) u1 = u2 y v1 ≈ v2
2) u1 ≈ u2 y v1 = v2
Ejemplo 34
El producto de los dos primeros grafos es el tercer grafo:
2 2a 2b
1 a b 1a 1b
3 3a 3b
Ejemplo 35
A continuación, se muestran diversos ejemplos de grafos producto (de iz-

quierda a derecha): T2 × C4 , T2 × C3 , T5 × T4 .
Ejercicios
34. Describid, en términos de las operaciones entre grafos y a partir del grafo
nulo, los grafos bipartitos completos Kn,m .
35. Expresad los grafos siguientes en términos de combinaciones de grafos

elementales.
Soluciones
34. Kn,m = Nn + Nm
35. El grafo de la izquierda es T2 +C3 (también es K4 +N1 ), el central es N1 +N4 ,

el de la derecha es N2 + T4 .
2.3. Grafos isomorfos
Los grafos se pueden describir de maneras diferentes atendiendo a

la numeración o al etiquetado concreto de los vértices, lo que puede
dar lugar a descripciones conjuntistas muy diferentes.
Ejemplo 36
Los grafos siguientes son grafos con los vértices etiquetados y son obvia-
mente diferentes (atendiendo a las etiquetas).
.
1 4 1 4 1 4
2 3 2 3 2 3
G1 G2 G3
En concreto, para todos ellos V = {1,2,3,4} y, además,
G1 = (V,{{1,2},{2,3},{3,4}})
G2 = (V,{{1,2},{1,4},{3,4}})
G3 = (V,{{1,2},{2,3},{1,4}})
que son claramente diferentes, puesto que lo son los respectivos conjuntos
de aristas. Aun cuando las estructuras son las mismas, el etiquetado no es
irrelevante; puede ser clave para ciertos modelos y aplicaciones si el grafo
es el modelo para un proyecto de comunicaciones y los vértices del gra-
fo son poblaciones concretas, entonces es de mucha importancia práctica
saber qué vértice queda conectado con cuál o cuáles otros.
..
Definición 19
Dos grafos G1 = (V1 ,A1 ), G2 = (V2 ,A2) son idénticos si, y sólo
si, V1 = V2 , A1 = A2 .
Dos grafos G1 = (V1 ,A1 ), G2 = (V2 ,A2 ) son isomorfos si, y

sólo si, existe una biyección ϕ : V1 → V2 que conserva las
adyacencias y las no adyacencias, es decir, u ≈ v ⇔ ϕ(u) ≈
ϕ(v). En este caso, se dice que ϕ es un isomorfismo y G1 ∼
= G2 .
..
Proposición 6
Condiciones necesarias de isomorfismo (ninguna de ellas es

suficiente):
1) Dos grafos isomorfos son del mismo orden.

2) Dos grafos isomorfos tienen la misma medida.
3) Si ϕ : V1 → V2 es un isomorfismo de los grafos G1 = (V1 ,A1 ),
G2 = (V2 ,A2 ), entonces, por la propiedad de conservación
.
de las adyacencias y las no adyacencias, los vértices corres-
pondientes por la aplicación ϕ tienen que tener los mismos
grados, es decir gG1 (u) = gG2 (ϕ(u)). De aquı́ se deriva, en parti-
cular, que las secuencias de grados de dos grafos isomorfos tie-
nen que coincidir. Esta propiedad se puede utilizar para buscar
isomorfismos, puesto que sólo pueden asociarse vértices con
los mismos grados, cosa que es útil si hay vértices con grados
singulares o hay pocos vértices con los mismos grados.
Demostración: Consecuencia inmediata de la definición de isomorfismo

entre dos grafos.
Ejemplo 37
Un ejemplo simple de aplicación es el caso siguiente; los grafos no son

isomorfos porque no son de la misma medida o, alternativamente, porque
no tienen la misma secuencia de grados:
Ejemplo 38
Pero estas tres condiciones no son suficientes como lo demuestra el ejem-

plo siguiente: G1 = C6 , G2 = C3 ∪ C3 , tienen el mismo orden, la misma
medida y la misma secuencia de grados, pero no son isomorfos.
La idea general de un isomorfismo es que conserva toda la estructu-

ra del grafo, en particular todos los tipos de subgrafos. Esto puede
ser útil para concluir que dos grafos no son isomorfos. Por ejemplo,
si un grafo tiene un triángulo y el otro no, entonces no pueden ser
isomorfos.
Ejemplo 39
Observad que los grafos de la figura siguiente son del mismo orden, de la
misma medida y de la misma secuencia de grados. Por lo tanto, la pareja
pasa todos los tests anteriores sin que se pueda llegar a ninguna conclusión.
CC-BY-NC-ND • PID_00267019 40 Fundamentos de grafos
3 4 d
1 2 a b c f
6 5 e
Sea G1 = (V1 ,A1 ) el de la izquierda y G2 = (V2 ,A2 ) el de la derecha. Se puede

comprobar que no son isomorfos: se supone que existe algún isomorfismo
ϕ : V1 → V2 ; entonces, dado que los grados de los vértices correspon-
dientes tienen que ser los mismos, la imagen del único vértice de grado
1 de la izquierda tiene que ser el único vértice de grado 1 de la derecha,
de manera que ϕ (1) = a y al único vértice de grado 3 de la izquierda debe
corresponderle el único vértice del mismo grado de la derecha, de manera
que ϕ (2) = c. Ahora bien, la adyacencia no se conserva, puesto que 1 ≈ 2
y en cambio las imágenes a, c no son adyacentes. Por lo tanto, no puede
haber ningún isomorfismo entre los dos grafos.
Se pueden utilizar otros argumentos sobre la estructura: los dos grafos an-
teriores no pueden ser isomorfos, puesto que el de la izquierda contiene un
ciclo C5 , es decir, un subgrafo isomorfo a un 5-ciclo, lo que no sucede con
el de la derecha.
Ejemplo 40
Veamos ahora a continuación un ejemplo de isomorfismo. Se establecerá

la correspondencia isomórfica guiados por la conservación de grados, de
adyacencias y no adyacencias. Se indica por G1 el grafo de arriba y por G2
el grafo de abajo, y se verá como se puede definir ϕ : V1 → V2 de manera
que sea un isomorfismo.
1
8 5
4 2
7 6
3
e b a
g d
h
El proceso de asignación de imágenes pasa por varias fases:
1) Los vértices de grado 1 tienen que tener como imágenes vértices de

grado 1. Por lo tanto, hay dos posibilidades (se escogerán la primera y,
si conviniera, después se eligirı́a la segunda):
1 7→ c 3 7→ d
2) El único vértice de grado 4 tiene que tener por imagen el único vértice
de grado 4, es decir:
5 7→ f
3) El único vértice de grado 2 tiene que tener como imagen el único vértice
de grado 2, es decir:
8 7→ e
4) Falta por asignar las imágenes de los vértices 2,4,6,7, que son de grado
3, a los que corresponderá vértices de grado 3, con criterios de conser-
vación de adyacencias y no adyacencias; 1,3 son adyacentes a 2 y, por
lo tanto, la imagen de 2 tendrá que ser adyacente a las imágenes de 1,3,
de manera que resultará:
2 7→ b
4 es adyacente a 5,2 y, en consecuencia, la imagen tiene que ser adya-
cente a las imágenes correspondientes, es decir, a a, de manera que se
tendrá
4 7→ a
6 es adyacente a 4,5 y, en consecuencia,
6 7→ h
Finalmente, 7 7→ g por razones similares.
Una última comprobación permite ver que hay conservación de adyacen-

cias y no adyacencias, y obviamente la correspondencia es biyectiva.
..
Definición 20
Un grafo es autocomplementario si es isomorfo a su comple-

mentario.
Ejercicios
36. Dos grafos son isomorfos si, y sólo si, lo son los complementarios res-
pectivos. ¿Cierto o falso?
37. ¿Cómo se relacionan n y r en el caso de grafos de orden n r-regulares

autocomplementarios?
38. Estableced una correspondencia isomórfica entre los dos grafos que se
muestran a continuación:
.
1 4 b a
2 3 d c
Soluciones
36. Cierto (acabad de justificar la respuesta).
37. En estos grafos n tiene que ser impar y r = (n – 1)/2.
38. Por ejemplo, ϕ(1) = b, ϕ(2) = d, ϕ(3) = c, ϕ(4) = a.
2.4. Extensiones del concepto de grafo (simple)
Hay situaciones que no se pueden modelar a partir de un grafo

simple. Por eso, es necesario extender el concepto de grafo a estas
situaciones. Y, desde este punto de vista, las definiciones que hemos
visto hasta ahora continúan siendo correctas, como extensiones del
concepto de grafo simple.
2.4.1. Multigrafos y pseudografos
..
Definición 21
Un multigrafo es un grafo que admite aristas múltiples.
Ejemplo 41 Nota histórica
En el caso de los puentes de Königsberg, representado más abajo, aparecen El estudio de grafos tiene
aristas múltiples que conectan una pareja de vértices. También aparece esta uno de sus momentos
situación cuando se considera un grafo de comunicaciones entre localida- fundacionales en el siglo
des y hay más de un camino directo que las comunica. XVIII , con la formulación
por parte de Euler del
problema de los puentes
. de Königsberg: consiste
en averiguar si hay
alguna manera de
organizar un recorrido
por la ciudad de
Köningsberg, con el
mismo punto de llegada
que de salida y que pase
por todos los puentes
(aristas del grafo) sin
repetir ninguno.
..
Definición 22
Un pseudografo es un grafo que admite aristas del tipo {u,u}

conectando un vértice consigo mismo (bucles o lazos), posi-
blemente de forma múltiple, y también aristas múltiples entre
pares de vértices.
Los grados de los vértices se cuentan según la definición original.

De ahı́ que para cada bucle se incrementa en 2 el grado del vértice.
Los grafos simples son los que corresponden a la definición original,

por contraposición con estas nuevas extensiones.
Ejemplo 42
Esta figura representa un pseudografo:
Ejercicios
39. Indicad la secuencia de grados de los grafos de los puentes de Königsberg.
40. Analizad si la fórmula de los grados se puede extender a los multigrafos

y pseudografos.
Soluciones
39. La secuencia de grados del grafo de Königsberg es 3,3,3,5.
40. Sı́ (acabad de justificar la respuesta).

2.4.2. Grafos orientados o dirigidos
Existen aplicaciones en las cuales las situaciones no se describen

correctamente si no se asignan orientaciones o sentidos de recorri-
do a las aristas del grafo. Esto da lugar a grafos orientados, también
denominados dirigidos o digrafos.
Ejemplo 43
Esta figura representa un grafo orientado:
..
Notación
Definición 23
{u,v} indica que no hay
orden entre u y v,
• Un digrafo (o grafo dirigido) G = (V,A) es un par ordena-
mientras que (u,v)
do, en el que V es un conjunto finito y A es un subconjunto distingue el primer
del producto cartesiano V × V. vértice u del segundo v.
Utilizaremos {u,v} para
• Un arco (o arista orientada) es un par ordenado (u,v) ∈ las aristas de los grafos
simples y (u,v) para los
V × V; en el caso u = v, se tiene un bucle orientado. Los arcos de los digrafos.
arcos (u,v) y (v,u) son diferentes; el origen del arco a = (u,v)
es el vértice u y el final o extremo es el vértice v.
• El orden del digrafo es el número de vértices y la medida
es el número de arcos.
..
Definición 24
Para cada vértice v ∈ V del digrafo se define g + (v), grado de

salida, como el número de arcos que tienen el vértice v como
origen; o, dicho de otro modo, el cardinal del conjunto {(v,u) |
(v,u) ∈ A}.
Análogamente, el grado de entrada g – (v) es el número de ar-

cos cuyo extremo es el vértice v o, de manera equivalente, el
cardinal del conjunto {(u,v) | (u,v) ∈ A}.
..
Definición 25
Dado el digrafo G = (V,A), se define el grafo subyacente

(V,A′ ) de manera que {u,v} ∈ A′ si, y sólo si, (u,v) ∈ A o
(v,u) ∈ A.
Se pueden considerar también combinaciones de los conceptos an-

teriores e hı́bridos, en los cuales por ejemplo no todas las aristas
sean orientadas.
Ejercicios
41. Indicad cuál es el grado de entrada y salida de cada vértice del grafo del
ejemplo 43.
42. Formulad una versión para digrafos de la fórmula de los grados expresada
en términos de los grados de entrada y de salida de los vértices.
Soluciones
41. Grados de entrada: 0, 2, 2, 1, 1, 3, 1, 2, 3.

Grados de salida: 3, 2, 1, 3, 2, 1, 2, 1, 0.
42. g + (v) + g – (v) = 2|A| o, precisando más, g + (v)= g – (v) =

P P P P
v∈V v∈V v∈V v∈V
|A|.
2.5. Representación y almacenamiento
Ni la representación abstracta ni la representación gráfica de un

grafo en el plano son apropiadas para describir el grafo, si se lo
quiere manipular mediante un programa; se tienen que proponer
métodos alternativos para la descripción y el almacenamiento. En
primer lugar, siempre es necesario enumerar los vértices. A conti-
nuación, se puede construir la matriz de adyacencias, o bien la lista
de adyacencias.
2.5.1. La matriz de adyacencias
..
Definición 26
Dado el grafo G = (V,A), se define la matriz de adyacencias

de un grafo simple (relativa a una ordenación de los vértices)
como la matriz B = (bij ) dada por bij = 1 si, y sólo si, los vértices
vi y vj son adyacentes y bij = 0, en caso contrario.
Ejemplo 44
La matriz de adyacencias del grafo
.
1 2
5 4
será una matriz cuadrada de orden 5 × 5:
1 2 3 4 5
Observación
1 0 1 0 0 1
2 1 0 1 1 1 La matriz de adyacencias
3 0 1 0 1 0 de un grafo simple:
4 0 1 1 0 1
• Es simétrica.
5 1 1 0 1 0
• Sólo contiene 0 y 1.
• Tiene la diagonal
En el caso de multigrafos, pseudografos y grafos orientados, se tiene
principal ocupada
que tener en cuenta que: por 0.
1) Los 0 de la diagonal podrı́an ser 1 si hubiera lazos.
2) La matriz podrı́a contener valores mayores que uno si hubiera

aristas múltiples.
3) La matriz podrı́a no ser simétrica en el caso de grafos orientados.
Ejemplo 45
Este ejemplo muestra cómo la matriz de adyacencias depende de una orde-

nación determinada de los vértices del grafo. Si se modifica la ordenación
de los vértices del grafo del ejemplo anterior se obtiene otra matriz de adya-
cencias:
.
3 5
4 1
2 3
0 1 0 1 1
1 0 0 0 1
6 7
6 7
6 7
B=6
6 0 0 0 1 1 7
7
1 0 1 0 1
6 7
4 5
1 1 1 1 0
Se puede generalizar el concepto de matriz de adyacencias para

multigrafos, pseudografos.
Ejemplo 46
La matriz de adyacencias del grafo de Königsberg es

2 3
0 1 0 2
6 1 0 1 1 7
B=6
6 7
0 1 0 2
7
4 5
2 1 2 0
Cada posición contiene el número de aristas que conectan los dos vértices
correspondientes.
Una de las ventajas de la matriz de adyacencias es la simplicidad de

la estructura de datos para el almacenamiento, puesto que se puede
almacenar en una tabla (array) bidimensional.
Para un grafo de orden n serı́a,
G : tabla [1 . . n,1 . . n] entero
De las caracterı́sticas de esta estructura de almacenamiento se pue-

den deducir las propiedades siguientes:
1) Es una estructura muy fácil de manipular y el tiempo necesario

para acceder a cada posición es constante.
2) El espacio necesario para almacenar un grafo de orden n es pro-
Observación
porcional a n2 . Como el número de aristas es, como máximo,
1
2 n(n – 1), siempre habrá ceros en la matriz y se tendrá espacio de
La desventaja principal
almacenamiento ocupado innecesariamente. de la matriz de
adyacencias es el espacio
3) Si el grafo no es dirigido, la matriz será simétrica y todavı́a se ocupado de forma
innecesaria.
tendrá más espacio ocupado innecesariamente. En estos casos
se puede utilizar una matriz de adyacencias triangular para
Observación
almacenar el grafo con un ahorro del 50% en el espacio ocupado.
4) Para realizar un recorrido de todas las aristas del grafo, será ne- La ventaja principal de la
matriz de adyacencias es
cesario hacer n(n – 1)/2 consultas, independientemente de la me- la simplicidad
dida m del grafo. Igualmente, para visitar los vértices adyacentes estructural.
a un vértice, será necesario hacer n – 1 consultas independien-
temente del grado de este vértice. Por lo tanto, el tiempo que
tardaremos en hacer recorridos será proporcional a n2 y no a la

medida m del grafo.
2.5.2. La lista de adyacencias
Para conseguir evitar el principal inconveniente de la matriz de

adyacencias (el espacio ocupado de manera innecesaria) se puede
optar por almacenar el grafo en forma de lista de adyacencias.
..
Definición 27
Dado el grafo G = (V,A), se define la lista de adyacencias de

un grafo simple como una lista de vértices adyacentes a un
vértice dado.
Ejemplo 47
Para el grafo,
.
1 2
5 4
la lista de adyacencias será:
1 : 2, 5
2 : 1, 3, 4, 5
3 : 2, 4
4 : 2, 3, 5
5 : 1, 2, 4
Como en la matriz de adyacencias, la representación depende de

la ordenación concreta de los vértices. Además, también se puede
generalizar esta estructura para multigrafos, pseudografos y grafos
orientados.
Para almacenar la lista de adyacencias se necesita una tabla (array)

de n punteros, donde el i-ésimo elemento apunta a una lista enlaza-
da de todas las aristas incidentes al vértice i. Para un grafo de orden
n serı́a,
G : tabla [1 . . n] puntero lista de vértices

Ejemplo 48
Para el grafo
.
1 2
5 4
la estructura de datos será,
1 2 5
2 1 3 4 5
3 2 4
4 2 3 5
5 1 2 4
Comparando esta estructura de datos con la de la matriz de adya-

cencias se observa que:
1) El espacio necesario para almacenar un grafo de n vértices y m

aristas, mediante el uso de una lista de adyacencias, es propor-
cional a n + 2m (n + m si el grafo es dirigido).
2) La estructura es más difı́cil de manipular que la matriz de adya-
cencias. En particular, el tiempo necesario para comprobar si dos
vértices son adyacentes no es constante; es proporcional a gi , si
gi es el grado del vértice i.
3) La elección de una estructura de datos u otra dependerá de las
Observación
medidas del grafo y de los algoritmos que tengan que utilizarse.
Como regla general, la matriz de adyacencias es adecuada para La desventaja principal
grafos densos (los que tienen muchas aristas), en los que m ∼ n2 . de la lista de adyacencias
es la dificultad de
En cambio, la representación como lista de adyacencias es ade- manipulación.
cuada para grafos poco densos, aquellos que m << n2 .
4) Por otra parte, recorrer las aristas del grafo requiere realizar 2m Observación
operaciones, tiempo que puede ser inferior al de la representa-
La ventaja principal de la
ción por matriz de adyacencias si el grafo tiene pocas aristas. lista de adyacencias es la
Igualmente, es más eficiente el recorrido de los vértices adyacen- minimización del espacio
de almacenamiento.
tes a un vértice, dado que depende del grado de este vértice y no

de n. Esto quiere decir que la representación por lista de adya-
cencias es más rápida para implementar recorridos del grafo.
En la práctica, aunque la lista de adyacencias es más difı́cil de mani-

pular, tiene mejor comportamiento en la mayorı́a de los algoritmos.
Ejercicios
43. Escribid las matrices de adyacencias y las listas de adyacencias (con las
ordenaciones naturales de los vértices) del grafo nulo N5 , del grafo completo
K5 , del grafo bipartito completo K2,3 , del grafo trayecto T5 , del grafo ciclo C5 ,
del grafo estrella E5 y del grafo rueda R5 .
44. Indicad cómo se puede calcular el grado de un vértice a partir de la ma-

triz de adyacencias y a partir de la lista de adyacencias. Indicad, también, el
número de operaciones elementales que serı́an necesarias.
45. ¿Cómo puede detectar un programa los grafos nulos y completos a partir
de la matriz de adyacencias?
46. Completad la tabla siguiente, indicando, para cada entrada, qué tipo de
representación serı́a la más adecuada (matriz de adyacencias o lista de adya-
cencias) y el número de operaciones elementales que serı́an necesarias para
cada uno de los problemas propuestos.
Problema Representación Operaciones

Comprobar si el vértice i es adyacente al vértice j
Calcular el grado del vértice i
Añadir una arista entre el vértice i y el vértice j
Comprobar si el grafo es nulo
Eliminar la arista entre el vértice i y el vértice j
Calcular la medida del grafo
Comprobar si el grafo es regular
Soluciones
43. Las matrices de adyacencias y listas de adyacencias para estos casos con-
cretos son las siguientes:
2 Grafo nulo (N5 ) 3 Grafo completo (K53)

2 Grafo2bipartito completo3 (K2,3 )
0 0 0 0 0 0 1 1 1 1 0 0 1 1 1
0 0 0 0 0 1 0 1 1 1 6 0 0 1 1 1 7
6 7 6 7 6 7
6 7 6 7
6 7 6 7 6 7
6
6 0 0 0 0 0 7
7
6
6 1 1 0 1 1 7
7
6 1 1 0 0 0 7
6 7
0 0 0 0 0 1 1 1 0 1 4 1 1 0 0 0 5
6 7 6 7 6 7
4 5 4 5
0 0 0 0 0 1 1 1 1 0 1 1 0 0 0
2Grafo trayecto (T5 )3 2Grafo estrella (E5 )3 2 Grafo rueda (R5 ) 3

0 1 0 0 0 0 1 1 1 1 0 1 1 1 1
6 1 0 1 0 0 6 1 0 0 0 0 6 1 0 1 0 1
6 7 6 7 6 7
7 7 7
6 7 6 7 6 7
6 0 1 0 1 0 7 6 1 0 0 0 0 7 6 1 1 0 1 0 7
6 7 6 7 6 7
4 0 0 1 0 1 4 1 0 0 0 0 4 1 0 1 0 1
6 7 6 7 6 7
5 5 5
0 0 0 1 0 1 0 0 0 0 1 1 0 1 0
2 Grafo ciclo (C5 ) 3

0 1 0 0 1
6 1 0 1 0 0
6 7
7
6 7
6 0 1 0 1 0 7
6 7
4 0 0 1 0 1
6 7
5
1 0 0 1 0
Grafo nulo (N5 ) Grafo completo (K5 ) Grafo bipartito completo (K2,3 )
1 : 1 : 2, 3, 4, 5 1 : 3, 4, 5
2 : 2 : 1, 3, 4, 5 2 : 3, 4, 5
3 : 3 : 1, 2, 4, 5 3 : 1, 2
4 : 4 : 1, 2, 3, 5 4 : 1, 2
5 : 5 : 1, 2, 3, 4 5 : 1, 2
Grafo trayecto (T5 ) Grafo estrella (E5 ) Grafo rueda (R5 ) Grafo ciclo (C5 )
1 : 2 1 : 2, 3, 4, 5 1 : 2, 3, 4, 5 1 : 2, 5
2 : 1, 3 2 : 1 2 : 1, 3, 5 2 : 1, 3
3 : 2, 4 3 : 1 3 : 1, 2, 4 3 : 2, 4
4 : 3, 5 4 : 1 4 : 1, 3, 5 4 : 3, 5
5 : 4 5 : 1 5 : 1, 2, 4 5 : 1, 4
44. Si se supone que se calcula el grado del vértice etiquetado i.
Matriz de adyacencias: sumando los términos de la fila i-ésima. Será necesario

hacer n operaciones elementales (n sumas).
Lista de adyacencias: contar el número de elementos de la lista i-ésima. Acce-

der a la lista i-ésima necesita una operación y contar el número de elementos
depende del grado gi del vértice i-ésimo. En total, gi + 1 operaciones elementa-
les.
45. Lo puede detectar comprobando los elementos de la matriz. Si todos son

ceros, es el grafo nulo; si todos son 1, excepto la diagonal, entonces el grafo es
completo.
46. En esta tabla, n es el orden del grafo, m, la medida y gi indica el grado del
vértice i.
Problema Representación Operaciones

Comprobar si el vértice i es adyacente al vértice j Matriz 1
Calcular el grado del vértice i Lista gi + 1
Añadir una arista entre el vértice i y el vértice j Matriz 1
Comprobar si el grafo es nulo Lista n
Eliminar la arista entre el vértice i y el vértice j Matriz 1
Calcular la medida del grafo Lista 2m + n
Comprobar si el grafo es regular Lista 2m + n
Ejercicios de autoevaluación
1. El Sr. Castillo y su mujer invitaron a cuatro parejas a una fiesta. Cuando

todos ya habı́an llegado, algunas de las personas de la sala saludaron (dando la
mano) a otras personas del grupo. Naturalmente, ninguna persona dio la ma-
no a su cónyuge ni ninguna persona dio la mano dos veces a otra persona.
Pudo haber personas que no saludasen a nadie.
Al final, el Sr. Castillo, se da cuenta de que ninguno de sus invitados (su mujer
incluida) han saludado al mismo número de personas.
Utilizad la teorı́a de grafos e interpretad y responded a cada una de las pre-

guntas siguientes:
a) ¿Es posible que el Sr. Castillo también diera la mano a un número de per-
sonas diferente al de las demás?
b) ¿Es posible que el Sr. Castillo diera sólo un número impar de apretones de
manos?
c) ¿Hay alguna persona que no dio la mano a nadie?
d) ¿Cuántas veces dio la mano el Sr. Castillo? ¿Y la Sra. Castillo?
2. Probad que cualquier grafo G = (V,A) con un mı́nimo de dos vértices

siempre tiene un mı́nimo de dos vértices del mismo grado. En otras palabras,
no hay ningún grafo de orden superior o igual a 2 con todos los grados de los
vértices diferentes.
3. Dado un grafo G = (V,A), si ki P es el número

P de vértices de grado i, indicad
qué relaciones hay entre: |A|, |V |, i≥0 iki , i≥0 ki .
4. Sea G = (V,A) un grafo de orden n ≥ 10 tal que todos los vértices son de
grado estrictamente mayor que 5. Probad que el número de aristas del grafo
es mayor o igual que 30.
5. Sea G = (V,A) un grafo de n vértices, t de los cuales son de grado k y el

resto, de grado k + 1. Probar que t = (k + 1)n – 2m, siendo m el número de
aristas.
6. Si G = (V,A) es un grafo bipartito de orden n, ¿cuál será el número máximo

de aristas de este grafo?
7. Demostrad que no puede haber ningún grafo con vértices de grados 3, 3,

3, 1.
8. Estudiad si pueden haber grafos con las secuencias de grados siguientes:
a) 3, 3, 3, 3, 3, 4, 4
b) 6, 3, 3, 2, 2, 2
c) 4, 4, 3, 2, 1
9. ¿Para qué valores de d, entero no negativo, la secuencia siguiente es gráfica?
d,d + 1,d + 2, . . . ,d + n – 1
10. Si G = (V,A) es un grafo de orden n = 6, demostrad que G o su comple-

mentario Gc contiene algún triángulo (3-ciclo).
Este resultado es bastante sorprendente si no se interpreta en términos de

reuniones y relaciones de amistad o conocimiento mutuo entre asistentes a
una reunión: en una reunión de seis personas, o bien hay tres que se conocen
dos a dos, o bien hay tres que no se conocen dos a dos
11. ¿Cuál es la representación en matriz y lista de adyacencias de los dos

grafos siguientes?
Obtened, también, el espacio ocupado en cada caso.
12. Dependiendo de la medida m de un grafo de orden n puede llegar a

ser más eficiente utilizar la representación en matriz de adyacencias que la
representación en lista de adyacencias. Calculad, en función de n y m, cuándo
es más eficiente utilizar un tipo de representación u otro.
Soluciones
1. A partir de la información del problema puede construirse el grafo que se

muestra a continuación:
.
8 7
9 6
0 5
1 4
2 3
La respuesta es consecuencia inmediata de las propiedades del grafo.
2. Sea G = (V,A) un grafo de orden n (n ≥ 2). Ya que para cada vértice v ∈ V

se cumple 0 ≤ g(v) ≤ n – 1, sólo pueden existir los grados 0,1, . . . ,n – 1. Si
todos fueran diferentes, éstos tendrı́an que ser los grados correspondientes a
los vértices del grafo. Pero si un vértice tiene grado n – 1 es imposible que otro
tenga grado 0.
Una observación interesante es que este resultado se puede interpretar en

términos de reuniones y saludos entre asistentes a una reunión de la mane-
ra siguiente: en una reunión donde se saluda hay un mı́nimo de dos personas
que han hecho el mismo número de saludos. Esto es fácil de ver con el modelo
siguiente de la reunión en términos de teorı́a de grafos: los vértices represen-
tan los asistentes a la reunión y dos vértices son adyacentes si, y sólo si, las
personas correspondientes se saludan. El grado de cada vértice es el número
de saludos de la persona correspondiente. Sólo hace falta aplicar el resultado
que se ha demostrado.
3. Las relaciones son: |V | =

P P
i≥0 ki y 2|A| = i≥0 iki .
4. Por hipótesis se tiene que g(v) ≥ 6, ∀v ∈ V. Ahora se puede aplicar la

fórmula de los grados:
X X
2|A| = g(v) ≥ 6 = 6|V | ≥ 6 × 10 = 60.
v∈V v∈V
Inmediatamente se deriva el resultado que se debe demostrar.
5. Se puede escribir V = Vk ∪ Vk+1 , donde Vk es el conjunto de vértices de grado

k y Vk+1 es el conjunto de vértices de grado k + 1. Aplicando la fórmula de los
grados se obtiene la relación 2m = kt + (k + 1)(n – t). De la relación obtenida se
deriva inmediatamente la relación buscada.
6. Si x es el número de vértices del conjunto V1 , entonces n – x será el número

de vértices de V2 . El número total de aristas será x(n – x). Por lo tanto, hace
falta maximizar la función f (x) = x(n – x). La solución será ⌊ 14 n2 ⌋.
7. Se demostrará por medio de dos métodos diferentes,
Método A. Si existe un grafo G con la secuencia de grados 3, 3, 3, 1; también

deberı́a existir el grafo Gc con la secuencia de grados 0, 0, 0, 2, obviamente
imposible.
Método B. Aplicando el algoritmo de Havel-Hakimi:
3, 3, 3, 1
2, 2, 0
1,-1
8. a) No, porque contradice la proposición 4, consecuencia de la fórmula de

los grados.
b) No, porque no cumple la relación 0 ≤ g(v) ≤ n – 1.
c) No, aplicando el algoritmo de Havel-Hakimi.
9. La única posibilidad es que d = 0 y la secuencia quedarı́a 0,1,2, . . . ,n – 1.

Pero, por la definición de grado, no puede haber un vértice de grado 0 y otro
de grado n – 1.
10. Sea v ∈ V. Se puede suponer que v es adyacente a tres vértices de G, como

mı́nimo. En efecto, si esto no fuera ası́, es decir, si no hubiera tres vértices
adyacentes a v, habrı́a como máximo dos de adyacentes con v y, por lo tanto,
quedarı́a un mı́nimo de tres no adyacentes con v en G, los cuales serı́an adya-
centes a v en el grafo complementario Gc . Esto quiere decir que, fijado v ∈ G,
hay tres vértices adyacentes con v a G, o bien hay tres vértices adyacentes con
v a Gc .
.
w1
v w2
w3
En cualquiera de los casos se seguirı́an razonamientos similares; por ello, no

hay pérdida de generalidad al suponer que v es adyacente con tres vértices a
G, como mı́nimo.
Sean w1 ,w2 ,w3 vértices adyacentes con v en el grafo G. Si alguno de los wi es

adyacente a algún otro de los wj , entonces ya se tiene el 3-ciclo o triángulo,
cuya existencia se habı́a que demostrar, como se puede ver en los esquemas
que siguen:
.
De lo contrario, resultará la situación del esquema de más abajo (subfigura iz-

quierda), donde las aristas inexistentes se han indicado con trazo discontinuo;
entonces, en el grafo complementario Gc , los vértices w1 ,w2 ,w3 son adyacen-
tes dos a dos, demostrando ası́ la existencia de un 3-ciclo, como se ve en la
subfigura derecha del esquema siguiente, donde se han indicado con lı́nea
discontinua las aristas inexistentes.
11. El primer grafo es el grafo de Petersen que tiene orden 10 y medida 15.
En la representación en matriz de adyacencias ocuparı́a 102 = 100 unidades
de memoria. Como lista de adyacencias ocuparı́a 10 + 2 · 15 = 40 unidades de
memoria.
El segundo grafo es un grafo dirigido de orden 7 y medida 12. En la repre-

sentación en matriz de adyacencias ocuparı́a 72 = 49 unidades de memoria.
Como lista de adyacencias ocuparı́a 7 + 12 = 19 unidades de memoria.
12. La matriz de adyacencias necesita n2 unidades de memoria. La lista de

adyacencias n+2m (si no si tiene en cuenta el espacio necesario para almacenar
2
los enlaces). Por lo tanto, será mejor utilizar la lista si n + 2m < n2 o m < n 2–n .
2
Se observa que n 2–n es el número de aristas del grafo completo de n vértices.
Esto demuestra que la lista de adyacencias siempre ocupa menos memoria que
la matriz de adyacencias, excepto cuando el grafo es completo, caso en el
que tienen la misma ocupación de memoria.
Bibliografı́a
Biggs, N. L. (1994). Matemática Discreta. (1a. edición, traducción

de M. Noy). Barcelona: Ediciones Vicens Vives.

M3.Fundamentos de Ngrafos

Cargado por

Copyright:

Formatos disponibles

M3.Fundamentos de Ngrafos

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

M3.Fundamentos de Ngrafos

Cargado por

Copyright:

Formatos disponibles

Fundamentos de

Tiempo mínimo de dedicación recomendado: 5 horas

Joaquim Borges Robert Clarisó Ramon Masià Jaume Pujol

Josep Rifà Joan Vancells Mercè Villanueva

Cuarta edición: Septiembre 2019

2. Estructura y manipulación de grafos . . . . . . . . . . . . . . . 31

Este módulo es una iniciación a la teorı́a de grafos, en la que se

Es posible que esta disciplina os sea completamente nueva, dado

En muchas situaciones, se establecen una serie de relaciones en- Grafo

En esta representación gráfica, la posición de un vértice o la longi-

Se considera el grafo que se representa de la manera siguiente.

1. Proponed un modelo en términos de teorı́a de grafos (y haced una repre-

2. Proponed un modelo de grafos representativo de las comunicaciones por

dibujad) un modelo en términos de teorı́a de grafos que recoja la situación de

1. Un esquema posible serı́a el siguiente.

2. Realmente no hay “una” solución. Un posible esquema indicativo, ficticio

3. Un posible esquema es el del grafo siguiente. Éste corresponde a un tipo

1.2. Vértices y aristas

Los vértices u,v ∈ V son adyacentes si, y sólo si, existe la

• Los vértices u, v y la arista uv son incidentes.

Igualmente, se dice que dos aristas son adyacentes si compar-

Se considera el grafo siguiente.

Los vértices v5 , v6 son adyacentes; no lo son los vértices v6 , v8 . Los vértices

Las propiedades y algoritmos que relacionan el número de vértices

• Dado un grafo G = (V,A), el orden del grafo es el cardi-

No es difı́cil deducir la siguiente proposición.

Dado un vértice v ∈ V del grafo G = (V,A) se define el grado

g(v) = |{u ∈ V | v ≈ u}| = |{u ∈ V | {u,v} ∈ A}|

Los vértices de grado cero se denominan vértices aislados.

Consideremos un grupo de personas que se encuentran en una reunión.

Resulta evidente que:

Este resultado se puede utilizar para descartar la existencia de grafos

Se observa que no puede existir ningún grafo con la secuencia de grados

A partir del grado de los vértices de un grafo, puede definirse el

Un grafo es regular si todos los vértices son del mismo gra-

A continuación se presentan diversos ejemplos de grafos regulares.

El primer grafo es 1-regular y el resto son 3-regulares.

4. Considerad el grafo del esquema adjunto. Describid formalmente el con-

5. Representad gráficamente un grafo de vértices V = {v1 , v2 , v3 , v4 , v5 } y

6. Un grafo 4-regular es como mı́nimo de orden 5. ¿Es esto cierto?

7. ¿Qué grafos son 0-regulares?

8. ¿Qué medidas son posibles, para los grafos de orden 3?

5. A continuación se presentan diversas soluciones.

6. Cierto, ya que |V | ≥ g(v) + 1 ≥ 4 + 1 ≥ 5. En general, si un grafo es r-regular,

7. Los grafos 0-regulares son los grafos sin aristas.

1.3. Subestructuras de un grafo

Dado un grafo G = (V,A), un subgrafo de G es un grafo H =

Ası́, el nuevo conjunto de vértices es un subconjunto del original, y

• Dado un grafo G = (V,A), se considera un subconjunto

El grado de un vértice u relativo a un subgrafo H se escribe gH (u).

Considerad el grafo representado en la figura siguiente.

Un ejemplo de subgrafo puede ser el siguiente: H = (V ′ ,A′ ), V ′ = {1,2,4,5},

Un subgrafo generador serı́a, por ejemplo, H = {{1,2,3,4,5},{{3,4},{2,4}}}.

El subgrafo generado por el conjunto de vértices S = {2,3,4,5} es el grafo

1.4. Fórmula de los grados

Fórmula de los grados. Teorema 3

Dado un grafo G = (V,A), se cumple que

es decir, la suma de los grados de un grafo es el doble del

Demostración: Tan solo es necesario contar el número de aristas del grafo a

Se considera un grafo con secuencia de grados 2,2,2,2,2,2,3,1. Se puede