Unidad 2 Grafos y arboles

Vista previa del material en texto

Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
1 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
2 
 
 
Tabla de contenidos 
 
UNIDAD 2. GRAFOS Y ÁRBOLES _______________________________________________________ 3 
Propósito de la unidad ______________________________________________________________ 3 
Competencia específica _____________________________________________________________ 4 
Presentación de la unidad ___________________________________________________________ 3 
 
2.1. Grafos ________________________________________________________________________ 4 
2.1.1. Clasificación de un grafo _______________________________________________________ 6 
Actividad 1. Áreas dónde se aplica la teoría de grafos _____________________________________ 9 
2.1.2. Representación de grafos ______________________________________________________ 9 
Actividad 2. Solución de problemas mediante la representación de grafos _____________________ 13 
Actividad 3. Matriz de adyacencia ____________________________________________________ 14 
 
2.2. Caminos y circuitos ____________________________________________________________ 14 
2.2.1. Terminología básica __________________________________________________________ 14 
2.2.2. Camino de Euler _____________________________________________________________ 16 
2.2.3. Circuitos de Euler ____________________________________________________________ 17 
2.2.4. Circuito de Hamilton __________________________________________________________ 18 
Actividad 4. Pozos ________________________________________________________________ 20 
2.2.5. Isomorfismo ________________________________________________________________ 20 
 
2.4. Árboles _______________________________________________________________________ 23 
2.3.1. Tipos de árboles _____________________________________________________________ 25 
Actividad 5. Árbol genealógico _______________________________________________________ 28 
Evidencia de aprendizaje. Grafo de rutina cotidiana ______________________________________ 29 
 
Cierre de la unidad _________________________________________________________________ 29 
Fuentes de consulta _______________________________________________________________ 29 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
3 
 
 
 
 
UNIDAD 2. GRAFOS Y ÁRBOLES 
 
 
Presentación de la unidad 
En esta unidad se proporciona una introducción formal a grafos y árboles. Estos temas son de fácil 
comprensión y sus conceptos se ilustran fácilmente con dibujos. Aunque la exposición del tema con 
frecuencia sea intuitiva, no es descuidada, a lo largo de esta unidad se va introduciendo la rigurosidad 
matemática. Sin embargo, se trató de desarrollar esta unidad de manera sencilla para adquirir práctica y 
sensibilidad hacia el tipo de problemas relacionados con las matemáticas discretas. 
 
En la presente unidad se describirá qué es y para qué es útil un grafo y un árbol, así como sus 
características; de la misma manera se describirá a los caminos y circuitos. 
 
 
Propósito de la unidad 
 
 
 
El propósito de esta unidad es presentar una parte de las 
matemáticas discretas que tiene que ver con la 
representación de situaciones o procesos mediante 
dibujos o diagramas para proporcionar información que 
permita un mayor análisis. 
 
 
 
 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
4 
 
Competencia específica 
 
 
 
 
 
 
Construir modelos de grafos para esquematizar conjuntos 
de datos relacionando estructuras mediante la teoría de 
grafos y árboles. 
 
 
2.1. Grafos 
Muchas situaciones de la vida real pueden ser esquematizadas por medio de diagramas construidos por 
puntos (vértices o nodos) y líneas (aristas o arcos) que conectan algunos pares de vértices, aunque 
eventualmente alguna línea puede unir un vértice consigo mismo. 
Estos esquemas, que facilitan la comprensión del problema a resolver, aparecen frecuentemente en 
disciplinas dispares y bajo nombres diversos, a saber: redes (en ingeniería, economía), sociogramas (en 
psicología), organigramas (en economía y planificación) así como diagramas de flujo (en programación). 
La teoría que se ocupa del estudio de estos diagramas o esquemas se le conoce con el nombre de teoría 
de grafos. 
La teoría de grafos desempeña un papel importante en varios campos de las ciencias, entre ellos ciencias 
de la conmutación, tales como la teoría de la conmutación y diseño lógico, inteligencia artificial, lenguajes 
formales, gráficos por computadora, sistemas operativos, escritura de compiladores y organización, así 
como en la recuperación de información. 
Como ya se mencionó, los grafos están formados por vértices que se unen entre sí mediante aristas, tal 
como se ilustra en la Figura 2.1. Por tanto, una definición matemática de grafo debe basarse en el conjunto 
de vértices y en el conjunto de aristas. Toda arista está asociada con dos vértices, esto es, existe una 
correspondencia entre las aristas y los pares de vértices. A continuación se da la definición formal de grafo. 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
5 
 
Figura 2.1. Grafo. 
 
 
 
 
 
La definición de grafo implica que a toda arista del grafo G se le puede asociar una pareja ordenada o 
desordenada de vértices del grafo. Si una arista e  A está asociada de esta forma con un par ordenado 
(u, v) o con un par desordenado {u, v}, en donde u, v  N, entonces se dice que la arista e conecta los 
vértices u y v. Se supondrá en todo momento que tanto el conjunto A como el conjunto N de un grafo son 
finitos. Con frecuencia es conveniente escribir los grafos en una forma abreviada G = (N, A), o bien 
simplemente como G. En el primer caso, cada arista se representa directamente como el par con el cual se 
corresponde, lo cual obvia la necesidad de especificar f si f es una correspondencia uno a uno. 
La definición de un grafo no contiene referencias de las longitudes o formas y posiciones de las aristas que 
puedan conectar pares de vértices, y tampoco estipula ningún orden de las posiciones de los vértices. Por 
tanto, para un grafo dado no existe un único diagrama que represente al grafo, y puede ocurrir que dos 
diagramas que tengan un aspecto completamente diferente entre sí representen un mismo grafo. 
En los siguientes temas se dará información precisa de algunos términos usados en la definición previa, 
para su mejor comprensión y estudio. 
Partes de un grafo 
Como se mencionó en la sección anterior, una grafo está compuesto por puntos (también llamado vértices 
o nodos) y líneas (también llamado aristas o arcos) que conectan algunos pares de vértices. Una parte 
importante de los grafos son las etiquetas, que identifican a las aristas y los vértices. Ver partes de un grafo 
en la Figura 2.2. 
En lo sucesivo utilizaremos los nombres de Vértices para referirnos alos puntos y Aristas para referirnos a 
las líneas. 
Definición: Un Grafo G = (N, A, f) consta de un conjunto no vacío N 
denominado conjunto de vértices del grafo, un conjunto A de aristas del grafo y 
una correspondencia f del conjunto de aristas A en un conjunto de pares 
ordenados o desordenados de N. Si una arista se corresponde con un par 
ordenado, entonces se dice que es una arista dirigida; en caso contrario, se 
denomina arista no dirigida. 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
6 
 
