Matemáticas Discretas

Grafos
Guía de Conceptos
Unidad IV
Matemáticas Discretas – Unidad IV

Tabla de contenido
INTRODUCCIÓN ............................................................................................................................. 3
1. HISTORIA ................................................................................................................................... 3
2. GRAFOS ..................................................................................................................................... 4
2.1. Definición .................................................................................................................. 4
2.2. Grafo dirigido ............................................................................................................ 5
2.3. Vértices adyacentes ................................................................................................... 5
2.4. Grafos no dirigidos .................................................................................................... 6
2.5. Grafo conexo ........................................................................................................... 11
2.5.1. Conexidad en grafos .................................................................................................. 14
2.6. Grado de un vértice.................................................................................................. 15
3. ÁRBOLES .................................................................................................................................. 16

4. MATRIZ DE ADYACENCIA DE UN GRAFO ................................................................................. 18

5. PASEOS Y CIRCUITOS ............................................................................................................... 19
5.1. Paseos eulerianos y circuitos ................................................................................... 20
5.2. Paseos y circuitos hamiltonianos ............................................................................. 21
7. UNAS APLICACIONES DE LOS GRAFOS .................................................................................... 24
7.1. Grafos y redes de computadores .............................................................................. 24
7.2. El problema del cartero chino .................................................................................. 25
7.4. Búsqueda en Internet y la teoría de grafos .............................................................. 27
BIBLIOGRAFÍA .............................................................................................................................. 28

Material Básico pág. 2

Matemáticas Discretas – Unidad IV

INTRODUCCIÓN
La Teoría de Grafos forma parte actualmente de los estudios de matemáticas, de
investigación operativas, de matemática discreta, y se encuentra en los estudios
informáticos.

Tiene una notable eficacia para la representación de cualquier relación que implique la
resolución de problemas de conectividad, a los efectos de tomar la mejor decisión
cuando se modelan rutas entre ciudades, rutas aéreas, envíos de correos electrónicos,
recorridos turísticos, sistema de transporte público, entre otros.

Los grafos se utilizan para modelar situaciones en las que se relacionan entre sí pares
de objetos de una determinada colección. Gráficamente, el modelo consiste en puntos
que representan los objetos y líneas que unen dichos puntos.

1. HISTORIA
La Teoría de Grafos, dice Cambariza (2003), es una de las ramas más importantes de
las matemáticas modernas, comenzó en el siglo XVIII por una de las mentes más

Material Básico pág. 3

Matemáticas Discretas – Unidad IV

grandes que ha existido. En 1736 el matemático Suizo Leonhard Euler público un