Figura 2.2. Partes de un grafo. 
2.1.1. Clasificación de un grafo 
 
 
 
 
 
 
En la Figura 2.3., se muestra un ejemplo de grafo dirigido (a), y un ejemplo de grafo no-dirigido (b). 
 
Figura 2.3. Grafo (a) dirigido y (b) no-dirigido. 
Una arista de un grafo que conecte un vértice o nodo consigo mismo se denominará bucle o lazo. La 
dirección de un bucle no es significativa; por tanto, se puede considerar como una arista dirigida o como 
una arista no-dirigida. Existen grafos que tienen más de una arista entre pares de nodos, estas aristas se 
denominan arista paralela. En el caso de aristas dirigidas, las aristas entre una pareja de vértices que 
tienen sentidos opuestos no se consideran paralelas. 
Todo grafo que contenga aristas paralelas se denominará multígrafo. Para este caso, la notación 
abreviada G = (N, A) no basta para representar los multígrafos, y se necesita la notación completa G = (N, 
A, f). Por otra parte, si no hay más de una arista entre pares de nodos, entonces el grafo se denomina 
grafo sencillo. 
En la Figura 2.4 se muestra un ejemplo de multígrafo no-dirigido (a), y un ejemplo de multígrafo dirigido (b), 
con bucle y aristas paralelas. 
En lo general, existen tres tipos de grafos: dirigidas, no-dirigidas y mixtas: 
 Dirigidas: si las aristas tienen un sentido concreto, lo cual se indica mediante una 
cabeza de flecha, entonces se dice que es un grafo dirigido o digrafo. 
 No-dirigidas: en este tipo de grafos las aristas no tienen un sentido. 
 Mixto: cuando en un grafo existen aristas dirigidas y aristas no-dirigidas. 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
7 
 
Figura 2.4. Multígrafo (a) no-dirigido y (b) dirigido, con bucle y aristas paralelas. 
Antes de continuar, se describen algunas definiciones de teoría de grafos que ayudarán a la comprensión y 
estudio de este tema en las secciones posteriores. 
Definiciones: 
 Los pares de vértices que estén conectados por una arista dentro de un grafo se denominan 
vértices adyacentes. 
 En un grafo, un vértice que no sea adyacente a ningún otro vértice se denominará Vértice aislado. 
 Un grafo que contenga solamente nodos aislados se denominará grafo nulo. Entonces, el conjunto 
de aristas, A, de un grafo nulo está vacío. 
 Los grafos en los que cada arista tiene asignado un peso se denominan grafos ponderados. 
 Un grafo no dirigido es conexo si para cualquier pareja de vértices del grafo se puede llegar hasta 
el otro vértice partiendo de cualquiera de ellos. 
Definición: En un grafo dirigido, para todo vértice v el número de aristas que tienen a v 
como vértice inicial se denomina grado de entrada del vértice v. El número de aristas que 
tienen a v como vértice terminal se denomina grado de salida, y la suma de ambos es lo 
que se denomina grado total del vértice v. De manera general, el grado total de un vértice v, 
δ(v), es el número de aristas dirigidas o no-dirigidas incidentes en v. El grado total de un 
vértice aislado es 0, y el de un vértice con bucle y sin otras aristas que incidan en él es 2. 
Definición: Sea N(H) el conjunto de vértices de un grafo H, y sea N(G) el conjunto de 
vértices de un grafo G tales que N(H)  N(G). Si además toda arista de H es también una 
arista de G, entonces se dice que el grafo H es un Subgrafo del grafo G, y esto se 
expresa en la forma H  G. 
 
 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
8 
La Figura 2.5 ilustra un ejemplo de subgrafo. Los grafos de la parte (b) son subgrafos de la parte (a). Se 
pueden obtener otros subgrafos borrando ciertos vértices y aristas de G. 
 
Figura 2.5. Grafo y algunos de sus subgrafos. 
También, se dice que un grafo G = (N, A) es completo si todos sus vértices son adyacentes a todos los 
vértices del grafo, es decir, existe una arista ente cada par de vértices distintos. Los grafos completos de n 
vértices se denotan en la forma Kn. La Figura 2.6 muestra los cinco primeros grafos completos. 
 
Figura 2.6. Grafos completos del 1 al 5. 
Un tipo de grafo sencillo es el bipartito. Un grafo G = (N, A) se denomina grafo bipartito si el conjunto de 
vértices N se puede separar en dos subconjuntos V1 y V2 de modo que cada arista en A sea incidente en 
un vértice de V1 y en un vértice de V2. Dicho de otro modo, que no haya dos vértices de V1 que sean 
adyacentes, ni tampoco dos vértices de V2 que sean adyacentes. 
El grafo ilustrado en la Figura 2.7. (a) es una grafo bipartito, ya que los dos subconjuntos disjuntos de 
vértices son V1 = {v1, v2} y V2 = {v3, v4, v5}, cada arista es incidente en un vértice de V1 y un vértice de V2. 
Por el contrario, la Figura 2.7. (b) no es un grafo bipartito, puesto que no es posible descomponer el 
conjunto N en dos subconjuntos disjuntos no vacíos. 
 
Figura 2.7. Grafo (a) bipartito y (b) no bipartito. 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
9 
Actividad 1. Áreas dónde se aplica la teoría de grafos 
Propósito 
Proporcionar ejemplos de campos donde es posible aplicar la teoría de grafos para representar situaciones 
y dar solución, ya sea en el ámbito científico o social. 
Instrucciones 
Responde en el foro las siguientes preguntas: 
 ¿En qué áreas del ámbito científico podemos aplicar los grafos? 
 
 ¿Será posible hacer grafos del funcionamiento del cuerpo humano? 
 
 ¿Será posible hacer un grafo de tu rutina diaria? 
 
 
2.1.2. Representación de grafos 
Hasta esta etapa, se ha representado a los grafos mediante diagramas/esquemas. En muchos casos, como 
por ejemplo, al utilizar una computadora para analizar un grafo, es necesaria una representación más 
formal. La representación más formal de un grafo es mediante su matriz de adyacencia, o mediante su 
matriz de incidencia. 
Matriz de adyacencia 
Para obtener la matriz de adyacencia, considerar el grafo de la Figura 2.8. Primero se debe elegir un orden 
para los vértices, por ejemplo: a, b, c, d, e. Posteriormente, construir una matriz y etiquetar los renglones y 
las columnas con los vértices ordenados. La entrada en esta matriz es un 1 si los vértices del renglón y la 
columna son adyacentes y 0 en caso contrario. 
 
Figura 2.8. Representación de un grafo. 
La matriz de adyacencia del grafo de la Figura 2.8., es la que a continuación se da: 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
10 
____ a b c d e
a
b
c
d
e
0 1 0 0 1
1 0 1 0 1
0 1 1 0 1
0 0 0 0 11 1 1 1 0
é
ë
ê
ê
ê
ê
ê
ê
ù
û
ú
ú
ú
ú
ú
ú
 
Obsérvese que se puede obtener el grado de un vértice v en un grafo sencillo sumando el renglón v o 
columna v en la matriz de adyacencia. Ejemplo: el grado total del vértice b es 3. Además, aunque la matriz 
de adyacencia permite representar bucles, no permite representar aristas paralelas; sin embargo, si 
modificamos la definición de una matriz de adyacencia para que ésta pueda contener enteros no negativos 
arbitrarios, podemos representar las aristas paralelas. En la matriz de adyacencia modificada, 
interpretamos la entrada ij-ésima especificando el número de aristas entre i y j. 
Considerar el grafo de la Figura 2.9 para obtener la matriz de adyacencia. Siguiendo la metodología del 
ejemplo anterior, la matriz de adyacencia es la que se muestra como A. 
 
Figura 2.9. Representación de un grafo. 
_______ a b c d e
A =
a
b
c
d
e
0 1 0 1 0
1 0 1 0 1
0 1 0 1 1
1 0 1 0 0
0 1 1 1 0
é
ë
ê
ê
ê
ê
ê
ê
ù
û
ú
ú
ú
ú
ú
ú
 
Utilizando el ejemplo previo, se mostrará que si A es la matriz de adyacencia de un grafo sencillo G, las 
potencias de A, 
A, A2, A3,…, 
cuentan el número de caminos de diversas longitudes. Más precisamente, si los vértices de G se etiquetan 
1, 2,…, la entrada ij-ésima en la matriz An es igual al número de caminos de i a j de longitud n. Por 
ejemplo, supón que se obtiene el cuadrado de la matriz A del ejemplo de la Figura 2.9. 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
11 
__________________________________________ a b c d e
A2 =
0 1 0 1 0
1 0 1 0 1
0 1 0 1 1
1 0 1 0 0
0 1 1 1 0
é
ë
ê
ê
ê
ê
ê
ê
ù
û
ú
ú
ú
ú
ú
ú
0 1 0 1 0
1 0 1 0 1
0 1 0 1 1
1 0 1 0 0
0 1 1 1 0
é
ë
ê
ê
ê
ê
ê
ê
ù
û
ú
ú
ú
ú
ú
ú
=
a
b
c
d
e
2 0 2 0 1
0 3 1 2 1
2 1 3 0 1
0 2 0 2 1
1 1 1 1 2
é
ë
ê
ê
ê
ê
ê
ê
ù
û
ú
ú
ú
ú
ú
ú
 
Considerar la entrada del renglón a, columna c en A2, obtenida al multiplicar por pares las entradas del 
renglón a por las entradas de la columna c de la matriz A y sumando: 
 