artículo llamado Solutio problematis ad geometrian situs pertinentis, en español, La
solución de un problema referente a la geometría de posición, relacionado al problema
de los puentes de Konigsberg, en la antigua Alemania, que actualmente pertenece a
Rusia y se llama Kaliningrado, es considerado el primer resultado de la teoría de grafos.
También se considera uno de los primeros resultados topológicos en geometría (que no
depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría
de grafos y la topología.

Según Dubreil (2003), fue Gustav Kirchhoff quien en 1845 publicó sus leyes de los
circuitos para calcular el voltaje y la corriente en los circuitos eléctricos. Por su parte,
Francis Guthrie en 1852 planteó el problema de los cuatro colores que plantea si es
posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal
forma que dos países vecinos nunca tengan el mismo color.

Este problema, que no fue resuelto hasta un siglo después por Kenneth Appel y
Wolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al
tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos
fundamentales de los grafos.

2. GRAFOS
2.1. Definición
Expresa Durán (2008), que un grafo es un conjunto no vacío de objetos llamados
vértices o nodos, y una selección de pares de vértices, llamados aristas que pueden ser
orientados o no. Típicamente, un grafo se representa mediante una serie de puntos, los
vértices, conectados por líneas, que son las aristas, tal se observa en la Figura 1.

Figura 1. Grafo con 6 vértices y 7 aristas. (Teoría de Grafos, 2012)

Liu (1995), define un grafo como un par G = (V, E), donde V es un conjunto no vacío,
llamado conjunto de vértices de G, y E es un conjunto de pares no ordenados de vértices
distintos, llamados aristas, tal que cada par de vértices distintos determinan una única
arista. Se dice que una arista es incidente con los vértices que ella une.

Material Básico pág. 4

Matemáticas Discretas – Unidad IV

2.2. Grafo dirigido

Siguiendo con Liu (1995) un grafo dirigido G define en términos abstractos como un par
ordenado (V, E), donde V es un conjunto y E es una relación binaria sobre V. Un grafo
dirigido puede representarse geométricamente como un conjunto de puntos marcados
V con un conjunto de flechas E entre parejas de puntos (Figura 2).

Figura 2. (Liu, 1995)

En la Figura 2 se tiene que la arista (a , b) es incidente con los vértices a y b. Para ser
más específico, puede decirse que la arista (a , b) es incidente desde a y es incidente
hacia b. El vértice a es llamado vértice inicial y el vértice b el vértice terminal de la arista
(a , b).

Una arista que es incidente a partir y hacia el mismo vértice, como (c , c) en la Figura 2,
es llamado un lazo. Por su parte, un grafo con lazos y/o con aristas paralelas se
considera un multigrafo.

2.3. Vértices adyacentes

Explica Dubreil (2003), los vértices adyacentes son aquellos grafos que conforman un
lado o arista. Todo lado conformado por dos vértices se dice que es incidente sobre
esos vértices. Si un vértice no tiene otro adyacente se dice que es aislado. En la Figura
3 se tiene que los vértices 1 y 2 son adyacentes, sin embargo, los vértices 2 y 4 son no
adyacentes. En tanto, la arista c (3 , 2) es incidente en los vértices 2 y 3.

Figura 3. (Dubreil, 2003)

Material Básico pág. 5

Matemáticas Discretas – Unidad IV

2.4. Grafos no dirigidos

Según Liu (1995) un grafo no dirigido G se define de manera abstracta como un par
ordenado (V , E), donde V es un conjunto y E es un conjunto de multiconjuntos de dos
elementos de V.

Por ejemplo, 𝑮 = ({𝒂 , 𝒃, 𝒄, 𝒅} , {𝒂 , 𝒃} , {𝒂 , 𝒅} , {𝒃 , 𝒄} , {𝒃 , 𝒅} , {𝒄 , 𝒄}) es un grafo no

dirigido. Un grafo no dirigido puede representarse geométricamente como un conjunto
de puntos marcados V con un conjunto de líneas entre los puntos. El grafo no dirigido
G mencionado se muestra en la Figura 4.

Figura 4. (Liu, 1995)

Para 𝑽 = {𝒂 , 𝒃 , 𝒄, 𝒅, 𝒆} un conjunto de programas de computadora, en la Figura 5 se

muestra un grafo no dirigido en el cual hay una arista entre dos vértices si los programas
correspondientes comparten algunos datos en común.

Figura 5. (Liu, 1995)

Material Básico pág. 6

Matemáticas Discretas – Unidad IV

Ejemplo 1. Sea 𝑉 = {𝑎 , 𝑏 , 𝑐, 𝑑} un conjunto de cuatro jugadores en un torneo de tenis

de eliminación directa.

Sea 𝐸 = {(𝑎 , 𝑏), (𝑎 , 𝑑), (𝑏 , 𝑑), (𝑐 , 𝑎), (𝑐 , 𝑏), (𝑑 , 𝑐)} una relación binaria sobre V de
manera que (x , y) en E significa que x venció a y en el encuentro entre ellos. El grafo
G = (V , E) se muestra en la Figura 6.

Figura 6. (Liu, 1995)

Ejemplo 2. Sea 𝑉´ = {1 , 2 , 3, 4} el conjunto de los cuatro capítulos en un libro.

Si 𝐸´ = {(1 , 2), (2 , 3), (3 , 1), (3 , 4), (4 , 1), (4 , 2)} es una relación binaria sobre 𝑉´ tal que
(1 , 2) está en 𝐸´ significa que el material en el capítulo 1 hace referencia al material en
el capítulo 2, y así sucesivamente. El grafo 𝐺´ = (𝑉´, 𝐸´) se muestra en la Figura 7.
Observando con detenimiento se podrá reconocer que el grafo de la Figura 6 se parece
al grafo de la Figura 7.

Figura 7. (Liu, 1995)

Material Básico pág. 7

Matemáticas Discretas – Unidad IV

De hecho, la semejanza es más evidente si se vuelve a dibujar el grafo de la Figura 6,

tal se muestra en la Figura 8. Comparando los grafos de la Figura 6 y de la Figura 8, es
posible identificar que el problema del torneo de tenis como el problema de las
referencias cruzadas entre capítulos puede representarse de modo abstracto por el
mismo grafo.

Figura 8. (Liu, 1995)

Por tanto, muchos de los resultados referentes a los jugadores de tenis pueden volverse
a expresar a partir de los resultados referentes a los capítulos del libro. Así, de acuerdo
con la Figura 6, el jugador b es mejor que el jugador d quien, a su vez, venció al jugador
c, y de acuerdo con la Figura 7, el capítulo 1 se refiere al capítulo 2, el cual, a su vez,
se refiere al capítulo 3.

El concepto de semejanza entre los dos grafos analizados se puede hacer con precisión,
dado que dos grafos son isomorfos si hay una correspondencia uno a uno entre sus
vértices y entre sus aristas, de modo que las incidencias se conservan. Es decir, existe
una arista entre dos vértices en un grafo si y sólo si hay una arista correspondiente entre
los vértices correspondientes en el otro grafo.

En la Figura 9 se muestra un par de grafos no dirigidos isomorfos, y la Figura 10, por su

parte muestra un par de grafos dirigidos isomorfos. En estas dos figuras, los vértices
correspondientes en los dos grafos isomorfos están etiquetados con la misma letra, con
superíndice de prima y sin superíndice.

Material Básico pág. 8

Matemáticas Discretas – Unidad IV

Figura 9. Grafos no dirigidos isomorfos (Liu, 1995)

Figura 10. Grafos dirigidos isomorfos (Liu, 1995)

Sea G = (V, E) un grafo. Se dice que un grafo G´= (V´, E´) es un subgrafo de G si E´ es
un subconjunto de E y V´ es un subconjunto de V tal que las aristas de E´ son incidentes
sólo con los vértices de V´. La Figura 11(b) muestra un subgrafo del grafo de la Figura
11(a). Se dice que un subgrafo de G es un subgrafo generador si éste contiene todos
los vértices de G.

Figura 11(a). (Liu, 1995) Figura 11(b). (Liu, 1995)

Material Básico pág. 9

Matemáticas Discretas – Unidad IV

El complemento de un subgrafo G´= (V´, E´) con respecto al grafo G es otro

subgrafo G´´ = (V´´, E´´) tal que E´´ es igual a E – E´, y V´´ sólo contiene a los
vértices con los cuales las aristas de E´´ son incidentes. La Figura 11(c) muestra
el complemento del subgrafo de la Figura 11(b).

Figura 11(c). (Liu, 1995)

El grafo completo no dirigido de n vértices, denotado por 𝐾𝑛 , es un grafo con n vértices,

en el cual existe una arista entre cada par de vértices distintos. El complemento de un
grafo G de n vértices está definido como su complemento con respecto a 𝐾𝑛 y se denota
por 𝐺̅ .

Sea por ejemplo G un grafo de n vértices. Suponiendo que los n vértices de G

representan n personas, y el conjunto de aristas de G, representa una relación de
compatibilidad tal que una arista entre dos vértices significa que las dos personas
correspondientes pueden trabajar cooperando mutuamente. Entonces, el conjunto de
aristas de 𝐺̅ representará la relación de incompatibilidad entre las n personas.

También se define un grafo dirigido completo de n vértices como un grafo con n vértices
en el cual existe exactamente una flecha entre cada par de vértices distintos, tal se
muestra en la Figura 12 (Liu, 1995)

Material Básico pág. 10

Matemáticas Discretas – Unidad IV

Figura 12. Grafo completo. (Burgos, 2014)

2.5. Grafo conexo

Burgos (2014), enuncia que en matemáticas y ciencias de la computación es
aquel grafo que entre cualquier par de sus vértices existe un Camino (Grafo) que los
une.

Sea el grafo G = (A, B) donde a es el conjunto de los nodos o vértices y, b es la

colección de sus arcos o aristas. En dependencia de si es un grafo orientado o no
orientado, se dice que G es conexo si y solo si entre cualquier par de vértices (a, b)
de V existe un camino que comience en a y termine en b.

En el caso de los grafos no orientados simples que entre cualquier par de vértices existe
una arista que los une se hacen llamar grafos completos y los que |V |= K se
denominan Kn, observado en la Figura 13.

Figura 13. K20. (Burgos, 2014)

Por su parte, Grimaldi (1998) dice que un grafo G es conexo si existe un camino simple
entre cualesquiera dos vértices distintos de G.

Material Básico pág. 11

Matemáticas Discretas – Unidad IV

Si G = (V, E) es un grafo dirigido, su grafo no dirigido asociado es el grafo obtenido de

G si no se tienen en cuenta las direcciones de las aristas. Si se obtiene más de una
arista no dirigida de un par de vértices distintos de G, entonces sólo una de estas aristas
se dibuja en el grafo no dirigido asociado. Cuando este grafo asociado es conexo, se
considera que G es conexo.

Un grafo que no es conexo es disconexo, es decir, si dos o más de sus nodos

no están conectados por caminos simples.

Los grafos de las Figuras 14, 15 y 16 son conexos. En la Figura 15 el grafo no es conexo
ya que, por ejemplo, no hay un camino simple de a hasta e.

Figura 14. Grafo conexo. (Grimaldi, 1998)

Figura 15. Grafo conexo. (Grimaldi, 1998)

Material Básico pág. 12

Matemáticas Discretas – Unidad IV

Figura 16. Grafo conexo. (Burgos, 2014)

Figura 17. Grafo no conexo. (Grimaldi, 1998)

Así también en la Figura 17 se tiene un grafo no dirigido sobre 𝑉=

{𝑎 , 𝑏 , 𝑐, 𝑑, 𝑒, 𝑓, 𝑔}. Este grafo no es conexo dado que, no hay un camino simple de a
hasta e. Sin embargo, el grafo está compuesto por piezas donde los conjuntos de
vértices son 𝑉1 = {𝑎 , 𝑏 , 𝑐, 𝑑}, 𝑉2 = {𝑒 , 𝑓 , 𝑔} y los conjuntos de aristas son 𝐸1 =
{(𝑎 , 𝑏), (𝑎 , 𝑐), (𝑎 , 𝑑), (𝑏 , 𝑑)}, 𝐸2 = {𝑓, (𝑎 , 𝑐), (𝑓 , 𝑔)} que son conexos; estas piezas son
las componentes del grafo. Por lo tanto, un grafo no dirigido G = (V , E) es disconexo si
y sólo si V puede separase en al menos dos subconjuntos 𝑉1 y 𝑉2 tales que no haya una
arista en E de la forma (x , y) donde 𝑥 ∈ 𝑉1 , 𝑦 ∈ 𝑉2. Un grafo es conexo si y sólo si
tiene solamente una componente.

Material Básico pág. 13

Matemáticas Discretas – Unidad IV

Figura 18. Grafo no conexo. (Grimaldi, 1998)

2.5.1. Conexidad en grafos

Reseña Burgos (2014), que en los grafos dirigidos existen tres tipos de niveles de
conexidad por los que se llaman a los grafos como:

1. Conexos. Idéntico a la definición antes vista.

2. Débilmente conexos. Dígrafos que no son conexos pero que sus equivalentes
no orientados o sosías sí lo son. (Figura 19)
3. Fuertemente conexos. Grafos orientados que entre cualquier par de nodos
distintos existe un arco que los une. Mínimo deberá contener dos caminos de un
vértice a otro. Los grafos fuertemente conexos nunca son simples pues exige
que siempre entre un par de vértices exista un par de aristas, una de ida y otra
de vuelta. (Figura 20)

Figura 19. Dígrafo no conexo. (Burgos, 2014)

Material Básico pág. 14

Matemáticas Discretas – Unidad IV

Figura 20. Grafo fuertemente conexo. (Burgos, 2014)

2.6. Grado de un vértice

Sea G un grafo o multigrafo no dirigido. Para cualquier vértice v de G, el grado de v, es
el número de aristas en G que son incidentes con v. En este caso, un lazo o bucle en
un vértice v se considera como dos aristas incidentes en v, y contribuye con dos
unidades al grado del vértice, expone Grimaldi (1998).

Para Liu (1995), en un grafo cualquiera existe un número par de vértices de grado impar.
Dado que cada arista contribuye con 1 al grado de cada uno de los dos vértices con los
cuales es incidente, la suma de los grados de los vértices es igual al doble del número
de aristas de un grafo. Entonces, debe existir un número par de vértices de grado impar.

Para el grafo de la Figura 21, siguiendo a Grimaldi (1998) se tiene:

▪ grado(b) = grado(d) = grado(f) = grado(g) = 2, grado(c) = 4, grado(e) = 0 y

grado(h) = 1.
▪ Para el vértice a se tiene que grado(a) = 3 porque se cuenta el lazo dos veces.
Como h tiene grado 1, se le llama vértice colgante.

Para cualquier grafo o multigrafo no dirigido, el número de vértices de grado impar debe
ser par.

Figura 21. (Grimaldi, 1998)

Material Básico pág. 15

Matemáticas Discretas – Unidad IV

Ejemplo 3. Identifica los grados del grafo G dados en la figura.

Solución

Los grados del grafo G son:

g(A1) = 3; g(A2) = 5; g(A3) = 4; g(A4) = 5; g(A5) = 4; g(A6) = 0; g(A7) = 1.

3. ÁRBOLES
Un grafo G se dice que es un árbol si es un grafo conexo y no existe ningún circuito en
él. En un grafo con n vértices, los árboles tienen exactamente n – 1 aristas, tal se
observa en la Figura 22.

Figura 22. Este grafo tiene 9 vértices y 8 aristas. (Peña, 2013)

La importancia radica en que los árboles son grafos que conectan todos los vértices
utilizando el menor número posible de aristas.

Material Básico pág. 16

Matemáticas Discretas – Unidad IV

Un significativo campo de aplicación de su estudio se encuentra en el análisis

filogenético, el de la filiación de entidades que derivan unas de otras en un proceso
evolutivo, que se aplica sobre todo en la averiguación del parentesco entre especies,
aunque se ha usado también en el estudio del parentesco entre lenguas. (Peña, 2013)

Ejemplo 4. Grafos que son árboles

Figura 23. (ITESM, s/f)

Ejemplo 5. Grafos que no son árboles

Figura 24. (ITESM, s/f)

Material Básico pág. 17

Matemáticas Discretas – Unidad IV

4. MATRIZ DE ADYACENCIA DE UN GRAFO

Todo grafo simple puede ser representado por una matriz, que se denomina matriz de
adyacencia.

Se trata de matriz cuadrada de n filas por n columnas, siendo n el número de vértices

del grafo.

Para construir la matriz de adyacencia, cada elemento 𝒂𝒊𝒋 tomar el valor 1 cuando existe
una arista que une los vértices 𝑖 y 𝑗. En caso contrario el elemento 𝒂𝒊𝒋 asume el valor
0.

La matriz de adyacencia, entonces, estará formada por ceros y unos. (IES, s/f)

Ejemplo 5. Construir la matriz de adyacencia del siguiente grafo.

Solución
El grafo tiene 5 vértices, se tendrá una matriz de 5 filas y 5 columnas.
Se completa la primera fila de la matriz la del vértice 1, este vértice está conectado al 2
y al 4, por tanto, se coloca un 1 en las columnas 2 y 4, y un 0 en las demás, tal se
observa a continuación:

Se procede de igual forma con el resto de filas y así se obtiene la matriz de adyacencia:

Material Básico pág. 18

Matemáticas Discretas – Unidad IV

En la siguiente imagen puede observarse por ejemplo las conexiones entre el nodo 1 y
el nodo 4.

Imagen 1.

5. PASEOS Y CIRCUITOS
Refiere Liu (1995) que, en un grafo dirigido, un paseo es una sucesión de aristas
(𝑒1 , 𝑒2 , … , 𝑒𝑘 ) tal que el vértice terminal de una arista coincide con el vértice inicial de
otra. Se dice que un paseo es simple si no incluye la misma arista dos veces, y que un
paseo es elemental si no encuentra el mismo vértice dos veces.

Asimismo, Islas (2017) señala que un camino en un grafo es una sucesión finita en la
que aparecen alternadamente vértices y aristas de dicho grafo.

Coincide con Liu al manifestar que un camino es una secuencia de arcos en que el
extremo final de cada arco coincide con el extremo inicial del siguiente en la secuencia,
tal se observa en la Figura 25.

Figura 25. Un camino – marcado en color rojo. (Islas, 2017)

Con respecto al ciclo expresa el mismo autor que es un camino simple y cerrado.

Material Básico pág. 19

Matemáticas Discretas – Unidad IV

Figura 26. Un ciclo – marcado en color rojo. (Islas, 2017)

5.1. Paseos eulerianos y circuitos

Manifiesta Liu (1995) que Leonhard Euler se convirtió en el padre de la teoría de grafos
cuando demostró en 1736 que no era posible cruzar cada uno de los siete puentes sobre
el río Pregel en Königsberg, entonces Alemania, hoy Rusia, específicamente
Kaliningrado, una y sólo una vez durante una caminata turística. Un mapa de los puentes
de Königsberg se muestra en la Figura 27, el cual puede representarse por el grafo
expuesto en la Figura 28, donde las aristas representan los puentes y los vértices las
islas y las dos riberas. El problema de cruzar cada uno de los puentes de Königsberg
una y sólo una vez es equivalente al de encontrar un paseo en el grafo de la Figura 26
que pase a través de cada arista una y sólo una vez. Resulta ser, que en lugar de buscar
una solución usando la fuerza bruta por tanteos, lo cual probablemente es lo que los
habitantes de Königsberg hicieron, Euler descubrió un criterio muy simple para
determinar cuándo existe un paseo en un grafo que pase a través de cada arista una y
sólo una vez.

Figura 27. (Liu, 1995)

Material Básico pág. 20

Matemáticas Discretas – Unidad IV

Figura 28. (Liu, 1995)

Se define un paseo euleriano en un grafo como el paseo que pasa a través de cada lado
en el grafo una y sólo una vez. De modo similar, se define un circuito euleriano en un
grafo como un circuito que pasa a través de cada arista del grafo una y sólo una vez.

Para establecer una condición necesaria y suficiente para la existencia de paseos o

circuitos eulerianos en un grafo arbitrario, se precisa de la noción de grado de un vértice.

La existencia de paseos eulerianos o circuitos eulerianos en un grafo está relacionada

con los grados de los vértices.

Teorema 1. Un grafo no dirigido tiene un paseo euleriano si y sólo si éste es conexo y

tiene cero o dos vértices de grado impar.

Corolario 1.1. Un grafo no dirigido tiene un circuito euleriano si y sólo si es conexo y

sus vértices son todos de grado par.

Teorema 2. Un grafo dirigido tiene un circuito euleriano si y sólo si éste es conexo y el

grado de entrada de cualquier vértice es igual a su grado de salida. Un grafo dirigido
tiene un paseo euleriano si y sólo si es conexo y el grado de entrada de cualquier vértice
es igual a su grado de salida, con la posible excepción de dos vértices. Para estos dos
vértices, el grado de entrada de uno es mayor en uno que su grado de salida, y el grado
de entrada del otro es menor en uno que su grado de salida. (Liu, 1995)

5.2. Paseos y circuitos hamiltonianos

Un problema similar a la determinación de un paseo o circuito euleriano, es el de
determinar un paseo o un circuito que pasa a través de cada vértice en un grafo una y
sólo una vez.

Se define un paseo (circuito) hamiltoniano como un paseo (circuito) que pasa a través
de cada uno de los vértices de un grafo exactamente una vez.

Material Básico pág. 21

Matemáticas Discretas – Unidad IV

Sir William Hamilton inventó el juego “alrededor de todo el mundo” en el cual el jugador
es invitado a determinar una ruta a lo largo de un dodecaedro tal que pasará a través
de cada vértice una y sólo una vez.

A modo de ejemplo, se considera el problema de sentar un grupo de personas alrededor

de una mesa. Si se supone que los vértices de un grafo no dirigido denotan las personas
y las aristas denotan cuando dos personas sean amigas, un circuito hamiltoniano
corresponde a la manera de sentarlas de modo que cada una tenga un amigo a cada
lado.

Aunque el problema de determinar la existencia de circuitos o paseos hamiltonianos

tiene la misma connotación de que el de determinar la existencia de paseos o circuitos
eulerianos, no se conoce ninguna condición necesaria y suficiente. Para demostrar que
un grafo tiene un paseo o circuito hamiltoniano, puede tomarse en cuenta una
construcción explicita de dicho paseo o circuito. En el grafo de la Figura 29 las aristas
gruesas constituyen un circuito hamiltoniano.

Figura 29. (Liu, 1995)

Teorema 3. Sea G un grafo lineal de n vértices. Si la suma de los grados para cada par
de vértices de G es n – 1 o mayor, entonces existe un paseo hamiltoniano en G.

Teorema 4. Siempre existe un paseo hamiltoniano en un grafo dirigido completo. (Liu,

1995)

6. TEOREMA DE LOS CUATRO COLORES

Un problema relativo a los grafos, planteado por Francis Guthrie en 1852 fue el
siguiente: ¿cuántos colores son necesarios para dibujar un mapa político, con la
condición obvia que dos países adyacentes no puedan tener el mismo color?

Se supone que los países son de un solo pedazo, y que el mundo es esférico o plano.

Material Básico pág. 22

Matemáticas Discretas – Unidad IV

En un mundo en forma de toroide; el teorema siguiente no es válido: Cuatro colores son

siempre suficientes para colorear un mapa.

El mapa de la Figura 30 muestra que tres colores no bastan. Si se empieza por el país
central a y se esfuerza uno en utilizar el menor número de colores, entonces en la corona
alrededor de a alternan dos colores.

Figura 30. (Teoría de Grafos, 2012)

Llegando al país h se tiene que introducir un cuarto color. Lo mismo sucede en i si se

emplea el mismo método.

La forma precisa de cada país no importa; lo único relevante es saber qué país toca a
qué otro. Estos datos están incluidos en el grafo donde los vértices son los países y las
aristas conectan los que justamente son adyacentes. Entonces la cuestión equivale a
atribuir a cada vértice un color distinto del de sus vecinos.

Tres colores no son suficientes, y demostrar que con cinco siempre se llega, es bastante
fácil. Pero el teorema de los cuatro colores no es nada obvio. Prueba de ello es que se
han tenido que emplear ordenadores para acabar la demostración, para el efecto se ha
hecho un programa que permitió verificar una multitud de casos, lo que ahorró
muchísimo tiempo a los matemáticos. Fue la primera vez que la comunidad matemática
aceptó una demostración asistida por ordenador, lo que ha creado una fuerte polémica
dentro de la comunidad matemática, llegando en algunos casos a plantearse la cuestión

Material Básico pág. 23

Matemáticas Discretas – Unidad IV

de que esta demostración y su aceptación es uno de los momentos que han generado
una de las más terribles crisis en el mundo matemático. (Teoría de Grafos, 2012)

Expone Durán (2008), que a partir de cualquier mapa es posible construir un grafo donde
las regiones se representan por vértices y dos vértices son adyacentes si y solo si las
regiones correspondientes son limítrofes.

El grafo resultante es planar, es decir, se puede dibujar en el plano sin aristas que se
crucen, tal se observa en la Figura 31.

Así, conforme el Teorema de los Cuatro Colores los vértices de un grafo planar pueden
ser coloreados usando a lo sumo 4 colores y de manera tal que no haya dos vértices
adyacentes que reciban el mismo color.

Figura 31. (Durán, 2008)

7. UNAS APLICACIONES DE LOS GRAFOS

7.1. Grafos y redes de computadores
Presenta Álvarez (2013), que el principal problema de una red de computadores es
mantener una comunicación rápida y expedita entre todos los computadores y así
permitir que los mensajes viaje con fluidez entre cualquier lugar de la red y cualquier
punto de destino. El problema no se origina en la velocidad física de transmisión, que

Material Básico pág. 24

Matemáticas Discretas – Unidad IV

es la velocidad de la luz, sino en la forma que se ordena la red y el método de asignación

de caminos y prioridades para la enorme cantidad de mensajes que deben viajar por la
misma. Primero, es imprescindible que en todo momento se encuentre interconectada,
es decir, no exista ningún computador o grupo de computadores aislados por la red,
para evitar estos contratiempos se diseña la red de tal forma que cada computador tenga
con el resto al menos una vía alternativa de comunicación. Entonces, si un computador
abandona el servicio, otro puede remplazarlo en la tarea de transmitir mensajes.

Un segundo problema es la distribución de la carga de los mensajes. Existen momentos

críticos en que la cantidad de mensajes que fluyen por determinados caminos de la red
es excesiva para el soporte físico de ésta, en consecuencia, dichas zonas se convierten
en más lentas que el resto de la red; la solución es la asignación de vías alternativas,
que permiten desviar la carga.

Todas las situaciones descritas pueden ser analizados en forma abstractas con la teoría
de grafos y encontrarles una adecuada solución. Adecuadamente, es posible determinar
los puntos críticos de la red, la fluidez aproximada de la comunicación y el grado de
interconexión de los computadores.

7.2. El problema del cartero chino

La ruta ideal de un cartero inteligente que desea hacer bien su trabajo será aquella calle
sólo debe recorrer una vez. Si al recorrido de calles se asocia el grafo correspondiente
entonces lo ideal es buscar el circuito Euleriano. Pero si no existe, deberán repetirse
algunas calles procurando hacer las mínimas repeticiones. Esto fue estudiado por el
matemático chino Meigu Guan en 1962, se ha popularizado con el nombre de “El
problema del cartero chino”, expone Álvarez (2013),

Figura 32(a)

Figura 32(b)

Material Básico pág. 25

Matemáticas Discretas – Unidad IV

En la Figura 32(b) se puede notar que con el truco de introducir tan sólo una nueva arista
ya tiene un circuito Euleriano con la trayectoria indicada, en la que únicamente una calle
se recorre dos veces (5 y 6).

Este método se puede utilizar en otros contextos como en las empresas que deben
distribuir sus productos y quieren minimizar los recorridos y los tiempos empleados en
estas labores, entre otros.

7.3. Rutas del caballo en ajedrez

El popular tablero de ajedrez ha dado como pie a numerosos retos matemáticos. Un

problema clásico es fijar una de las fichas del juego (peón, alfil, rey, caballo, torre…) y
estudiar qué tipo de trayectorias puede hacer en el tablero moviéndose por supuesto de
acuerdo con las especiales características de desplazamientos que este tipo de figuras
tienen predeterminado. Resulta particularmente interesante el caso de los caballos y la
cuestión ¿es posible para un caballo de ajedrez hacer un recorrido en el tablero en el
que partiendo de un cuadrado pueda regresar al mismo habiendo recorrido todos los
cuadrados (64), pasando por todos ellos una sola vez?

Imagen 2.

La respuesta es sí y la buena noticia es que hay muchos caminos posibles. Este

problema, como muchos otros de ajedrez, se puede estudiar mediante teoría de grafos.
Cada cuadrado representa un vértice del grafo, cada movimiento del caballo equivale a

Material Básico pág. 26

Matemáticas Discretas – Unidad IV

una línea que une dos vértices de este grafo, cada movimiento del caballo equivale a
una línea que une dos vértices de este grafo (respetando la peculiar forma de los saltos)
y, por lo tanto, el reto es encontrar un tour hamiltoniano con salida y meta en el mismo
cuadrado. (Álvarez, 2013)

7.4. Búsqueda en Internet y la teoría de grafos

Los actuales algoritmos de búsqueda en Internet suponen una enorme ventaja en
comparación con los viejos algoritmos para lograr un mejor ordenamiento de las páginas
web al momento de realizar una determinada búsqueda. La obtención del vector de
importancia de equilibrio a partir de las relaciones existentes entre las páginas permite
ordenar las páginas web de una manera inmensamente más útil que aquella que se
puede lograr mediante un algoritmo de búsqueda basado en texto.

Se utiliza la teoría de grafos para brindar una representación de la red de páginas en

Internet con diagramas de grafos y sus matrices asociadas. Por otra parte, al concebir
la búsqueda web como un fenómeno aleatorio, la misma se puede abordar mediante los
conceptos de Cadenas de Markov, que se desarrollan dentro de la teoría de la
probabilidad y la estadística, y establece una fuerte dependencia entre que tenga lugar
un evento y un evento anterior. (Barriola – Dotta, 2015)

Material Básico pág. 27

Matemáticas Discretas – Unidad IV

BIBLIOGRAFÍA
Álvarez, M.; Parra, J. (2013). Teoría de Grafos. Trabajo de Grado. Universidad del Bío-
Bío. Chile. Recuperado de
http://repobib.ubiobio.cl/jspui/bitstream/123456789/1953/3/Alvarez_Nunez_Marc
elino.pdf.

Barriola, J.; Dotta, M. (2015). ¿Cómo funciona Google? El algoritmo pagerank,

diagramas de grafos y Cadenas de Markov. Revista Científica. Indexada.
Facultad de Ciencias Económicas UBA. Buenas Aires, Argentina. Recuperado e
http://www.economicas.uba.ar/wp-content/uploads/2016/04/2-
%C2%BFC%C3%B3mo-funciona-google_-el-algoritmo-pagerank-diagramas-
de-grafos-y-cadenas-de-markov.-Juan-Manuel-Barriola-y-Milena-Dotta-2.pdf.

Burgos, M. (2014). Matemática Discreta y Álgebra Lineal. Universidad de Granada.

España.

Cambariza, G. (2003). Una introducción a la Teoría de Grafos. Bogotá, Colombia.

Recuperado de
http://funes.uniandes.edu.co/6102/1/CombarizaUnaintroducci%C3%B3nGeometr
%C3%ADa2003.pdf.

Dubreil, M.L. (2003). Matemática Discreta. Barcelona: Reverté S.A.

Durán, G. (2008). Teoría de Grafos. Universidad de la República. Montevideo, Uruguay.

Recuperado de
http://cms.dm.uba.ar/academico/materias/2docuat2017/investigacion_operativa/2
017/curso_grafos.pdf.

Grimaldi, R. (1998). Matemática Discreta y Combinatoria. 3ª Edición. México: Pearson

Educación.

IES (s/f). Matemáticas. Recuperado de https://matematicasies.com/Matriz-de-

adyacencia-de-un-grafo.

Islas, L. (2018). Matemáticas Discretas. Apuntes Digitales. Universidad Autónoma del

Estado de Hidalgo. México. Recuperado de
http://cidecame.uaeh.edu.mx/lcc/mapa/PROYECTO/libro5/index.html.

Material Básico pág. 28

Matemáticas Discretas – Unidad IV

Liu, C. (1995). Elementos de Matemática Discreta. 2ª Edición. México: McGraw-Hill.

Peña, M.; Ferre, N. (2013). Grafos. Recuperado de

https://es.calameo.com/read/00206630437cfa4666eb6.

Teoría de Grafos. (2012). Universidad de Pamplona. Colombia. Recuperado de

http://www.unipamplona.edu.co/unipamplona/portalIG/home_23/recursos/general
/11072012/grafo3.pdf.

Material Básico pág. 29