a 0 1 0 1 0( )
0
1
0
1
1
é
ë
ê
ê
ê
ê
ê
ê
ù
û
ú
ú
ú
ú
ú
ú
b
d
= 0·0 +1·1+ 0·0 +1·1+ 0·1= 2 
La única forma en que un producto distinto de cero podría aparecer en esta suma es cuando ambas 
entradas por multiplicar son iguales. En este ejemplo la suma es 2 pues existen dos caminos de longitud 2 
de a a c. 
(a, b, c) y (a, d, c) 
En general, la entrada en el renglón x y la columna y de la matriz A2 es el número de caminos de longitud 2 
del vértice x al vértice y. 
Las entradas de la diagonal de A2 proporcionan los grados de los vértices (cuando el grafo es sencillo). 
Considerar el vértice c en el ejemplo de la Figura 2.9. el grado de c es 3 pues c es incidente en las tres 
aristas (c, b), (c, d), (c, e). Pero cada una de estas aristas se puede convertir en un camino de longitud 2 de 
c a c. 
(c, b, c), (c, d, c) y (c, e, c) 
 
 
 
 
 
 
b d
c
Teorema: Si A es la matriz de adyacencia de un grafo 
sencillo, la entrada ij-ésima de An es igual al número de 
caminos de longitud n del vértice i al vértice j, n = 1, 2,… 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
12 
Matriz de incidencia 
Otra manera de representar un grafo es mediante la matriz de incidencia. Para obtener la matriz de 
incidencia, considera el grafo de la Figura 2.10. Primero se debe construir una matriz y etiquetar los 
renglones con los vértices y las columnas con las aristas en algún orden arbitrario. La entrada del renglón v 
y la columna e es 1 si e es incidente en v y 0 en caso contrario. 
 
Figura 2.10. Representación de un grafo. 
La matriz de incidencia del grafo de la Figura 2.10 es la que a continuación se da: 
___ e1 e2 e3 e4 e5 e6 e7
v1
v2
v3
v4
v5
1 1 1 0 0 0 0
0 0 1 1 1 0 1
0 0 0 0 0 1 0
1 1 0 1 0 0 0
0 0 0 0 1 1 0
é
ë
ê
ê
ê
ê
ê
ê
ù
û
ú
ú
ú
ú
ú
ú
 
La matriz de incidencia permite representar las aristas paralelas y los bucles. La columna como e7 
representa un bucle. Obsérvese que en un grafo sin bucles, cada columna tiene dos 1s y que la suma de 
los elementos de un renglón proporciona el grado del vértice identificado con ese renglón. Las aristas 
paralelas en este ejemplo son e1 y e2. 
Ejemplos complementarios de la sección 
Problema: elabora un grafo que represente un mapa de carreteras y ciudades, considera 5 ciudades (A, B, 
C, D, E), con las siguientes características: 1) hay dos rutas que unen las ciudades A y B, 2) no existe una 
ruta entre A y D, 3) existe un camino que pasa por B, C y D, 4) la ciudad E está aislada. 
Solución: Una posible solución al ejercicio, es la que se muestra en la Figura 2.11. Se usa un grafo no 
dirigido puesto que el problema no plantea alguna dirección para alguna carretera. Las aristas representan 
a las carreteras y los vértices representan a las ciudades. Para cumplir con el requisito 1), se usan aristas 
paralelas. 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
13 
 
Figura 2.11. Grafo representando un mapa de carreteras y ciudades. 
Problema: La Figura 2.12.a) muestra una parte del plano de una ciudad, en el cual las flechas denotan 
calles de dirección única. Elabora un grafo que represente esta parte del plano. Este grafo puede ser útil 
para los servicios de emergencia públicos, como los Bomberos y la Policía. 
Solución: Según el plano, existen calles con dirección única y otras que no, por lo tanto, el tipo de grafo 
requerido es mixto. Para este caso, las aristas representarán a las calles y los vértices representarán las 
esquinas o intersecciones entre calles. El grafo obtenido es el que se muestra en la Figura 2.12. (b). 
 
Figura 2.12. Representación gráfica del sistema de calles de una ciudad. 
Actividad 2. Solución de problemas mediante la representación de grafos 
Propósito 
Construir un grafo mediante un planteamiento dado. 
Instrucciones 
Karla, Manuel, Juan, Mónica, Eliangel e Iliana, van a subir a un juego mecánico en forma circular, se sabe 
que: 
 Karla conoce a Juan y a Mónica 
 Manuel conoce a Juan y a Eliangel 
 Iliana conoce a Eliangel y a Mónica 
 
 ¿Es posible sentarlos de forma que personas que estén sentadas juntas se conozcan? 
1. Construye un grafo dónde se represente la solución del planteamiento. 
2. Menciona el número de vértices del grafo que construiste. 
Envía tus resultados al Facilitador(a). 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
14 
 
Actividad 3. Matriz de adyacencia 
Propósito 
Representar con una matriz de adyacencia un grafo. 
Instrucciones 
Representa utilizando una matriz de adyacencia el siguiente grafo: 
 
Envía tus respuestas al Facilitador(a). 
 
2.2. Caminos y circuitos 
Si se piensan a los vértices de un grafo como ciudades y las aristas como carreteras, un camino corresponde a un 
viaje que comienza en cierta ciudad, pasa por varias ciudades y termina en alguna ciudad. A continuación se dan 
las definiciones formales de caminos y circuitos. 
2.2.1. Terminología básica 
 
 
 
 
 
Un ejemplo de camino sería: {(vi1 , vi2), (vi2 , vi3), …, (vik-2 , vik-1), (vik-1 , vik)} 
y se puede escribir de la siguiente forma: {(vi1, vi2 , …, vik-1 , vik)} 
 Un camino de un dígrafo en el cual todas las aristas sean distintas se denomina camino sencillo. 
 Un camino en el que todos los vértices sean diferentes se denomina camino elemental. 
 El número de aristas que aparecen en la sucesión de un camino se denomina longitud del camino. 
Definición: Sea G = (N, A, f) un dígrafo sencillo. Se dice que una 
sucesión de aristas es un Camino de G si y sólo si el vértice terminal, vt, 
de cada arista del camino es el vértice inicial, vi, de la próxima arista del 
camino. 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
15 
 
Figura 2.13. Grafo con distintos caminos. 
En la Figura 2.13., se muestra un dígrafo con una diversidad de caminos. Algunos caminos que surgen en el vértice 
1 y finalizan en el vértice 9 son: 
Camino 1: {1, 9} 
Camino 2: {1, 2, 3, 8, 1, 9} 
Camino 3: {1, 2, 4, 6, 7, 8, 1, 9} 
 
 
 
 
 
En un circuito el nodo inicial aparece al menos dos veces aun cuando se trate de un circuito elemental. 
Algunos circuitos presentes en el grafo de la Figura 2.13. son: 
Circuito 1: {1, 2, 3, 8, 1} 
Circuito 2: {1, 2, 4, 5, 7, 8, 1} 
Circuito 3: {1, 2, 3, 8, 1, 2, 3, 8, 1} 
Un grafo sencillo que no tenga ningún ciclo/circuito se denomina acíclico, naturalmente, los grafos acíclicos no 
pueden tener bucles; ver ejemplos en la Figura 2.14. 
Definición: Un camino que comienza y acaba en un mismo 
vértice se le denomina circuito o ciclo. Un circuito se 
denomina sencillo si ninguna arista del circuito aparece 
más de una vez en el camino y se denomina elemental si 
no pasa por ningún vértice más de una vez. 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
16 
 
Figura 2.14. Ejemplos de grafos acíclicos. 
La definición de camino requiere que las aristas que aparezcan en la sucesión tengan un vértice inicial y uno 
terminal bien definidos. En el caso de un grafo sencillo no-dirigido, una arista está dada por una pareja no 
ordenada, y cualquiera de los vértices de esa pareja no ordenada se puede considerar como vértice inicial o final 
de la arista. Para aplicar la misma definición de camino a un grafo no-dirigido, se puede considerar que todas las 
aristas del grafo no-dirigido se sustituirán por dos aristas dirigidas de sentidos opuestos. Una vez hecho esto, se 
tiene un grafo dirigido, y las definiciones de camino, circuito, etc., pueden ser aplicadas. 
2.2.2. Camino de Euler 
El Camino de Euler está definido como un camino a través del grafo G que recorre todas las aristas del 
grafo solamente una vez, pero que su vértice de inicio y final son diferentes. 
Para ejemplificar la anterior definición, analizamos el grafo de la Figura 2.15, el cual tiene un camino de 
Euler. El camino de Euler en dicho grafo es (4, 3, 5, 2, 3, 1, 2, 4, 5). Obsérvese que los vértices 4 y 5 tienen 
grado impar. 
 
Figura 2.15. Grafo con camino de Euler. 
Las condiciones para la existencia de un camino de Euler están dadas en el siguiente teorema. 
 
 
 
 
Teorema: Si G es un grafo y no tiene vértices aislados, entonces, este tiene 
un camino de Euler si y sólo si las siguientes dos propiedades se cumplen: 
1) El grafo G está conectado. 
2) El grafo tiene exactamente dos vértices de grado impar. 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
17 
Para comprobar dicho teorema, buscamos un camino de Euler en el grafo de la Figura 2.16. Este grafo está 
completamente conectado, es decir, no tiene vértices aislados, y tiene exactamente dos vértices de grado 
impar, vértice 2 y 6. Por lo que se puede suponer que el grafo tiene un camino de Euler. El camino de 
Euler en dicho grafo es (2, 5, 4, 1, 2, 3, 6, 5, 8, 4, 7, 8, 9, 6). 
 
Figura 2.16. Grafo con camino de Euler. 
2.2.3. Circuitos de Euler 
El primer artículo en teoría de grafos fue el escrito por Leonhard Euler en 1736. El artículo presentó una 
teoría general que incluía una solución a lo que ahora se llama el problema de los puentes de Königsberg. 
El problema de los puentes de Königsberg consiste en determinar un circuito a partir de un modelo gráfico 
representando a los puentes de Königsberg, que incluya todas las aristas y todos los vértices del grafo. 
Por lo tanto, en honor a Euler, un circuito de una grafo que incluya todas las aristas y todos los vértices de 
G se le denomina Circuito de Euler. 
De acuerdo a la sección anterior, un circuito de Euler debe cumplir con el siguiente teorema. 
 
 
 
 
 
 
Usamos el ejemplo de la Figura 2.17 para verificar si esté tiene un circuito de Euler. Observando el grafo se 
determina que es conexo, y como el grado de cada vértice es par, basados en el teorema previo decimos 
que el grafo tiene un circuito de Euler. 
Los grados de cada uno de los vértices son: 
 δ(v1) = δ(v2) = δ(v3) = δ(v5) = 4, δ(v4) = 6, δ(v6) = δ(v7) = 2. 
Teorema: Si G es un grafo conexo y todo vértice tiene grado par, entonces G tiene 
un circuito de Euler. 
O en su caso, 
Teorema: Si un grafo G tiene un circuito de Euler, entonces G es conexo y todo 
vértice tiene grado par. 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
18 
 
Figura 2.17. Grafo conexo con circuito de Euler. 
Por inspección se determina que el circuito Euler es el siguiente: 
(v6, v4, v7, v5, v1, v3, v4, v1, v2, v5, v4, v2, v3, v6). 
2.2.4. Circuito de Hamilton 
Sir William Rowan Hamilton lanzó al mercado a mediados del siglo XIX un juego en forma de dodecaedro 
(ver Figura 2.18a). Cada esquina llevaba el nombre de una ciudad y el problema era partir de cualquier 
ciudad, recorrer las aristas, visitar cada ciudad exactamente una vez, y regresar a la ciudad inicial. El grafo 
de las aristas del dodecaedro se muestra en la Figura 2.18b. Entonces, podemos resolver el juego de 
Hamilton si podemos determinar un circuito en el grafo de la Figura 2.18b que contenga a cada vértice solo 
una vez, excepto por el vértice inicial y final que aparece dos veces. 
 
Figura 2.18. (a) Juego de Hamilton, (b) Grafo del juego de Hamilton. 
Por lo tanto, en honor de Hamilton, se dice que un circuito en un grafo G que contenga cada vértice solo 
una vez, excepto por el vértice inicial y final que aparece dos veces, es un circuito Hamiltoniano. 
Una solución al grafo del juego de Hamilton se ilustra en la Figura 2.19. 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
19 
 
Figura 2.19. Solución al juego de Hamilton. 
El problema de determinar un circuito Hamiltoniano en un grafo parece similar al de determinar un circuito 
de Euler. Un circuito de Euler visita cada arista una vez, mientras que un circuito Hamiltoniano visita cada 
vértice una vez; sin embargo, en realidad estos problemas son un poco distintos. Además, a diferencia de 
los circuitos de Euler, no se conocen condiciones necesarias y suficientes fácilmente verificables para la 
existencia de un circuito Hamiltoniano en un grafo. 
Los siguientes ejemplos muestran casos de grafos con un circuitoHamiltoniano y otro que no lo tiene. El 
grafo de la Figura 2.20a tiene un circuito Hamiltoniano, el circuito (1, 2, 3, 4, 5, 1) es un circuito 
Hamiltoniano. El grafo de la Figura 2.20b no tiene un circuito Hamiltoniano; para producir un circuito 
Hamiltoniano en este grafo será necesario eliminar dos aristas, una incidente en el vértice v2 y otra 
incidente en el vértice v4. 
 
Figura 2.20. Grafo (a) con circuito Hamiltoniano, y (b) sin circuito Hamiltoniano. 
 
 
 
 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
20 
Actividad 4. Pozos 
Propósito 
Representar un grafo mediante un planeamiento. 
Instrucciones 
 
1. Resuelve lo que se te indica: 
 
 Se tiene tres casas y tres pozos. Intenta dibujar senderos que unan cada casa con 
cada pozo de tal manera que no se crucen. 
 
2.2.5. Isomorfismo 
Definición: Dos grafos G1 y G2 son Isomorfos si existe una función uno a uno y sobre, f, de 
los vértices de G1 a los vértices de G2 y una función uno a uno y sobre, g, de las aristas de G1 
a las aristas de G2, de modo que una arista e es incidente en v y w en G1 si y sólo si la arista 
g(e) es incidente en f(v) y f(w) en G2. El par de funciones f y g es un Isomorfismo de G1 
sobre G2 . 
Dicho de manera menos abstracta, dos grafos son Isomorfos si tienen una estructura idéntica, aunque sean 
representados gráficamente de manera diferente; o , dos grafos son Isomorfos si existe un renombramiento 
de los vértices de los grafos tal que ambos sean idénticos. 
En el ejemplo dado en la Figura 2.21, se muestran dos grafos isomorfos, ambos tienen una estructura 
idéntica aunque gráficamente son representados de manera diferente, y aunque tengan nombres de 
vértices diferentes. 
 
Figura 2.21. Grafos isomorfos. 
Un isomorfismo para los grafos de la Figura 2.21 se define como 
f(a) = A, f(b) = B, f(c) = C, f(d) = D, f(e) = E 
g(xi) = yi, i = 1, …, 5. 
 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
21 
 
 
 
 
Para ejemplificar dicho teorema, daremos las matrices de adyacencia de los grafos mostrados en la Figura 
2.21. La matriz de adyacencia del grafo de la Figura 2.21a con respecto del orden de los vértices a, b, c, 
d, e, es el siguiente: 
 
 
 
 
 
 
Y se puede observar que es igual a la matriz de adyacencia del grafo de la Figura 2.21b con respecto del 
orden de los vértices A, B, C, D, E, que es el siguiente: 
 
 
 
 
 
Por lo tanto, ambos grafos de la Figura 2.21 son isomorfos. 
Lo siguiente es una forma de demostrar que dos grafos sencillos G1 y G2 no son isomorfos. Se determina 
una propiedad de G1 que G2 no tenga, pero que G2 tendría si G1 y G2 fuesen isomorfas. Tal propiedad 
es un invariante. Más precisamente, una propiedad P es un invariante, si siempre que G1 y G2 sean 
grafos isomorfos. 
 Si G1 tiene la propiedad P, entonces G2 también tiene la propiedad P. 
Según la definición previa de Isomorfismo, si dos grafos G1 y G2 son isomorfos, entonces existen funciones 
uno a uno y sobre de las aristas de G1 en las aristas de G2. Así, si G1 y G2 son isomorfos, entonces G1 y G2 
tienen el mismo número de aristas y el mismo número de vértices. Por tanto, si e y n son enteros no 
negativos, las propiedades “tiene e aristas” y “tiene n vértices” son invariantes. 
____ a b c d e
a
b
c
d
e
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
é
ë
ê
ê
ê
ê
ê
ê
ù
û
ú
ú
ú
ú
ú
ú
___ A B C D E
A
B
C
D
E
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
é
ë
ê
ê
ê
ê
ê
ê
ù
û
ú
ú
ú
ú
ú
ú
Teorema: Dos grafos sencillos G1 y G2 son isomorfos 
si y sólo si para cierto orden de sus vértices, las 
matrices de adyacencia son iguales. 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
22 
 
Para ilustrar la propiedad de invariante, se hace uso de los grafos de la Figura 2.22. Los grafos de la Figura 
2.22 no son isomorfos, pues el grafo de la Figura 2.22a tiene siete aristas y el grafo de la Figura 2.22b 
tiene seis aristas, y “tener siete aristas” es un invariante. 
 
Figura 2.22. Grafos no isomorfos. 
Ejemplos complementarios de la sección 
Ejemplo: De un conjunto de caminos dados, pertenecientes al grafo ilustrado en la Figura 2.23, identificar si 
es un camino sencillo, o si es un circuito, o un circuito sencillo. Aplicando las definiciones y teoremas 
descritos en la sección, los resultados son los que se muestran en la tabla siguiente. 
 
Figura 2.23. Grafo no-dirigido. 
Camino ¿Es un camino 
sencillo? 
¿Es un circuito? ¿Es un circuito 
sencillo? 
(6, 5, 2, 4, 3, 2, 1) NO NO NO 
(6, 5, 2, 4) SI NO NO 
(2, 6, 5, 2, 4, 3, 2) NO SI NO 
(5, 6, 2, 5) NO SI SI 
(7) SI NO NO 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
23 
2.4. Árboles 
Los árboles forman una subclase de grafo de uso amplio. Los árboles se utilizan en muchos otros campos 
de aplicación. Por ejemplo, en ciencias de la computación, desglosar problemas complejos y representarlos 
mediante una estructura en forma de árbol, son algunas de las aplicaciones. 
En general, hay dos grupos de árboles, los árboles libres y los árboles con raíz. Un árbol libre es una clase 
especial de grafo no dirigido, y un árbol con raíz es un caso especial de un grafo dirigido. 
Definición 
 Un Árbol Libre T es un grafo sencillo no dirigido que es a la vez conexo y acíclico, es 
decir, es un grafo que no contiene circuitos o ciclos y todos sus pares de vértices 
están conectados. 
 Un Árbol con Raíz es un árbol en el cual un vértice particular se designa como la raíz. 
Propiedades de un árbol 
Teorema: Todo árbol que contenga n vértices debe de tener n-1 aristas. 
En las Figura 2.24 se muestra varios ejemplos de árboles libres, los cuales cumplen con su definición y con 
el teorema previo. En la Figura 2.25 se muestra un ejemplo típico de árbol con raíz, el cual tiene un vértice 
definido como tal. 
 
 
 
Figura 2.24. Ejemplos de árboles libres. 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
24 
 
Figura 2.25. Ejemplo de árbol con raíz. 
Como el camino sencillo de la raíz a cualquier vértice es único, cada vértice está en un nivel determinado 
de manera única. Decimos que el nivel de la raíz es el nivel 0. Los vértices de bajo de la raíz están en un 
nivel 1, y así sucesivamente. Así, el nivel de un vértice v es la longitud del camino sencillo de la raíz a v. La 
altura de un árbol con raíz es el número máximo de nivel que aparece en dicho árbol. 
Ejemplo: Examinando el árbol T mostrado en la Figura 2.26a y designando al vértice e como el vértice raíz, 
se obtiene el árbol con raíz T’ mostrado en la Figura 2.26b. Los vértices a, b, c, d, e, f, g, h, i, j están en los 
niveles 2, 1, 2, 1, 0, 1, 1, 2, 2, 3, respectivamente. La altura del árbol T’ es 3. 
 
 
 
Figura 2.26. (a) Un árbol T y (b) un árbol con raíz T’. T’ se obtiene de T designado a e como la raíz. 
Con frecuencia, un árbolcon raíz se utiliza para especificar relaciones jerárquicas. Cuando un árbol se 
utiliza de esta manera, si el vértice a está en el siguiente nivel arriba del vértice b y a y b son 
adyacentes, entonces a está “justo arriba” de b y existe una relación lógica entre a y b: a domina a b 
o b está subordinado a a de alguna manera. Un ejemplo de árbol con raíz especificando relación 
jerárquica, es el que se muestra en la Figura 2.27, es un organigrama de una universidad. 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
25 
Presidente
Vice-Presidente
académico
Vice-Presidente
admistrativo
Decano de 
Artes
Decano de 
Ciencias
Director de 
Planeación
Director de 
Adquisición
Jefe de 
Danza
Jefe de 
Física
 
Figura 2.27. Ejemplo de organigrama. 
2.3.1. Tipos de árboles 
Árbol de expansión 
Un problema importante que está asociado a una red representada por un grafo consiste en obtener un 
árbol de expansión para el grafo. Este árbol de expansión debe contener todos los vértices del grafo y 
algunas de sus aristas, para asegurar su conectividad. 
Definición: Un Árbol de Expansión de un grafo conexo no dirigido G = (N, A) es un árbol libre 
con el conjunto de vértices N que es un subgrafo de G; esto es, un árbol de expansión es 
conexo, acíclico y tiene a todo N como vértices y aparte de A como conjunto de aristas. 
 
Teorema: Un grafo G tiene un árbol de expansión si y sólo si G es conexo. 
Hay muchos enfoques para generar un árbol de expansión correspondiente a un grafo dado. Un enfoque 
consiste en eliminar las aristas que pertenezcan a circuitos uno tras otro hasta que no queden circuitos en 
el grafo. Si solo se eliminan aristas de circuitos, entonces el grafo seguirá siendo conexo, y esto es esencial 
para la generación de un árbol de expansión. 
Un ejemplo de este enfoque se ilustra en la Figura 2.28, En este caso se decide eliminar los pares de 
aristas siguientes: {2, 5}, {2, 6}, {3, 6}, {3, 7}, {4, 7}, {6, 7}. Obsérvese que se podrían generar muchos 
árboles de expansión a partir del grafo dado. 
1 3
5
2
76
4
1 3
5
2
76
4
 
Figura 2.28. Ejemplo de obtención de un árbol de expansión a partir de un grafo. 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
26 
Árbol binario 
Otra clase de árbol es el árbol binario. Los árboles binarios son de los tipos particulares más importantes de 
árboles con raíz. Cada vértice de un árbol binario tiene a lo más dos hijos. Además, cada hijo se designa 
como hijo izquierdo o como hijo derecho. Al trazar un árbol binario, un hijo izquierdo se dibuja a la izquierda 
y un hijo derecho se dibuja a la derecha. La definición formal de árbol se da a continuación. 
Definición: Un Árbol Binario es un árbol con raíz en el cual cada vértice tiene cero, uno, o dos 
hijos. Si un vértice tiene un hijo, ese vértice se designa como un hijo izquierdo o como un hijo 
derecho, pero no ambos. Si un vértice tiene dos hijos, uno de ellos se designa como hijo 
izquierdo y el otro como hijo derecho. 
En la Figura 2.29 se muestra un ejemplo de árbol binario. El vértice b es el hijo izquierdo y el vértice c es el 
hijo derecho del vértice a. El vértice d es el hijo derecho del vértice b; el vértice b no tiene hijo izquierdo. El 
vértice e es el hijo izquierdo del vértice c; el vértice c no tiene un hijo derecho. 
 
 
Figura 2.29. Árbol binario. 
El árbol binario completo es un árbol binario en el cual cada vértice tiene dos o cero hijos. Un resultado 
fundamental acerca de los árboles binarios completos es el siguiente teorema. 
Teorema: Si T es un árbol binario completo con i vértices internos, entonces T tiene i+1 
vértices terminales y 2i + 1 vértices en total. El vértice raíz es considerado un vértice interno. 
Isomorfismo 
Al igual que los grafos, los árboles también presentan la propiedad de isomorfismo. Como un árbol libre es 
un grafo sencillo, los árboles T1 y T2 son isomorfos si y sólo si existe una función, f , uno a uno y sobre el 
conjunto de vértices de T1 al conjunto de vértices de T2 que preserva la relación de adyacencia, en el 
sentido de que los vértices vi y vj son adyacentes en T1 si y sólo si los vértices f(vi) y f(vj) son 
adyacentes en T2. 
Ejemplo: La Figura 2.30 muestra un caso de isomorfismo. La función f del conjunto de vértices del árbol T1 
al conjunto de vértices del árbol T2 es una función uno a uno, sobre, que preserva la relación de 
adyacencia. Por lo tanto, los árboles T1 y T2 son isomorfos. 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
27 
f(a) = A, f(b) = B, f(c) = C, f(d) = D, f(e) = E 
 
Figura 2.30. Árboles libres isomorfos. 
Al igual que en el caso de grafos, se puede mostrar que dos árboles no son isomorfos si exhiben un 
invariante no compartido por los árboles. Esto se puede ilustrar en la Figura 2.31. los árboles T1 y T2 no 
son isomorfos, pues T2 tiene un vértice x de grado 3, pero T1 no tiene un vértice de grado 3. 
 
 
Figura 2.31. Árboles libres no isomorfos. 
Definición: Sea T1 un árbol con raíz r1 y sea T2 un árbol con raíz r2. Los árboles con raíz T1 
y T2 son isomorfos si existe una función f, uno a uno y sobre el conjunto de vértices de T1 en el 
conjunto de vértices de T2 tal que 
a) Los vértices vi y vj son adyacentes en T1 si y sólo si los vértices f(vi) y f(vj) son 
adyacentes en T2. 
b) f(vi) = r2. 
Decimos que la función f es un isomorfismo. 
A continuación, se dan dos ejemplos de árboles con raíz para identificar si tienen la propiedad de 
isomorfismo. 
Los árboles con raíz de la Figura 2.32 son isomorfos. Un isomorfismo es 
f(a) = A, f(b) = B, f(c) = C, f(d) = D, f(e) = E, f(f) = F, f(g) = G 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
28 
 
Figura 2.32. Árboles con raíz isomorfos. 
 
 
Los árboles con raíz de la Figura 2.33 no son isomorfos, pues la raíz de T1 tiene grado 3 y la raíz de T2 
tiene grado 2. Estos árboles son isomorfos como árboles libres. 
 
Figura 2.33. Árboles con raíz no isomorfos. * Los árboles son isomorfos como árboles libres. 
Actividad 5. Árbol genealógico 
Propósito 
Representar una secuencia genealógica utilizando árboles. 
Instrucción 
Utiliza un árbol para representar la secuencia genealógica de tu familia desde tus bisabuelos hasta la última 
generación 
Envía tu árbol al Facilitador(a). 
 
 
 
 
 
 
 
 
Matemáticas discretas 
Unidad 2. Grafos y árboles 
 
 
 
 Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 
29 
 
Evidencia de aprendizaje. Grafo de rutina cotidiana 
Instrucciones 
Realiza un grafo de tu rutina diaria con al menos 10 actividades desde que te levantas de tu cama en la 
mañana hasta que regresas a ella por la noche. 
 
1. Usa un grafo simple para describir las actividades de un día normal. Las actividades 
corresponderán a los vértices y se unirán mediante arcos. 
2. Utiliza flechas en los arcos para indicar cómo se van desarrollando las actividades.3. Resuelve cuál es el grado de cada vértice del grafo. 
4. Usa una matriz de adyacencia para representar el grafo. 
 
 
Cierre de la unidad 
Es necesario tener a la mano papel y lápiz para poder resolver algunas operaciones, una recomendación 
es utilizar el software Paint de Office para poder hacer los grafos. 
Fuentes de consulta 
 McEliece, R. (1989). Introduction to discrete mathematics. New York: Random House. 
 Skiena, S. (1990). Implementing discrete mathematics: Combinatoric and graph theory with 
mathematica. California: Addison-Wesley Pub. Co. 
 Grassmann, W. & García, B. (2003). Matemática discreta y lógica. Madrid: Pearson Educación, S.A. 
 Johnsonbaugh, R. & Palmas, V. (1999). Matemáticas discretas (4ª ed.). México: Prentice Hall-
Hispanoamericana, S. A.