1

Gobierno del Estado de México

Secretaría de Educación, Cultura y Bienestar
Social
Subsecretaría de Educación Media Superior y
Superior

Tecnológico de Estudios Superiores del Oriente del Estado de México

Organismo Público Descentralizado del Gobierno del Estado de México

ELABORÓ: MAT. JORGE GARCIA NIEVA

México,D.F;Mayo del 2005.
 2

CONTENIDO

UNIDAD TEMAS SUBTEMAS PAGINAS

I Lógica 1.1 Proposiciones. 7
Matemática. • Proposiciones simples
y compuestas.
• Términos de enlace de
proposiciones y de los términos de
enlace.
• Simbolización de proposiciones y
de los términos de enlace.
1.2 Tipos de proposiciones. 8
• Conjunción, Negación.
• Disyunción, condicional y
bicondicional.
1.3 Término de enlace dominante 9
1.4 Fórmulas lógicas.
• Valores de certeza de una 10
proposición.
• Tablas de verdad de las
proposiciones moleculares
básicas. 13
• Tautología.
• Contradicción.

1.5 Diagramas Lineales.

• Reglas de inferencia.
• Inferencias válidas y no válidas.
• Demostraciones directas,
condicionales por contradicción y
por inducción.

II. Relacioaciones. 2.1 Concepto de relación. 31

• Relaciones binarias.
• Relaciones de equivalencia.
• Clases de equivalencia y
particiones.
 3

III. Funciones. 3.1 Definición de funciones.

• Composición de funciones. 39
• Clases de funciones:
Inyectivas.
Suprayectivas.
Biyectivas.
• Funciones inversas.
• Funciones localizadoras.
4.1 Grafos. 49
IV. Teoría de • Nodos.
grafos. • Ramas y lazos.
• Valencia.
• Caminos.
• Ramas paralelas.
• Grafos simples.
• Grafos de similaridad.
• Grafos bipartidos y Grafos
completos.
4.2 Representación matricial de grafos. 53
• Ramas sucesivas de longitud “n”.
• Matriz de adyacencia e incidencia
• Caminos.
• Caminos simples.

4.3 Grafos conexos. 55

• Caminos de Euler y Hamilton.
• Componentes de un grafo.

4.4 Grafos ponderados. 60

• Longitud de un camino.
• Camino más corto.
• Dos problemas clásicos.
“El problema de los puentes de
Konigsberg”.
.
• Grafos isomorfos.
• Grafos planos.
• Grafos homeomorfos.
• Teoremas de Kuratowski y de
Euler.

5.1 Definición de un árbol.

72
• Propiedad de los árboles.
V.
Árboles. • Árboles simples.
• Árboles con raíz.
• Árboles jerárquicos. El problema
 4
de las ocho monedas.
• Código de Huffman.
• Árboles binarios.
• Árboles binarios completos.
• Altura de un árbol.
• Árboles binarios de búsqueda.
• Bosques.
• Árboles generadores.
• Búsquedas “a lo largo” y “a lo
ancho”.
“ El problema de las cuatro
reinas”.
• Árboles generadores minimales.
81
5.2 Teorema de PRIM.
5.3Algoritmos voraces.
• Recorrido con orden inicial,
intermedio y final.
• Representaciones interfijas.
• Representaciones totalmente
parentéticas.
• Representaciones prefija o
notación polaca.
• Notación polaca inversa.
• Ordenamientos.
• Árboles de juego.

Bibliografía 99
5
6
 7

INTRODUCCIÓN

La Matemática Discreta, no obstante que tuvo su origen ya hace muchos años (en 1700) ,
sigue siendo una de las ramas de la matemática superior con mayor variación de autor a
autor en cuanto a conceptos y simbología usados, lo cual es muy preocupante porque la
presentación de la materia en el salón de clases entonces se vuelve dependiente del profesor
que la exponga ( o del libro que use para auxiliarse en sus clases). El resultado de esta falta
de uniformidad en el uso de simbología y conceptos hace que los alumnos que presentan
exámenes extraordinarios, por ejemplo, hechos por un profesor o grupos de profesores
distintos al que le impartió la materia ,se confundan y en consecuencia reprueben la
asignatura, quizás no por falta de conocimientos, sino por esta variedad de símbolos y
conceptos que existen dentro de esta disciplina.
Con el objetivo de apoyar a los alumnos en su autoaprendizaje, así como en sus tareas, y
además con la finalidad de uniformizar la simbología, los conceptos y los temas abordados
en la materia de Matemáticas Discretas en el TESOEM, presentamos estos apuntes, los
cuales fueron posibilitados en parte con el apoyo económico de el tiempo de academia,
destinado con tal fin por la Dirección del Instituto Tecnológico de Estudios Superiores Del
Estado de México.
Estos apuntes, son el resultado de los cursos que el autor ha impartido en este instituto y en
otras escuelas de educación superior sobre el tema , de modo que para su elaboración se
ha auxiliado con sus anotaciones , consultas bibliográficas y en ejercicios y discusiones que
ha hecho con los alumnos durante los mismos.
Agradezco antes que a nadie a mi esposa Sandra Villaverde su colaboración en la difícil
tarea de la captura de este trabajo, así como su constante motivación y su paciencia al estar
trabajando en este proyecto. Agradezco también el interés de las autoridades del TESOEM
en que se lleve a cabo este tipo de actividades, pensando en apoyar a nuestros alumnos en
su preparación y en ofrecerles una educación de mayor calidad. También agradezco a los
alumnos sus críticas, sugerencias y participación durante las clases.

Mat. Jorge García Nieva.

México,D.F;Mayo del 2005.
 8

UNIDAD I

LÓGICA MATEMÁTICA

Objetivos:

Al finalizar la unidad, el alumno :

 Solucionará problemas relacionados con la lógica matemática.

 Identificará los diferentes tipos de proposiciones compuestas que existen.
 Identificará la tabla de verdad asociada a cada tipo de proposición.
 Comprenderá el método de demostración mediante las leyes de la lógica y la
relación de este método con las tablas de verdad.
 Entenderá el concepto de demostración por inducción.
 9
INTRODUCCIÓN
En esta unidad trataremos conceptos básicos de Lógica Matemática, los cuales resultan de
gran importancia para aquellos especialistas que trabajen con computadoras; por ejemplo,
los operadores lógicos los utiliza el programador para imponer condiciones en la ejecución
de rutinas en sus programas y también resultan de gran relevancia en el diseño de los
circuitos (compuertas lógicas) de los instrumentos electrónicos, entre otras aplicaciones.
En este capítulo, interesa también que el estudiante de ingeniería en sistemas sea
introducido al concepto de demostración formal con la finalidad de que desarrolle el
pensamiento estructurado o axiomático, lo cual tiene enorme importancia para este tipo de
profesionistas ya que la mayor parte de su trabajo lo llevan a cabo interconectando en
forma lógica una gran cantidad de datos, hechos y procedimientos. De hecho, la Lógica
Matemática es el modo exacto de hablar en la Ciencia. 1

1.1 PROPOSICIONES

Una proposición es una oración afirmativa que se puede calificar de verdadera o falsa.
En base a las proposiciones se forman las teorías científicas; debido a ello, es muy
importante determinar las condiciones y la forma bajo las cuales se debe calificar de cierta
o falsa una afirmación hecha en la Ciencia. 1

EJEMPLO 1.1
1.-El agua hierve a 100° a una altura de 100 metros sobre el nivel del mar.
2.-El agua es un elemento que se forma con 2 átomos de de Hidrógeno y 1 de Oxígeno.
3.-La gasolina es inflamable.
Estos ejemplos son proposiciones que se les puede calificar directamente como verdaderas
o falsas; a este tipo de proposiciones se les llama simples , atómicas o primitivas, debido a
que no hay manera de descomponerlas en algo más sencillo.
Denotaremos a las proposiciones simples con letras minúsculas como son p,q,r,s,t,...
Las oraciones siguientes :

(a)¡Ah, caramba!
(b)¿Te gusta el helado de chocolate?

No son proposiciones, porque no afirman , sino que exclaman o preguntan. Otro ejemplo de
una oración que no es una proposición es:
Las señoras son generalmente gordas.

1
El primer estudio sistemático del razonamiento lógico se encuentra en la obra del filósofo griego Aristóteles
((384-322 A.C), quien presentó una serie de principios para el razonamiento deductivo; es sin embargo al
matemático alemán G.W. Leibniz ((1646-1716) quien es considerado el primero en intentar desarrollar a la
lógica simbólica como un lenguaje científico universal en su obra De Arte Combinatoria ( 1666).
 10
Esta no es una proposición, no obstante que está disfrazada como si lo fuera, debido a que
no tiene el mismo sentido para todos la palabra “gorda”.

EJERCICIO 1.1

Dar cinco ejemplos de proposiciones simples

Dar cinco ejemplos de oraciones que no sean proposiciones; es decir que no se les pueda
calificar de verdaderas o falsas.
A partir de proposiciones simples, podemos obtener otras más complejas: las
proposiciones compuestas o moleculares.

1.2 TIPOS DE PROPOSICIONES.

Son oraciones que se forman con dos o más proposiciones simples. Para formarlas, a las
proposiciones simples se les enlaza mediante los CONECTIVOS LÓGICOS, como son:

CONECTIVO NOMBRE FORMA DE LEERLO

CONJUNCIÓN p∧q pyq

DISYUNCIÓN p∨q Póq

INCLUSIVA
NEGACIÓN ¬p No p

CONDICIONAL p→q p implica q

BICONDICIONAL p↔q p si y sólo si q

DISYUNCIÓN p∨ q y/o
EXCLUSIVA

Para calificar de verdaderas o falsas cualquiera de estas proposiciones debemos seguir las
tablas siguientes:

Conjunción Disyunción Implicación Bicondicional Disyunción Negación

inclusiva o o doble exclusiva
condicional implicación
p q p∧ q p∨q p→ q p↔ q p∨q ¬p
V V V V V V F F
V F F V F F V F
F V F V V F V V
F F F F V V F V

Dichas tablas constituyen formalmente la definición de los conectivos lógicos.

 11
Nota: Se puede demostrar que la tabla de verdad de una proposición compuesta que
contenga n proposiciones simples debe tener exactamente 2 n renglones. Esto debe
tomarse en cuenta al momento de construir la tabla de verdad de dicha proposición
compuesta.

1.3 TERMINO DE ENLACE DOMINANTE

En una proposición compuesta la precedencia de las operaciones se marcan con la ayuda de

paréntesis; por ejemplo en ¬[ p ∧ (¬q )] → [(¬r ) ∨ q ] , se está indicando que lo primero que
se debe ejecutar es ¬q , enseguida ya se podrá ejecutar todo lo que está dentro del
corchete; y una vez ejecutado esto, se puede efectuar la negación ¬ . Hasta ese momento
se ha efectuado toda la operación compuesta a la izquierda del operador → . Enseguida se
efectúa la operación a la derecha de dicho operador . Es en este sentido que → es el
término de enlace dominante, porque es el operador que se ejecuta al final de una
operación. Para distinguirlo, debe seguir las siguientes reglas:
(1)Si aparecen solamente operadores ∧ u operadores ∨ , entonces cualquiera de ellos
puede ser considerado como el término de enlace dominante.
Por ejemplo , en ( p ∨ q ∨ r ) ∧ ( p ∨ t ∨ ¬q ) ∧ ( p ∨ ¬t ∨ r ) , se le puede entender como
( p ∨ q ∨ r ) ∧ [( p ∨ t ∨ ¬q ) ∧ ( p ∨ ¬t ∨ r )]
(2)Un operador ¬ puede ir a la derecha de cualquier otro operador sin necesidad de usar
paréntesis; como en p ∨ ¬t ∨ r o bien en ¬( p ∨ ¬q ) → ¬p
(3)En cualquier otro caso que no sean (1) y (2) se debe utilizar paréntesis para indicar la
precedencia de los operadores.

Teniendo en cuanta las reglas anteriores; se le llama Término de Enlace Dominante

al operador que ejecutaría al último en una operación lógica dada.
EJEMPLO 1.2
Hacer la tabla de verdad para cada una de las siguientes composiciones compuestas;
indicando en cada caso el término de enlace dominante.

1.- ( p ∨ q ) ∧ (¬r ) . Debe tener 2 3 = 8 filas, porque hay tres letras. Término de enlace
dominante: ∧ .

p Q r p∨q ¬r ( p ∨ q ) ∧ (¬r )
V V V V F F
V V F V V V
V F V V F F
V F F V V V
F V V V F F
F V F V V V
F F V F F F
F F F F V F
 12
2.- ¬( p ∨ ¬q ) → ¬p . Debe tener 2 2 = 4 filas . Término de enlace dominante: →
p Q ¬q ( p ∨ ¬q ) ¬( p ∨ ¬q ) ¬p ¬( p ∨ ¬q ) → ¬p
V V F V F F V
V F V V F F V
F V F F V V V
F F V V F V V

3.- (¬p ∨ q ) ∧ ¬( p ∨ r ) .Debe tener 2 3 filas. Término de enlace dominante: ∧

p Q r ¬p ¬p ∨ q p∨r ¬( p ∨ r ) (¬p ∨ q ) ∧ ¬( p ∨ r )
V V V F V F V V
V V F F V V F F
V F V F F F V F
V F F F F V F F
F V V V V V F F
F V F V V F V V
F F V V V V F F
F F F V V F V V

EJERCICIOS 1.2. Construya una tabal de verdad para cada una de las siguientes
proposiciones compuestas; p, q y r denotan proposiciones simples o primitivas.
(a) ¬( p ∨ ¬q ) → ¬p (b) [( p → q ) ∧ (q → r )] → ( p → r ) © q ↔ ( ¬p ∨ ¬q )
(d) [ p ∧ ( p → q )] → q

1.4 TAUTOLOGIAS Y CONTRADICCIONES.

TAUTOLOGIA:
Una proposición compuesta es una tautología si bajo cualquier asignación de valores de
verdad para sus proposiciones componentes siempre resulta verdadera. Denotaremos a una
tautología con el símbolo T0 .
CONTRADICCIÓN:
Una contradicción es una proposición compuesta que resulta falsa bajo cualquier
asignación de valores de verdad para sus proposiciones simples. Denotaremos a una
contradicción con el símbolo F0 .
Entenderemos a estos símbolos como los vectores siguientes
T0 = (V , V , V ,...) y Fo = ( F , F , F ,...)
EJEMPLO 1.3
1.- Verificar que es tautología la proposición siguiente
 13
( p → q ) ↔ (¬p ∨ q )
Solución:
P q p→q ¬p (¬p ∨ q ) ( p → q ) ↔ (¬p ∨ q )
V V V F V V
V F F F F V
F V V V V V
F F V V V V

En efecto es una tautología, porque se obtuvo sólo verdadero al final de la tabla.

2.- Verificar que la proposición ¬[(¬p ∧ ¬q ) → ¬( p ∨ q )] es una contradicción.
Solución:

p q ¬p ¬q (¬p ∧ ¬q ) ( p ∨ q ) ¬( p ∨ q ) (¬p ∧ ¬q ) → ¬( p ∨ q ) ¬[(¬p ∧ ¬q ) → ( p ∨ q )]

V V F F F V F V F
V F F V F V F V F
F V V F F V F V F
F F V V V F V V F

Es una contradicción porque se obtuvo sólo falso al final de la tabla.

3.- Ver si la proposición [( p → q ) ∧ (q → r )] → ( p → r ) es tautología, contradicción o
ninguna de las dos.
p q r ( p → q ) (q → r ) ( p → q ) ∧ (q → r ) ( p → r ) [( p → q ) ∧ (q → r )] → ( p → r )
V V V V V V V V
V V F V F F F V
V F V F V F V V
V F F F V F F V
F V V V V V V V
F V F V F F V V
F F V V V V V V
F F F V V V V V

Este ejercicio corresponde a una tautología .

PROPOSICIONES LÓGICAMENTE EQUIVALENTES.
Dos proposiciones p y q son lógicamente equivalentes si ambas tienen la misma tabla
de verdad , o bien si p ↔ q es una tautología. Esta situación la denotamos con el
símbolo p ≡ q .
 14
EJEMPLO 1.3
1.- Verificar que p → q es lógicamente equivalente con ¬p ∨ q ; es decir

[( p → q ) ↔ ( ¬p ∨ q )] ≡ T0 .

p Q p→q ¬p ¬p ∨ q
V V V F V
V F F F F
F V V V V
F F V V V

2.-Verificar si lógicamente equivalentes

p ↔ q y ( p → q ) ∧ (q → p )

Solución:
p q p↔q p→q q→ p ( p → q ) ∧ (q → p )
V V V V V V
V F F F V F
F V F V F F
F F V V V V
Sí son lógicamente equivalentes, porque coinciden la tercera y la última columnas.
CONTRAPOSITIVAS, RECIPROCAS E INVERSAS.
Considere la implicación p → q ,entonces:
A la proposición ¬q → ¬p se le llama contrapositiva de p → q .
A la proposición q → p se le llama recíproca de p → q .
A ¬p → ¬q se le llama inversa del p → q
Nota: En Matemáticas y Filosofía a p se le llama “antecedente” y a q se le llama
“consecuente”.
EJEMPLOS. Obtener la recíproca, las inversa y la contrapositiva de las siguientes
proposiciones:
1.- p: Juan va al lago de Téxcoco.
q: María comprara los boletos para el cine.
a) Obtener p → q .
Si Juan va al lago de Téxcoco María comprara los boletos para el cine.
b) Contrapositiva.
Si María no compra los boletos para el cine, entonces Juan no irá al lago de Téxcoco.
c) Reciproca.
Si María compra los boletos para el cine , entonces Juan irá al lago de Texcoco.
d)Inversa.
 15
Si Juan no va al Lago de Texcoco, entonces María no comprará los boletos para el
cine.
2.- p: Estudio.
q: Apruebo.
(a) Contrapositiva: Si no apruebo , entonces no estudio.
(b)Inversa : Si no estudio ,entonces no apruebo.
c) Recíproca: Si apruebo ,entonces estudio.

A la contrapositiva de una implicación se le utiliza en Matemáticas ( y en general en

la Ciencia) para hacer demostraciones llamadas “por contradicción”: si al
consecuente se le supone falso, entonces necesariamente según esta regla, el
antecedente debería también resultar falso, si no es así, se obtendría la veracidad de
p → q . Este es un tema que abordaremos posteriormente en esta misma unidad.
EJERCICIO 1.3. Demostrar que p → q es lógicamente equivalente con ¬q → ¬p ,
usando una tabla de verdad.

1.5. LAS LEYES DE LA LÓGICA Y LAS REGLAS DE INFERENCIA

En base a los conceptos de equivalencia lógica , tautología y contradicción , podemos

formular las siguientes reglas del pensamiento lógico, conocidas como Leyes de la Lógica.
En sí, representan un sistema axiomático que nos permite generar a lo que se llama el
Álgebra de Proposiciones, de modo que cualquier propiedad operativa que tengan las
proposiciones es consecuencia de estas propiedades básicas, así como cualquier propiedad
operativa ulterior que tengan los números reales es consecuencia de las propiedades de
campo, de orden y de completez que poseen. 2
Al ejemplificar el uso de estas reglas lógicas, de paso trataremos el tema de las
demostraciones.
LEYES DE LA LÓGICA .
Para cualesquiera proposiciones primitivas p, q y r, cualquier tautología To y cualquier
contradicción F 0 se cumplen las siguientes leyes o propiedades de las operaciones con
proposiciones:
1.- Ley de la doble negación.
¬¬p = q

2 .-Leyes De Morgan
¬( p ∧ q) ≡ ¬p ∨ ¬q
¬( p ∨ q) ≡ ¬p ∧ ¬q

2
Estas reglas aparecieron en los trabajos de los matemáticos ingleses George Boole(1815-1864) y Augustus
De Morgan (1806-1871) en sus respectivas obras The Mathematical Analisis of Logic ,Being an Essays
Towards a Calculus of Deductive Reasoning y Formal Logic ; or the Calculus of Inference ,Necessary
and Probable.
 16
3.- Leyes Conmutativas.
p∨q ≡ q∨ p
p∧q ≡q∧ p

4.- Leyes Asociativas

p ∨ q ∨ r ≡ p ∨ (q ∨ r ) ≡ ( p ∨ q ) ∨ r
p ∧ q ∧ r ≡ p ∧ (q ∧ r ) ≡ ( p ∧ q ) ∧ r .

5.-Leyes Distributivas
p ∨ (q ∧ r ) ≡ ( p ∨ q ) ∧ ( p ∨ r ) .
p ∧ (q ∨ r ) ≡ ( p ∧ q ) ∨ ( p ∧ r )

6.- Leyes Idempotentes

p∨ p ≡ p
p∧ p≡ p

7.- Leyes del Neutro

p ∨ Fo ≡ p
p ∧ To ≡ p

8 .-Leyes Inversas
p ∨ ¬p ≡ To
p ∧ ¬p ≡ Fo

9.- Leyes de Dominación

p ∨ To ≡ To
p ∧ Fo ≡ Fo

10 .-Leyes de Absorción
p ∨ ( p ∧ q ≡ p)
p ∧ ( p ∨ q) ≡ p

EJEMPLO 1.4. Usando las leyes de la lógica demostrar lo siguiente:

a) ( p ∨ q ) ∧ ¬(¬p ∧ q ) ≡ p
 17

solución:
PROPOSICIÓN RAZÓN

( p ∨ q ) ∧ ¬(¬p ∧ q ) DADA
≡ ( p ∨ q ) ∧ (¬¬p ∨ ¬q ) LEY DE MORGAN
≡ ( p ∨ q ) ∧ ( p ∧ ¬q ) DOBLE NEGACIÓN
≡ p ∨ (q ∧ ¬q ) LEY DISTRIBUTIVA
≡ p ∨ Fo LEY INVERSA
≡p NEUTRO

2.- Demostrar que ¬[¬[( p ∨ q ) ∧ r ] ∨ ¬q ] ≡ q ∧ r

solución:

PROPOSICIÓN RAZÓN

¬[¬[( p ∨ q ) ∧ r ] ∨ ¬q ] DADA
≡ [(q ∧ r ) ∧ p ] ∨ (q ∧ r ) ¬¬[( p ∨ q ) ∧ r ] ∧ ¬¬q LEY DE MORGAN
≡ [( p ∨ q ) ∧ r ] ∧ q
DOBLE NEGACIÓN
LEY DISTRIBUTIVA
≡ [[(r ∧ p )] ∨ [(r ∧ q )]] ∧ q LEY DISTRIBUTIVA
≡ [q ∧ (r ∧ p )] ∨ [q ∧ (r ∧ q )] LEY CONMUTATIVA
≡ [(q ∧ r ) ∧ p ] ∨ (q ∧ r ) LEY ASOCIATIVA
≡q∧r LEY DE ABSORCIÓN

3.- Demostrar que p ∨ q ∨ (¬p ∧ ¬q ∧ r ) ≡ p ∨ q ∨ r

p ∨ q ∨ ( ¬ ( p ∨ q ) ∧ r )  ≡ LEY DE MORGAN, LEY ASOCIATIVA.

s ∨ [ ¬s ∧ r ] ≡ LEY DE CERRADURA con s ≡ p ∨ q
( s ∨ ¬s ) ∧ ( s ∨ r ) ≡ LEY DISTRIBUTIVA.
To ∧ (s ∨ r ) ≡ LEY DE INVERSAS.
s∨r ≡ p∨q∨r LEY DEL NEUTRO Y DE SUSTITUCIÓN.
 18

4.-Demostrar que ( ¬p ∨ ¬p ) → ( p ∧ q ∧ r )  ≡ p ∨ q

PROPOSI CIONES RAZÓN
( ¬p ∨ ¬p ) → ( p ∧ q ∧ r ) ≡ DADA

( ¬p ) → ( p ∧ q ) ∧ r  ≡ LEY INDEMPOTENTE.

( ¬¬p ) ∨ ( p ∧ q ) ∧ r  ≡ LEY ASOCIATIVA.
( p ) ∨  p ∧ ( q ∧ r )  ≡ DOBLE NEGACIÓN
( p ∨ s ) ∧ ( p ∨ r )  ≡ LEY DISTRIBUTIVA Ó CERRADURA.
[ p ∨ ( p ∧ q )] ∧ ( p ∨ r ) LEY DE SUSTITUCIÓN.

5.- p → (q ∧ r ) ≡ [( p → q ) ∧ ( p → r )]
ANTES: RECORDAR QUE p → q ≡ ¬p ∨ q ( son lógicamente equivalentes)
PROPOSICIONES RAZÓN
p → (q ∧ r ) ≡ DADA
¬p ∨ ( q ∧ r ) ≡ LEY SUSTITUCIÓN
[(¬p ∨ q ) ∧ (¬p ∨ r ) ≡ ( p → q ) ∧ ( p → r )] LEY DISTRIBUTIVA.
( p → q) ∧ ( p → r )

6.- Demostrar que [( p ∨ q ) → r ] ≡ [( p → r ) ∧ (q → r )]

PROPOSICIONES RAZÓN
[¬( p ∨ q ) ∨ r ] DADA
(¬p ∧ ¬q ) ∨ r LEY DE MORGAN.
(¬p ∨ q ) ∧ (¬q ∨ r ) LEY DISTRIBUTIVA.
( p → r ) ∧ (q → r ) ≡ LEY DE SUSTITUCIÓN

REGLAS DE INFERENCIA Y LA VALIDEZ O INVALIDEZ DE UN

ARGUMENTO:
Generalmente, al demostrar que una proposición compuesta es equivalente a otra o que un
argumento dado es válido ó es falso (falacia),nos podemos valer de tres herramientas: las
tablas de verdad, las Leyes de la Lógica y además de las Reglas de Inferencia , las cuales
pueden ser expresadas en realidad en forma de implicación lógica de la manera mostrada
en la siguiente tabla:
 19

REGLA DE IMPLICACIÓN LÓGICA RELACIONADA NOMBRE DE LA

INFERENCIA REGLA
p  p ∧ ( p → q )  → q Regla de
p→q separación.
∴q

2) p → q Ley de silogismo.
( p → q ∧ )( q → r )  → ( p → r )
q→r
∴p→r

3) p → q
( p → q ) ∧ ¬q  → ¬p Modus Tollens.
¬q
∴ ¬p

4) p p∧q→ p∧q Regla de la

q conjunción.
∴p∧q

5) p ∨ q Reglas del
¬p ( p ∨ q ) ∧ ¬q  → q silogismo
disyuntivo.
∴q
Regla de
6)
¬p → F0 ( ¬p → F0 ) → p contradicción.
∴p

Regla de

7)
p∧q ( p ∧ q) → p simplificación
conjuntiva.
∴p

p → p∨q Regla de
p amplificación
8)
∴p∨q disyuntiva.

9) p ∧ q Regla de
( p ∧ q ) ∧  p → ( q → r )   → r
p → (q → r ) demostración
condicional.
∴r

10) p → r
( p → r ) ∧ ( q → r )  → ( p ∨ q ) → r  Regla de
demostración por
 20
q→r casos.
∴( p ∨ q) → r

11) p → q
( p → q ) ∧ ( r → s ) ∧ ( p ∨ r )  → ( q ∨ s ) Regla del dilema
r→s constructivo.
p∨r
∴q ∨ s

12) p → q
( p → q ) ∧ ( r → s ) ∧ ( ¬q ∨ ¬s )  → ( ¬p ∨ ¬r ) Regla del dilema
r→s
¬q ∨ ¬s destructivo.
∴ ¬p ∨ ¬r

Diremos que un argumento es válido si la conclusión del mismo se desprende lógicamente

de las premisas dadas para obtenerlo. Esta situación se denota simbólicamente por
p1 , p1  , pn  q
Formalmente esto significa que q es una consecuencia de las premisas p1 , p2 ,... pn , si
siendo dichas premisas verdaderas, q también lo es, en caso contrario la argumentación es
una falacia.
Los siguientes ejemplos nos muestran la forma de aplicar las reglas enumeradas junto con
otros resultados como las leyes de la lógica para probar la validez o invalidez de un
argumento:

EJEMPLO 1.5
1.- Demostrar la validez del argumento.

p→r
¬p → q
q→s
∴ ¬r → s

PASOS RAZONES

1) p → r Premisa.
2) ¬r → ¬p Paso (1) y p → r ≡ ¬r → ¬p .
3) ¬p → q Premisa.
4) p ∨ q Paso (2) y (3) y la ley del silogismo.
5) q → s Premisa.
6)∴ ¬r → s Paso (4) y (5) y la ley del silogismo

Una segunda forma de justificar el argumento es la siguiente.

 21
PASOS RAZONES.

1) p → r Premisa
2) q → s Premisa
3) ¬p → q Premisa
4) p ∨ q Paso (3) y ( ¬p → q ) ≡ ( ¬¬p ∨ q ) ≡ ( p ∨ q )
5) r ∨ s Paso (1),(2) y (4) y la regla del dilema constructivo
6) ∴ ¬r → s Paso (5) y ( r ∨ s ) ≡ ( ¬¬r ∨ s ) ≡ ( ¬r → s ) , donde
usamos la ley de la doble negación en la primera
equivalencia lógica

2.- Establezca la validez del argumento.

p→q
q → (r ∧ s)
¬r ∨ ( ¬t ∨ u )
p∧t
∴u

PASOS RAZONES.

1) p → q Premisa
2) q → ( r ∧ s ) Premisa
3) q → ( r ∧ s ) Pasos (1) y (2) y la ley del silogismo
4) p∧t Premisa
5) p Paso (4) y la regla de la simplificación conjuntiva
6) r∧s Paso (5) y (3) y Modus Ponens
7) r Paso(6) y la regla de la simplificación conjuntiva
8) ¬r ∨ ( ¬t ∨ u ) Premisa
9) ¬r ∧ ( ¬t ∨ u ) Paso (8), y la propiedad asociativa de ∨ y las leyes De
Morgan
10) t Paso (4) y la ley de la simplificación conjuntiva
11) r ∧ t Pasos (7) y (10) y la regla de la conjunción.
12∴ u Pasos (9) y (11) y la regla del silogismo disyuntivo

3) Este ejercicio nos muestra que el siguiente argumento es válido.

Si alguno de los muchachos de nuestro grupo de amigos no pudiera aprobar todas
sus materias o el salón de fiestas no se contratara a tiempo a tiempo, entonces la fiesta
de graduación tendría que cancelarse y Lupita se enojaría. Si la fiesta de graduación
 22
se cancelara, habría que devolver el dinero. No se devolvió el dinero. Por lo tanto,
todos los chicos aprobaron sus materias.
Primero convertiremos el argumento dado en una forma simbólica mediante la
siguiente asignación de proposiciones.
p : Todos los chicos aprobaron sus materias
q : Se contrató un salón a tiempo.
r : La fiesta de graduación se canceló.
s : Lupita estaba enojada.
t : Hubo que devolver el dinero.

El argumento anterior se escribe como

( ¬p ∨ ¬q ) → ( r ∧ s )
r →t
¬t

∴p

Ahora establezcamos la validez de este argumento como sigue:

PASOS RAZONES

1) r →t Premisa
2) ¬t Premisa
3) ¬r Paso (1),(2) y Modus Tollens
4) ¬r ∨ s Paso (3) y la regla de amplificación disyuntiva
5) ¬(r ∨ s ) Paso (4) y la leyes De Morgan
6) ( ¬p ∨ ¬q ) → ( r ∧ s ) Premisa
7) ¬ ( ¬p ∨ ¬q ) Paso (6), (5) y Modus Tollens

8) p ∧ q Paso (7) , Leyes de De Morgan y la Ley de la

doble negación
9)∴ p Paso (8) y la regla de simplificación conjuntiva

4) En este caso utilizaremos el Método de Demostración por Contradicción.

Consideremos el argumento:

¬p ↔ q
q→r
∴p
 23

Para establecer la validez de este argumento, hemos supuesto la negación ¬p de la

conclusión p como otra premisa. El objetivo ahora es usar las cuatro premisas para obtener
una contradicción F0 . He aquí una forma de obtenerla.
PASOS RAZONES

1) ¬p ↔ q Premisa
2) ( ¬p → q ) ∧ ( q → ¬p ) Paso (1) y ( ¬p ↔ q ) ⇔ ( ¬p → q ) ∧ ( q → ¬p ) 
3) ¬p → q Paso (2) y la regla de la simplificación conjuntiva
4) p → q Premisa
5) ¬p → r Paso (3), (4) y la ley del silogismo
6) ¬p Premisa que hemos propuesto
7) r Paso (5),(6) y Modus Ponens
8) ¬r Premisa
9) r ∧ ¬r ( ⇔ F0 ) Paso (7), (8) y la regla de conjunción
10) ∴ p Pasos (6), (9) y el método de demostración por
contradicción.

Nota. (Implicación lógica). si p y q son proposiciones arbitrarias tal que p → q

es una tautología , entonces decimos que p implica lógicamente a q y escribimos
p⇒q.

Por ejemplo: Si analizamos lo que ocurrió en el ejercicio anterior, tenemos que

( ¬p ↔ q ) ∧ ( q → r ) ∧ ¬∧
r ¬⇒
p  F0 .

Esto quiere decir que el valor de verdad de ( ¬p ↔ q ) ∧ ( q → r ) ∧ ¬r ∧ ¬p  sea 0. Como

¬p ↔ q, q → r y r son las premisas dadas, cada una de estas proposiciones tiene el valor
de verdad 1. En consecuencia, para que
( ¬p ↔ q ) ∧ ( q → r ) ∧ ¬r ∧ ¬p  tenga el valor de verdad 0, la proposición ¬p debe
tener el valor de verdad 0. Por lo tanto p tienen el valor de verdad 1 y la conclusión p del
argumento es verdadera.
3.- Consideremos las proposiciones primitivas p, q, r , s y t , y el argumento.
p
p∨q
q → (r → s)
t→r

∴ ¬s → ¬t
 24
Para mostrar que este argumento no es válido, necesitamos una asignación de valores de
verdad para cada una de las proposiciones p, q, r , s y t , de modo que la conclusión
¬s → ¬t sea falsa (tenga el valor de verdad 0) mientras que las cuatro premisas sean
verdaderas (tengan el valor de verdad 1). El único caso en que la conclusión ¬s → ¬t es
falsa se presenta cuando ¬s es verdad y ¬t es falsa. Esto implica que el valor de verdad de
s es 0 y el valor de verdad de t es 1.
Como p es una de las premisas, su valor de verdad debe de ser 1.Para que la premisa
p ∨ q tenga el valor de 1, q puede ser verdad (1) o falsa (0). Consideremos la premisa
t → r , donde sabemos que t es verdadera. Si t → r debe ser verdadera , entonces r debe
ser verdadera (tener el valor de verdad 1). Ahora bien, si r es verdadera (1) y s es falsa
(0), tenemos que r → s es falsa (0) y el valor de verdad de la premisa q → ( r → s ) será 1
únicamente cuando q sea falsa (0).

En consecuencia, con la asignación de los valores de verdad:

p :1 q : 0 r :1 s : 0 t :1 ,
las cuatro premisas
p p∨q q → (r → s) t→r
tienen el valor de verdad 1, mientras que la conclusión
¬s → ¬t
tienen el valor de verdad 0. En este caso hemos mostrado que el argumento dado no es
válido.
Las asignaciones de valores de verdad de p :1, q : 0, r :1, s : 0 y t :1 muestran un caso que
desaprueba algo que podría haberse considerado como un argumento válido. Debemos
observar que, para mostrar que una implicación de la forma
( p1 ∧ p2 ∧ p3 ∧ ... ∧ pn ) → q representa un argumento válido, necesitamos considerar
todos los casos en que la premisas p1 , p2 .... pn sean verdaderas [Cada uno de estos casos es
una asignación de valores de verdad para las proposiciones primitivas( que conforman las
premisas en que p1 , p2 , p3 .... pn son verdaderas). Para lograr esto (analizar todos los casos
sin escribir las tablas de verdad), hemos utilizados las reglas de inferencia junto con la leyes
de la lógica y otras equivalencias lógicas. Para analizar todos los casos necesarios, no
podemos recurrir a un solo ejemplo (o caso) específico como medio para establecerla
validez del argumento (para todos los casos posibles). Sin embargo, cuando queremos
mostrar que una implicación (de la forma anterior) no es una tautología, todo lo que
debemos hacer es encontrar un caso para el que la implicación sea falsa; es decir, un caso
en el que todas las premisas sean verdaderas pero que la conclusión sea falsa. Este caso
proporciona un contraejemplo para el argumento y muestra que no es válido.
 25
EJERCICIO 1.5
1.- Los siguientes tres argumentos son válidos. Establezca la validez de cada uno por el
método de una tabla de verdad. En cada caso, determinar las filas de la tabla que son
cruciales para evaluar la validez del argumento y las que puedan dejarse de lado.
a)  p ∧ ( p → q ) ∧ r  → ( p ∨ q ) → r 
b)  ( p ∧ q ) → r  ∧ ¬q ∧ ( p → ¬r )  → ( ¬p ∨ ¬q )
c)   p ∨ ( q ∨ r )  ∧ ¬q  → ( p ∨ r )

2.- Use tablas de verdad para verificar que cada una de las siguientes proposiciones es una
implicación lógica.
a) ( p → q ) ∧ ( q → r )  → ( p → r )
b) ( p → q ) ∧ ¬q  → ¬p
c) ( p ∨ q ) ∧ ¬q  → q
d) ( p → r ) ∧ ( q → r )  → ( p ∨ q ) → r 

3.-Verifique que cada una de las siguientes proposiciones es una implicación lógica,
mostrando que es imposible que la conclusión tenga el valor de verdad 0 mientras la
hipótesis tenga el valor de verdad 1.
a) ( p ∧ q ) → p
b) p → ( p ∨ q )
c) ( p ∨ q ) ∧ ¬p  → q
d) ( p → q ) ∧ ( r → s ) ∧ ( p ∨ r )  → ( q ∨ s )
e) ( p → q ) ∧ ( r → s ) ∧ ( ¬q ∨ ¬s )  → ( ¬p ∨ ¬r )

4.-Para cada uno de los siguientes pares de proposiciones, use el Modus Ponens o el Tollens
para completar la línea en blanco con un argumento válido.
a) Si Juana tiene problemas para arrancar su aprobar sus materias, entonces su mamá
la enviará a unos cursos de regularización.
Juana tiene problemas para aprobar sus materias.
∴ ________________________________________________________________

b) S i Pedro resolvió el último problema del examen correctamente, entonces aprobó

el semestre.
Pedro no resolvió el último problema correctamente
∴ ________________________________________________________________

c) Si este es un ciclo repeat-until , entonces el cuerpo de este ciclo se ejecutara al

menos una vez.
∴ El cuerpo del ciclo se ejecuta al menos una vez.
 26
5.- Para las proposiciones primitivas p, q y r , sean
P la proposición  p ∧ ( p → q ) ∧ ( s ∨ r ) ∧ ( r → ¬q )  → ( s ∨ t ) y
P1 la proposición  p ∧ ( q ∨ r )  ∨ ¬  p ∨ ( q ∨ r ) 
Use las reglas de inferencia para mostrar que q ∧ r ⇒ q ∨ r .
¿Es cierto que P ⇒ P1 ?

6.- Justifique cada uno de los pasos necesarios para mostrar que el siguiente argumento es
válido.
 p ∧ ( q ∧ r )  ∨ ¬  p ∨ ( q ∧ r ) 

PASOS RAZONES
1) p
2) p → q
3) q
4) r → ¬q
5) q → ¬r
6) ¬r
7) s ∨ r
8) s
9)∴ s ∨ t

7.- Dar las razones para los pasos que verifican el siguiente argumento.
( ¬p ∨ q ) → r
r → (s ∨ t)
¬s ∧ ¬u
¬u → ¬t
∴p

PASOS RAZONES
1) ¬s ∧ ¬u
2) ¬u
3) ¬u → ¬t
4) ¬t
5) ¬s
6) ¬s ∧ ¬t
7) r → ( s ∨ t )
8) ¬ ( s ∨ t ) → ¬r
9) ( ¬s ∧ ¬t ) → r
10) ¬r
11) ( ¬p ∨ q ) → r
 27
12) ¬r → ¬ ( ¬p ∨ q )
13) ¬r → ( p ∧ ¬q )
14) p ∧ ¬q
15)∴ p

8.- a) Dé las razones para los pasos que justifican el argumento

( p → q ) ∧ ( ¬r ∨ s ) ∧ ( p ∨ r )  → ( ¬q → s )

PASOS RAZONES
1) ¬ ( ¬q → s )
2) ¬q ∧ ¬s
3) ¬s
4) ¬r ∨ s
5) ¬r
6) ⋅ p → q
7) ¬q
8) ¬p
9) p ∨ r
10) r
11) ¬r ∧ ¬r
12)∴ ¬q → s

b) Realice una demostración directa del resultado de la parte (a).

9.- Establezca la validez de los siguientes argumentos.

a) ( p ∧ ¬q ) ∧ r  → ( p ∧ r ) ∨ q 
b)  p ∧ ( p → q ) ∧ ( ¬q ∨ r )  → r
c) p → q d) p → q e) p → ( q → r )
¬q r → ¬q ¬q → ¬p
¬r r p
_________ ________ ____________
∴ ¬( p ∨ r ) ∴ ¬p ∴r

f) p ∧ q g) p → ( q → r ) h) p ∨ q
p → (r ∧ q) p∨s ¬p ∨ r
r → (s ∨ t) t→q ¬r
¬s ¬s __________
__________ ___________ ∴q
∴t ∴ ¬r → ¬t
 28

11.- Muestre con un contraejemplo que ninguno de los siguientes argumentos es válido, es
decir, dé una asignación de valores de verdad a las proposiciones primitivas p, q, r , y s de
modo que todas las premisas sean verdaderas (tengan el valor de 1) y que la conclusión sea
falsa (tenga el valor de verdad de 0).
a) ( p ∧ ¬q ) ∧  p → ( q → r )   → ¬r
b)  ( p ∧ q ) → r  ∧ ( ¬q ∨ r )  → p
c) p ↔ q d) p
q→r p→r
r ∨ ¬s p → ( q ∨ ¬r )
¬s → q ¬q ∨ ¬s
∴s ∴s

12.- Escriba cada uno de los siguientes argumentos en forma simbólica. Establezca después
la validez del argumento o dé un contraejemplo para mostrar que no es válido.
Si Felipe obtiene el puesto de supervisor y trabaja mucho, entonces obtendrá un aumento.
Si obtiene el aumento, entonces comprará una casa . El no ha adquirido una casa. Por lo
tanto, Felipe no ha obtenido el puesto de supervisor o no ha trabajado mucho.

DEMOSTRACIONES POR INDUCCIÓN MATEMÁTICA.

En el siglo XVIII , el matemático italiano Giuseppe Peano(1858-1932) 3 ideó la inducción
matemática para argumentar la validez de las fórmulas o procedimientos con un número de
pasos infinito numerable, es decir, con un número de pasos contable o equivalente al
conjunto de los números naturales. La importancia de este tema para el ingeniero en
sistemas es que a menudo dentro de esta área se debe analizar el número de operaciones
que hace un programa para llevar a cabo una tarea ,y dicho análisis se hace en base a
fórmulas cuya validez debe probarse y es cuando se recurre al método de prueba por
inducción.
Dicho principio se desprende del principio del buen orden, el cual indica:
Principio del Buen Orden: Cualquier subconjunto no vacío de  + contiene un elemento
mínimo ( Es en este sentido que a veces se dice que  + es bien ordenado).
Principio de Inducción Matemática. Sea S (n) una proposición matemática abierta (o
un conjunto de tales proposiciones abiertas) , en la que aparece una o varias veces la
variable n , que representa un entero positivo.
Si S (1) es verdadera; y

3
En realidad, el mismo Giuseppe Peano atribuyó la invención del método al matemático Richard Dedekind
(1831-1916). Se cree que el veneciano Francesco Maurocylus fue el introductor en 1575 de la idea en
Europa, y así lo atestigua una cita del importante matemático francés Blaise Pascal ( en 1653), al demostrar
resultados de análisis combinatorio como C ( n,= k ) C (n, k + 1) * (k + 1) / n − k ), 0 ≤ k ≤ n − 1 . El
término “inducción matemática” fue acuñado por el matemático inglés Augustus De Morgan, quien
describió el proceso en 1838.
 29
Siempre que S (k ) sea verdadera (para algún k ∈  + particular , pero elegido al azar)
entonces S (k + 1) será verdadera;

Entonces S (n) será verdadera para todo n ∈  + .

Demostración. Sea S (n) una proposición abierta con las condiciones (a) y (b) ,
y sea F= {t ∈  + | S (t ) es falsa} . Se desea mostrar que F = ∅ ; así que para
obtener na contradicción suponemos que F ≠ ∅ . Entonces, por el principio del
buen orden , F tiene un elemento mínimo s .Como S (1) es verdadera, s ≠ 1 , de
modo que necesariamente s > 1 , y en consecuencia , s − 1 ∈  + . Como
s − 1 ∉ F ,tenemos que S ( s − 1) es verdadera. Así , por la condición (b) ,se sigue
que S (( s − 1) + 1) = S ( s ) es verdadera , lo que contradice que s ∈ F . La
contradicción surge de la hipótesis de que F ≠ ∅ . Por lo tanto F = ∅ .

EJEMPLO1.6.Demostrar que para cualquier.

n
n ∈  + , ∑ i = 1 + 2 + 3 + ... + n = (n)(n + 1) / 2
i =1
Demostración: Está claro que S (1)= 1= (1)(1 + 1) / 2 . Por lo tanto S (1) es verdadera.
Esta es nuestra base de inducción. En segundo lugar , dado k ∈  + , supongamos
que es verdad que S (k ) :1 + 2 + 3 + ....k= k (k + 1) / 2 y demostremos que esto
“obliga” a que S (k + 1) es verdadera. En efecto:
1 + 2 + 3 + ...k + (k + 1) = k (k + 1) / 2 + (k + 1) , puesto que S (k ) es supuesta verdadera.
Simplificando nuestra suma, llegamos a que:
1 + 2 + 3 + ...k + (k + 1) = (k + 1)(k + 2) / 2 .
Lo cual establece la veracidad del paso inductivo, y por tanto, valiéndonos del
Principio de Inducción , concluimos la veracidad de nuestra fórmula.

2.-Según los ejemplos:

14 = 3 + 3 + 8
1 =5 3 + 3 + 3 + 3 + 3
16= 8 + 8

Hacemos la conjetura de que todo número natural n ,con n ≥ 14 , se puede escribir como
una suma de treses y ochos.
Demostración:
Como el 14,15 y 16 se pueden escribir en la forma descrita, ello establece nuestra base de
inducción. Supongamos que la proposición es válida para k ≥ 16 , con k ∈  + .Entonces
tenemos que probar que para k + 1 la propuesta es también válida. Obsérvese para esto que
k + 1 = (k − 2) + 3 , pero como 14 ≤ k − 2 ≤ k , entonces k − 2 es un número que puede
escribirse como una suma de treses y ochos, de aquí concluimos que k + 1 también puede
ser escrito de esa manera.; de esta forma, por el Principio de Inducción, llegamos a la
conclusión de que nuestra afirmación es válida.
 30

EJERCICIOS 1.7. Demostrar por inducción matemática lo siguiente:

(a) 12 + 22 + 32 + ... + (2n − 1)
= 2
(n)(2n + 1) / 3
n
1 n
(b) ∑ =
i =1 i (i + 1) n +1
n2 − n
(c) Si n ∈  + , con n > 10 ,demostrar que n − 2 < .
12
 31

UNIDAD II
RELACIONES

Objetivos:

Al finalizar la unidad, el alumno:

 Comprenderá el concepto de producto cartesiano y aprenderá a calcularlo
 Entenderá el concepto de relación
 Manejará la simbología propia de las relación
 Identificará los diferentes tipos de relaciones que hay , según sus propiedades
 Entenderá el concepto de relación de equivalencia y su relación con la partición de
un conjunto en subclases.

En esta unidad desarrollaremos el concepto de relación ,el cual es esencial en el análisis del
concepto de función, de partición y del concepto de grafo, temas que se estudiarán más
adelante. Además, el concepto de relación juega un papel importante en varias teorías como
la de probabilidades, estadística y análisis combinatorio, materias que son importantes en la
formación de un ingeniero en sistemas computacionales.
Iniciaremos estudiando el concepto de producto cartesiano, el cual es la base para definir
una relación.
 32
PRODUCTO CARTESIANO.

El producto cartesiano entre dos conjuntos A y B se denota A × B , y formalmente se

define como sigue:
=
A × B {(a, b) | a ∈ A y b ∈ B}

Nota: Observe que el orden es importante; es decir, no es lo mismo A × B que B × A .

Puede demostrarse que si el conjunto A consta de m elementos , y el conjunto B de n
elementos, entonces su producto cartesiano A × B contendrá m × n elementos ( parejas
ordenadas). Esto es importante de señalar y tomar en cuenta porque nos proporciona una
guía al momento de calcular un producto cartesiano, al indicarnos si hemos enumerado
exactamente el número de elementos que debe tener un producto entre dos conjuntos dados
EJEMPLO 2.1
1.- Obtener A x B, si
A = {1, 2, 3}
B = { q, p}
Solución: El producto A × B debe contener 3*2=6 elementos. En efecto, haciendo una
enumeración directa: A x B = {(1, p), (1,q), (2,p) ,(2,q), (3,p), (3,q)}.

2.- Obtener A x B ,si A = {a, s} y B = {1, 2, 3, 4, 5, 6} , obtener A × B y B × A .

.Solución:
Deben haber 2*6=12 elementos en cada uno de los productos. En efecto:
A x B = {(a,1), (a,2), (a,3), (a,4), (a,5), (a,6) ,(s,1), (s,2), (s,3), (s,4), (s,5), (s,6)}
B x A = {(1,a), (1,s), (2,a), (2,s) (3,a), (3,s), (4,a), (4,s), (5,a), (5,s), (6,a), (6,s)}
3.- Si B = {2,5,7}, obtener B 2 y B 3 .
Solución:
B 2 = B x B = {(2,2), (2,5), (2,7), (5,2), (5,5), (5,7), (7,2), (7,5) (7,7)}
B 3 = B x B x B = { (2, 2, 2), (2, 2, 5), (2, 2, 7), (2, 5, 2), (2, 5, 5),
(2, 5, 7(2, 7, 2), (2, 7, 5), (2, 7, 7) (5, 2, 2), (5, 2, 5), (5, 2, 7), (5, 5, 2),
(5, 5, 2), (5, 5, 7), (5, 7, 2), (5, 7, 5), (5, 7, 7) (7, 2, 2), (7, 2, 5), (7, 2, 7)
(7, 5, 2), (7, 5, 5), (7, 5, 7), (7, 7, 2), (7, 7, 5), (7, 7, 7)}

PROPIEDADES DEL PRODUCTO CARTESIANO.

Para cualesquiera subconjuntos A, B y C de un conjunto universal U,

se cumplen las siguientes propiedades:
 33
1. − A × ( B ∩ C ) = ( A × B) ∩ ( A × C )
2. − A × ( B ∪ C ) = ( A × B) ∪ ( A × C )
3. − ( A ∩ B) × C = ( A × C ) ∩ ( B × C )
4. − ( A ∪ B) × C = ( A × C ) ∪ ( B × C )

EJEMPLO 2.2
1.- Si A = {1,2} , B = {a, b, c} y C = { @, *, c, d } , comprobar que
A × ( B ∪ C ) = ( A × B) ∪ ( A × C )
Solución:
Por un lado: B ∪ C = {a, b.c, @,*,d}
A × ( B ∪ C ) = {(1, a ), (1, b), (1, c), (1, @),(1,*),(1,d),(2,a),(2,b),(2,c),(2,@),(2,*),
(2,d)}
Desarrollando por el lado izquierdo:
A x B ={(1,a),(1,b),(1,c),(2,a),(2,c)}
A x C ={(1,@),(1,*),(1,c),(1,d),(2,@),(2,*),(2,c),(2,d)}
(A x B) ∪ (A x)={(1,a),(1,b),(1,c),(2,a),(1,@),(1,*),(1,c),(1,d),(2,@),(2,*),(2,c),
(2,d)}. Se puede ver que ambos conjuntos coinciden.

EJERCICIO 2.1. Obtener lo que se pide en cada caso:

=
(a) Sean M {= águila, sol}, D {1, 2,3, 4,5, 6} . Obtenga el producto M × D .
=
(b) Si A {1,= 2,3}, B {2, = 4}, C {3, 4,5}. Hallar A × B × C .
(c) =
Sean A {= a, b}, B {2,3}, = y C {3, 4} . Hallar :i) A × ( B ∪ C ),
(ii) ( A × B) ∪ ( A × C ) (iii) A × ( B ∩ C )

2.2 RELACIONES.
A un subconjunto del producto cartesiano A x B se le llama relación de A en B.
En general si A es un conjunto con n elementos y B un conjunto con m elementos,
entonces el número de relaciones de A a B es igual a 2 mn , incluyendo a la relación vacía
∅.
EJEMPLO 2.3
Obtener cinco relaciones de A en B , si
A = {m, n ,l}
B ={1, 0}

Solución:
Paso 1.
Hay 2 6 = 64 relaciones de A en B
 34
Obtener A x B = {(m,1), (m,0), (n.1), (n,0), (l,1), (l,0)}

Paso 2.
Del producto anterior obtendremos las cinco relaciones pedidas.
R1 = {(m,1)}
R2 = {(n,1),(n,1)}
R3 = {(m,0), (n,1),(l,1), (m,1)}
R4 = {(n,1), (n,0)}, {(n,1), (l,1)}, {(n,1),(l,0)}
R5 = ∅ ,etc.

EJEMPLO 2.4
.
1.- a) Obtener cuántas relaciones pueden establecerse entre el conjunto
A = {0,1,2,3,4} B = { α , β , γ )
Solución:
n(A)= 5
m(B)=3

Así que hay 215 relaciones de A en B.

b) Dar tres ejemplos de relaciones no vacías de A en B.

Solución:
Como primer paso, calculamos el producto cartesiano de ambos conjuntos en el orden
requerido:
A x B = {0,1,2,3,4} x { α , β , γ }
{(0, α ), (0, β ), (0, γ ), (1, α ), (1, β ), (1, γ ), (2, α ), (2, β ), (2, γ ),
(3, α ), (3, β ) (3, γ ), (4, α ). (4 β ,), (4, γ )}

De aquí, se obtienen tres relaciones no vacías de A en B:

R1 ={(2, α )},
R2 ={(2, β ), (1, α ), (1, β )}, R3 ={(3, β ), (4, β )}
c) Obtener tres relaciones de tamaño 5.

Solución:
R1 = {(0, α ), (1, β ), (1, γ ), (2, β ), (3, γ )}
R2 = {(0, β ), (2, α ), (4, γ ), (4, β ), (4, α )}
R3 = {( 0, γ ), (1, α ), (3, α ), (4, γ ), (2, β )}
 35

RELACIÓN BINARIA.
Considere a un conjunto vacío A, se le llama relación binaria a todo subconjunto de A x
A.
Es necesario indicar el significado de los siguientes símbolos:
Suponga que ℜ es una relación binaria, definida sobre el producto cartesiano A x A, y que
(a, b) ∈ ℜ , entonces a esta situación la denotamos con el símbolo aℜb , que significa :” a
está relacionada con b, mediante ℜ ”. En caso contrario, es decir si a no está relacionada
con b mediante ℜ , escribimos a ℜb .
La notación anterior cobra importancia en los siguientes ejemplos:
Definimos la relación ℜ sobre el conjunto  como aℜb , o (a, b) ∈ ℜ , si a ≤ b. Este
subconjunto de  x  es la relación ordinaria “ menor o igual que “ sobre el conjunto  , y
también puede definirse sobre  o , pero no sobre  . Con esta definición de ℜ , por
ejemplo está claro que 2 ℜ 3, porque 2 ≤ 3; sin embargo 5 ℜ 8, porque 5 ≤ 8. En tal sentido
decimos que (2,3) ∈ ℜ , pero que (5,3) ∈ ℜ .
La relación siguiente es una relación importante en muchos ámbitos, por ejemplo, nos
permite definir a una “función localizadora”, como veremos en el tema de funciones. Sea
n ∈  + . Para x, y ∈  ,la relación módulo n , ℜ , está definida como xℜy , si x-y es un
múltiplo de n. Por ejemplo, si n = 7 , encontramos que 9ℜ2 , −3ℜ11, (14,0) ∈ ℜ ,pero
3 ℜ 7 (es decir, 3 no está relacionado con 7).

EJEMPLO 2.5
1.-Si A = {a, b, c} ,obtener 3 relaciones binarias no vacías de A.
Solución:
Primero obtenemos el producto cartesiano A x A:
A x A = A{a ,b, c} x A{a, b, c}
= {(a ,a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
R1 = {(a, a), (a, b)}
R2 = {(a, a), (a, b), (a, c)}
R3 = {(a, a), (a, b), (a, c), (b, a)}

2.- Con A =  + , considérese la relación binaria ℜ en el conjunto A como

{( x, y ) | x ≤ y} . A esta relación se le llama “menor ó igual” para los enteros positivos. En
esta relación están por ejemplo las parejas ordenadas (6,6), (8,11); pero (6,4) ∉ ℜ .
3.- Sea ℜ el subconjunto de  × donde= ℜ {(=
m, n) | n 3m} . Esta relación indica que
dos enteros n y m están relacionados si n es el triple de m .Así, por ejemplo dentro de
esta relación se encuentran (1,3), (4,12), (−2, −6)
 36
EJERCICIO 2.2 Obtener lo que se pide en cada caso:
1.-Si A = {p, q, r} dar dos ejemplos de relaciones binarias no vacías de A .
2.- ¿Cuántas relaciones binarias tiene el conjunto A = {1, 2,3, 4,5, 6} ?
3.-Sea A un conjunto con 3 elementos. Si existen 4096 relaciones de A en B, ¿Cuántos
elementos contiene el conjunto B?.
4.- Indicar si aℜb , para
ℜ = {(1,3), (2,5), (2,7)}
(a) 1 ℜ 5
(b)2 ℜ 5

5.- Si ℜ = { (0,1).(3,2), (7,5)},es verdadero o falso que:

3 ℜ5
• 1ℜ 0

3.-Si ℜ = {(a, b)| a-b es un número entero positivo}, donde ℜ ℜ es un subconjunto de

 × .
(a) ¿ (7, 4) ∈ ℜ ?, (b) ¿ (−2, −8) ∈ ℜ ?

TIPOS DE RELACIONES
Dada una relación ℜ , puede o no tener la característica de ser reflexiva, simétrica y
transitiva, entre otras . Hacer esta distinción es importante, porque de el hecho que tengan
estas propiedades depende de que puedan introducir o no una partición o un orden parcial
dentro de un conjunto, lo cual es muy significativo en la ciencia de la computación para
poder clasificar datos.

RELACIÓN REFLEXIVA:
ℜ una relación sobre un conjunto A es una relación reflexiva, si para todo x ∈ A, implica
que x ℜ x .

RELACIÓN SIMETRICA:
La relación ℜ sobre el conjunto A es simétrica, si dados x, y ∈ A y ( x, y ) ∈ ℜ , implica
que (y, x) ∈ ℜ .

RELACIÓN TRANSITIVA:
R es una relación transitiva sobre un conjunto A si dados x, y, z ∈ A y además se cumple
que: xRy y yRz, implica que xRz .
EJEMPLO 2.6
 37
1.-Si A ={1,2,3,4} , R1 = {(2,1), (1,2), (4,3), (3,4)}. Puede verse que R1 no es reflexiva ,
porque por ejemplo (2,2) no es parte de R1 . También R1 es simétrica ; pero no es
transitiva, porque (2,1) y (1,2) son parte de R1 , pero (2,2) no.
2.- Considere R = {(a, b)| a, b∈  y a ≥ b} .Es una relación transitiva porque si x, y, z son
números reales y además x ≥ y x ≥ z, entonces x ≥ z. También es simétrica y reflexiva. A
esta relación se le llama “mayor ó igual”.
3.- Si A ={1,2,3,4} entonces ℜ1 ={(1,1),(2,3), (3,4), (2,4) } es una relación transitiva.
Claramente no es simétrica, porque por ejemplo (3,2) no es parte de esta relación, siendo
que (2,3) sí lo es; además tampoco es reflexiva, porque (2,2), por ejemplo, no forma parte
de dicha relación.

EJERCICIO 2.4.

1.-Si A = conjunto que consta de

A ={1,2,3}
ℜ ={(1,2), (2,1), (1,3), (3,1)},
(a) ¿ ℜ es simétrica?
(b)¿Es reflexiva?
© ¿Es transitiva?

2.-Si A = {1, 2,3, 4} , dar un ejemplo de una relación ℜ sobre A que sea:
(a) Reflexiva y simétrica, pero no transitiva.
(b)Reflexiva y transitiva, pero no simétrica
© Simétrica y transitiva, pero no reflexiva.
3.- Considere la relación ℜ sobre el conjunto  + , definida como
b
ℜ ={(a, b) | es un número entero} . Indicar si dicha relación es reflexiva, simétrica o
a
transitiva.
4.- ℜ es una relación definida sobre  , dada por ℜ ={ (a, b) | a + b es un número par}.¿Es
esta relación reflexiva, simétrica o transitiva?.

RELACIÓN DE EQUIVALENCIA.
Se le llama relación de equivalencia aquella que tenga las propiedad simétrica, reflexiva y
transitiva ( las tres juntas)
EJEMPLO 2.7
1.- Si A ={1,2,3}
R = {(1,1), (2,2),(3,3), (3,2)}
R es reflexiva, simétrica y transitiva (¿por qué?). Por lo tanto, dicha relación es una
relación de equivalencia.
 38
2.- Si A ={1,2,3}, entonces
R1 ={(1,1), (2,2), (3,3)},
R2 ={(1,1), (2,2), (2,3), (3,2), (3,3)},
R3 ={(1,1), (1,3), (2,2), (3,1), (3,3)} y
R4 ={(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1),(3,2), (3,3)}
son relaciones de equivalencia sobre A ¿Por qué ?.

PARTICIONES Y CLASES DE EQUIVALENCIA

Una relación de equivalencia induce una partición dentro del conjunto sobre el cual está
definida; es decir, lo divide en subconjuntos mutuamente disjuntos a los cuales llamaremos
clases de equivalencia.
Formalmente definimos:
Partición: De un conjunto A es una división de A en n subconjuntos A1 , A2 ,.. An , tales
que:
(i) Ai ∩ Aj =
∅, con i ≠ j . Para todo 1 ≤ i ≤ n y 1 ≤ j ≤ n .
n
(ii) A i =A
i =1

A los conjuntos Ai se les llama células o celdas. De modo que la definición de partición
significa simplemente que esta es una descomposición de un conjunto en celdas , tales que
todo elemento del conjunto esté en exactamente una de las celdas.
Tenemos al conocido teorema siguiente:
Teorema: Sea A un conjunto no vacío y sea ℜ una relación entre elementos de A que es
reflexiva, simétrica y transitiva, entonces ℜ produce una partición natural de A, en donde
a ={x ∈ S | xℜa}

es la celda que contiene a todos los elementos x que son equivalentes a a .

Cada celda a en la partición natural es una clase de equivalencia.

EJEMPLO 2.8.
1.-Dar tres ejemplos de particiones del conjunto A = {1, 2,3, 4} .
Solución:

℘1 ={{a, b, c, d }}
℘2 ={{a},{b, c, d }}
℘3 ={{a, b},{c, d }}
 39
Todas ellas son particiones en donde todo elemento está en exactamente uno de los
conjuntos, y la unión de los conjuntos de cada clase es exactamente igual a A.
2.- Denotamos por ejemplo con el símbolo 2 / 3 a todos los números racionales o
fraccionarios que equivalen en decimal a dicho número; es decir: 2 / 3
2n
= {2 / 3, −2 / − 3, 4 / 6, 6 / 9, −6 / 9....}
= { | n ∈  y n ≠ 0} . Este ejemplo muestra que los
3n
números fraccionarios o racionales pueden partirse en clases, cada una de las cuales
contiene a todos aquellos elementos que son numéricamente iguales a un número racional
dado.
3.- Definamos una relación ℜ en el conjunto  mediante nℜm si y sólo si nm ≥ 0 . ¿Es
ℜ una relación de equivalencia?. Debemos verificar las tres características de una relación
de equivalencia:
(1) Reflexividad: Si a ∈  , entonces aℜa , debido a que a 2 ≥ 0 .
(2)Simetría: Si a, b ∈  y además aℜb , entonces es claro que bℜa , porque
= ab ≥ 0 .
ba
(3)Transitividad: No lo es , porque por ejemplo (-3)(0) ≥ 0 y (0)(5) ≥ 0 , pero (-
3)(5)<0.

De este modo dicha relación no es una relación de equivalencia.

4.- Por último, tratemos el importante caso de las congruencias módulo n. Para h, k ∈  ,
definimos h congruente con k módulo n , lo cual se escribe h ≡ k (mod n) , si h − k es
divisible entre n; es decir , que h − k = ns , para alguna s ∈  . Por ejemplo ,
17 ≡ 33(mod 8) , puesto que 17-33=8(-2). Las clases de equivalencia para la congruencia
módulo n son las clases residuales módulo n. Cada una de estas clases residuales
contiene un número infinito de elementos . Por ejemplo, la clase residual para la
congruencia módulo 8 que contiene al 17 y al 33 es:

{..., −47, −39, −31, −23, −15, −7,1,9,17, 25,33, 41, 49,...} .

Esta clase residual contiene cada octavo número , comenzando con 1. De hecho, hay siete
clases residuales más en la partición dada por la congruencia módulo 8..
EJERCICIOS 2.5
1.-Determínese si la relación dada es una relación de equivalencia en el conjunto y
descríbase la partición que surge de cada relación de equivalencia.
a) n ℜ m de  si nm > 0
b) x ℜ y si | x | = | y |
c) n ℜ m en  + si y m tienen el mismo número de dígitos en la notación usual de base
diez.
d) x ℜ y en ℜ si x ≥ y
e) x ℜ y en ℜ si | x − y |≤ 3
f) n ℜ m en  + si n y m tienen el mismo dígito final en la notación usual de base diez.
 40
g) n ℜ m en  + si n − m es divisible entre 2.
h) Sea n un entero en  + muéstrese que la congruencia módulo n es una relación de
equivalencia en  + . Descríbanse las clases de residuales para n = 1, 2, 3.
i) El siguiente es un formato falso. Encuéntrese el error. “ El criterio de reflexividad es
redundante en las condiciones para una relación de equivalencia, ya que de
a  b y b  a (simetría) deducimos a  a por transitividad.

2.- Encuéntrese el número de relaciones de equivalencia posibles en un conjunto S S a

partir del número de sus elementos (Sugerencia: ayudarse del hecho de que una relación de
equivalencia introduce una partición natural en un conjunto dado).
a) 1 elemento
b) 2 elemento
c) 3 elementos
d) 4 elementos
e) 5 elementos
 41

UNIDAD III
FUNCIONES

En esta unidad , el alumno:

 Entenderá el concepto de función y las diferentes formas en las cuales puede
describirse a una función.
 Identificará y aprenderá a usar la simbología propia de las funciones.
 Entenderá las partes que describen o identifican a una función, como son el
dominio, el codominio y el rango.
 Aprenderá a clasificar a las funciones en inyectivas, suprayectivas y biyectivas.
 Entenderá las condiciones en las cuales una función es invertible.
 Aprenderá a calcular la inversa de una función.
 42

En este capítulo estudiaremos a las funciones, las cuales en realidad son un tipo especial de
relación, cuya definición tiene una larga historia que comenzó en el siglo XVIII, con los
trabajos matemáticos de Euler, y cuya definición fue aclarada y extendida en el siglo
pasado por matemáticos como Cantor, Fourier , Dirichlet y Cauchy. El concepto de función
aparece en ramas como la Física, la Teoría de Probabilidades, Economía, etc.; es uno de
los conceptos más usados. Y lo es porque nos permite modelar fenómenos de respuesta
única; es decir acontecimientos que cada vez que ocurren lo hacen arrojando exactamente
un resultado.

3.1. CONCEPTO DE FUNCIÓN.

Para los conjuntos A ,B , una función , o aplicación , f de A en B , que se denota con

f : A → B , es una relación de A en B en la que cada elemento de a aparece
exactamente una vez como la primera componente de un par ordenado en una relación. 4
Esta forma de definir a una función es sumamente fructífera , porque nos permite hablar
de funciones actuando sobre conjuntos no numéricos. También es común definir a una
función como una relación de un conjunto A a un conjunto B de modo que a cada
elemento a ∈ A , dicha relación le asigna exactamente un elemento b ∈ B .
Simbolizamos esta situación como f (a ) = b o bien (a,b) ∈ f . Al número b se le llama
la imagen de a bajo f ( al elemento a se le llama preimagen de b) y a la función f se le
llama regla de correspondencia.
De modo que para describir a una función ,se necesitan tres elementos:
(i) El conjunto A, al cual llamaremos dominio de la función
(ii) El conjunto B, al que llamaremos codominio
(iii) La regla de correspondencia dada por f.

EJEMPLO 3.1. Considere A = {1, 2,3} y B = {w, x, y, z} . Sean

(a) f : A → B y f = { (1, x), (2, z ), (3, y )} . Esta es una función definida de A a B .
(b) f : A → B y f = {(1, x), (3, z )} . Esta regla de asignación no es una función, porque la
definición indica que a cada elemento de A ( el dominio), dicha regla le debe asignar
exactamente un elemento en el conjunto B (el codominio) y en este caso al número 2
no se le asigna ningún elemento en B .
(c) f : A → B con f = {(1, w), (2, x), (3, y ), (3, z )} . En este caso f tampoco es una función,
debido a que al número 3 le asigna dos valores distintos y y z . La definición de
función dice que a cada elemento del dominio se le debe asignar exactamente un
elemento en el codominio.
(d) f : A → B con f = {(1, w), (2, w), (3, w)} . En este caso f es una función, porque la
regla de correspondencia f le asigna exactamente un elemento a cada número que
aparece en el conjunto dominio A , no importa que sea el mismo.
4
Esta definición de función la dio por primera vez el matemático alemán Peter Gustav Lejeune Dirichlet
( 1805-1859) en 1837. Como se ve en la definición de función dada por este matemático ,no es necesaria una
fórmula que relacione a las cantidades dependientes de las independientes, como a menudo se podría creer,
sobre todo por los cursos de cálculo diferencial e integral.
 43

Para la función f : A → B , A es el dominio ( lo denotaremos D f ) y B es el codominio

de f ( lo denotaremos Codf ). El subconjunto de B formado por aquellos elementos
que aparecen como segundas componentes de los pares ordenados de f se le conoce
como la imagen de f y se le denota también como f ( A) ya que es el conjunto de
imágenes (de los elementos de A ) mediante f . 5
FORMAS DESCRIPTIVAS DE UNA FUNCIÓN. Las funciones aparecen en muchas
formas en la práctica, como por ejemplo en forma de tablas ( una nómina es una función
que asigna a cada empleado un solo salario). Nos es familiar la forma gráfica de una
función, o los diagramas sagitales , y por supuesto, en forma de fórmula.

Forma gráfica Forma sagital Forma tabular

FUNCIONES EN COMPUTACIÓN
En la Computación aparecen repetidamente varios tipos de funciones ;por ejemplo, en los
lenguajes de programación , se hallan implementadas una gran cantidad de funciones, como
las siguientes:
a) Función parte entera o función suelo. Esta función se simboliza como
f :  →  con f =  x  y está dada por
f =  x  = el mayor entero menor o igual que x

Por ejemplo: f (3.7) =3; f (4) =4; f (−5) =−5; f (−3.8) =−3. Esta función en el
++
lenguaje C , se implementa mediante el molde int. En BASIC , se implanta mediante
INT.
b) La función trunc (de truncar) aparece en Pascal, por ejemplo , y su acción sobre un
número real elimina su parte fraccionaria .Por ejemplo, trunc(3.78)=3; trunc(5)=5;
trunc(-6.13)=-6.
c) Funciones localizadoras. Al guardar una matriz en una tabla unidimensional ,
varios lenguajes de programación lo hacen por filas , con el método de la fila

5
En los cursos de cálculo diferencial e integral también se le llama “rango o recorrido de f"
 44
principal . En este caso, si A = (ai , j ) n×n es una matriz n × n , la primera fila de A ,
se guarda en los lugares 1,2,3,...,n de la tabla si comenzamos con a11 en el lugar 1.

a11 a12  a1n a21  a2n a31  aij  a

a22 nn

1 2  n n +1 n+2  2n 2n + 1  (i − 1)n + j 

El elemento a21 se encuentra entonces en la posición n + 1 , mientras que el a34 ocupa la

posición 2n + 4 en la tabla. A fin de determinar el lugar de cualquier elemento a j de A en
donde 1 ≤ i, j ≤ n , se define la función de acceso f de los elementos de A en las
posiciones 1, 2, 3.... n 2 de la tabla. Una formula para la función de acceso es
f (aij ) =(i − 1)n + j . A este tipo de funciones se les llama funciones localizadoras y existen
varias formas de obtenerlas.
3.2 OPERACIONES ENTRE FUNCIONES.

Se pueden realizar varias operaciones entre dos funciones f y g dadas. En seguida

definimos la suma, la resta, la multiplicación, la división y la composición de dos
funciones.
Sean f y g dos funciones definidas como sigue f : A → B y g : C → D , entonces:
a) SUMA y RESTA: Definimos la suma (resta) de f y g como aquella función
cuyo dominio es igual al conjunto A ∩ C y cuya regla de correspondencia f ± g es

f ± g= {(a, b) | b= f (a) ± g (a) }

b) MULTIPLICACIÓN. Definimos la multiplicación f y g como aquella función

cuyo dominio es igual al conjunto A ∩ C y cuya regla de correspondencia f * g es

=
f * g {(=
a, b) | b f (a) * g (a ) }

c) DIVISIÓN: . Definimos la división f y g como aquella función cuyo dominio es

igual al conjunto ( A ∩ C ) − {a ∈ C | g (a ) ≠ 0 } y cuya regla de correspondencia f / g
es :
= f / g {(= a, b) | b f ( a ) / g ( a ) }

d) COMPOSICIÓN: Definimos la composición g  f de las funciones f y g como

aquella función cuyo dominio es igual al conjunto {a ∈ A | f (a ) ∈ C} y cuya regla de
correspondencia es :

=
g  f {(=
a, b) | b g ( f (a )}
 45

EJEMPLO 3.2. Si
f ={(2,3), (4, −1), (3,5), (7, 4), (6,8)} ; g =
{(2,5), ( −2,3), (3, 0), (7, 2), (13, 4)}
Obtener: f + g , f − g , f * g , f / g , f  g y g  f .
Solución: El dominio de f , es igual a D f = {2, 4,3, 7, 6} y el dominio de g es igual a
D=g {2, −2,3, 7,13} . El dominio de f + g , f − g y f * g , es el mismo y es igual al
conjunto {2,3,7}, de modo que dichas operaciones sólo están definidas en ese conjunto.
Las reglas de correspondencia, son:

f + g= {2,3 + 5), (3,5 + 0), (7, 4 + 2)}= {(2,8), (3,5), (7, 6)}
f − g = {(2,3 − 5), (3,5 − 0), (7, 4 − 2)}= {(2, −2), (3,5), (7, 2)}
= =
f * g {(2,3* 5), (3,5 * 0), (7, 4 * 2)} {(2,15), (3, 0), (7,8)}

Por otro lado, el dominio de la composición de estas funciones f  g , viene dado por el
conjunto D f  g = {a ∈ Dg | g (a ) ∈ D f } =
{−2, 7,13} . Por lo tanto, en esos números tiene
sentido hablar de tal composición; la regla de correspondencia resulta
f g = {(−2,5), (7,3), (13, −1)} .
De manera similar se puede ver que Dg  f = {2} y que por tanto g  f = {(2, 0)} .
2.-En este ejemplo, obtendremos los resultados de operar dos funciones dadas como una
fórmula. Sean f : [−8, 2] →  y g : [−2,5] →  , con reglas de correspondencia dadas
por las fórmulas f ( x) =
2x + 3 y g ( x) =
x2 . Obtenga
f + g, f − g, f / g, f  g y g  f .
EJEMPLO 3.3. (a) Obtenga el rango de la función f : [2,10] →  , cuya regla de
correspondencia viene dada por f ( x) = x 2 .

Solución . Si 2 ≤ x ≤ 10 , entonces es claro que 4 ≤ x 2 ≤ 100 . De este modo, el rango o

recorrido de esta función sobre el dominio dado es el conjunto
Rango f = {x ∈  | 4 ≤ x ≤ 100} , es decir, son todos los enteros entre 4 y 100.
(b)Obtenga el rango de la función f :{1, 2,3} → {1, 2,3, 4,5} , con regla de correspondencia
f = {(1,3), (2, 4), (3,5)} . Solución: Rangof = {3, 4,5} .

El dominio de la suma , de la resta y de la multiplicación es exactamente el mismo, según la

definición. Todo lo que tenemos que hacer para obtenerlo es intersectar los dominios , para
obtener [−2, 2] . Las reglas de correspondencia en cada
caso, son:
( f + g )( x) = (2 x + 3) + x 2
( f  g=
)( x) f ( g=
( x)) 2( x 2 ) + 3
( g  f )(=
x) g ( f ( x=
)) (2 x + 3) 2
( f − g )( x) = (2 x + 3) − x 2
( f * g )( x) = (2 x + 3) + x 2
 46

Observe que la composición de dos funciones ( g  f )( x) = g ( f ( x)) es una operación en

donde primero se aplica la función f sobre un elemento válido x , y enseguida la otra
función g retoma el resultado y lo transforma en otro valor; a esta situación la denotamos
así ( g  f )( x) = g ( f ( x)) , y en la práctica significa que sustituya dentro de la variable de la
función g a la función f .

EJERCICIO 3.1.
1) Indicar si las relaciones siguientes son funciones o no:
(a ) {(2,1), (−1,5), (0, 0), (6, 2)}
(b) {(−3,1), (−3, 0), (4, 2), (7,5)}
(c) {(−5, 2), (1, 2), (3, 2), (5, 2), (7, 2)}
(d ) {(0, 2), (1/ 2,3 / 2), (1/ 3, −2 / 5), (1/ 4,3)}

2)Obtenga el dominio de las funciones

3x + 1
(i) f ( x) = (ii) g(x)= 3 x + 1 (iii) f ={(3,1), (2, −8), (7, 2), (0, −1)}
5x − 1
3x + 1
3) Calcular f (4), f (−3), f (3.5) , si f ( x) = .
5x − 1
4) Si
f = {(2,1), (5, 0), (4,8), (6,5), (9,3)}
(a)
= g {(2,8), (7, −2), (4, 0), (6, 4), (5, 6), (3, 2)}
f = {(1,3), (2, 4), (3,5), (4, 6)}
(b)
= g {(0, −3), (3, 2), (4,1)}
Obtenga f + g , f − g , f * g , f / g , g / f , f  g y g f .
4.- Suponga que f : (−∞, 4] →  y g : (−1, 0) → , con reglas de correspondencia
f ( x) =
3x − 2 y g ( x) = 3 − 2x .2
Obtenga
f + g, f − g, f * g, f / g, g / f , f  g y g  f .
 47
3.3. FUNCIONES INYECTIVAS, SUPRAYECTIVAS Y BIYECTIVAS.

Existen ciertas clases de funciones que por la manera en que transforman un conjunto
en otro, adquieren una importancia muy especial en varios contextos.
Función Inyectiva o Uno a Uno: Si f : A → B , y cada si f (a ) = f (b) , solamente
si a = b ,entonces se dice que f es una función inyectiva. En otras palabras, una
función será inyectiva si a no hay en su dominio dos elementos a los cuales les asigne
el mismo elemento en el codominio.
Por ejemplo:
=(a) f {(1, 4), (3,1), (2,8), ( −5, 4)} , es una función inyectiva.
(b) f = {(1,3), (3, 2), (2,3)} , o es inyectiva, porque al 1 y al 2 les ha sido el número 3
© Si f :  → con f ( x) = x 2 , entonces f no es inyectiva, porque
= f (−2) , por ejemplo.
f (2)

(d)Sin embargo f : [0, ∞) →  , sí es una función inyectiva, puesto que no hay

dentro del dominio de esta función dos elementos que reciban el mismo valor.

Función Suprayectiva: : Si f : A → B , y para cada elemento y en el

codominio, existe un elemento x en el dominio tal que y = f ( x) , entonces se
dice que la función f es suprayectiva. ( o simplemente sobre). Es decir, una función
es suprayectiva si “mapea” a su dominio de manera que no queden elementos de
su codominio sin preimagen, no importando que sea la misma.
Por ejemplo:
(a) La función = S iA {1, = 2,3} y B {a, b, c} y f :A→B con
f = {(3, a ), (2, c), (1, b)} es un ejemplo de función suprayectiva.
(b) La función f : A → B = , con =
A {1, 2,3, 4,5} y B {a, b, c} , cuya regla de
correspondencia es f = {(1, a ), (2, b), (3, c), (4, a), (5, b)} , es suprayectiva.
(c) La función f :  → [0, ∞) con f ( x) = x 2 ,es una función suprayectiva: también la
función f ( x) =  x  es una función sobre, porque está definida como f :  →  .

Función Biyectiva: Es una función que es al mismo tiempo inyectiva y suprayectiva.

Es claro que una función será biyectiva si su dominio y codominio tienen la misma
cantidad de elementos; de hecho, a estas funciones se les utiliza para definir conceptos
como isomorfismo, numerable,etc., porque en ciertos contextos los conjuntos con el mismo
 48
número de elementos se les podría considerar como semejantes o equivalentes en algún
sentido o para ciertos usos.
Por ejemplo:
(a) La función f :  → cuya regla es f ( x) = x 3 es biyectiva, porque a cada
número real le asigna exactamente otro número real diferente al que haya asignado
a otro elemento distinto de su dominio; y por otra parte no existe ningún número
dentro de su codominio que no tenga una preimagen.
(b) Por las mismas razones que en (1) , la función f ( x) = sen( x) , con
f : [0, 2π ] → [−1,1] , es una función biyectiva; sin embargo no lo sería si la
hubiéramos definido como f :  → [−1,1] . ¿Por qué?.
(c) La función suelo f ( x) =  x  , no es biyectiva. ¿Por qué?.

3.4 FUNCIÓN INVERSA

Se dice que f : A → B es una función invertible si existe una función que denotaremos
como f −1 , tal que f −1 : B → A y ( f =
−1 −1
 f )( x) f= ( f ( x)) x , para cada elemento x
en el dominio de f ;
y además
( f= f −1 )( x) f=
( f −1 ( y )) y , para cada elemento y en B .

Nota:Se puede demostrar que una función es invertible ( que tiene inversa) si y sólo si es
biyectiva.
EJEMPLO 3.4
1) La importancia de que una función sea invertible, es que representa la posibilidad de
revertir el proceso al cual esté ligada o describa; así, por ejemplo, las funciones
CHR y ORD del lenguaje Pascal son inversas una de la otra, y por tanto permiten
pasar del código binario ASCII a la representación común de un símbolo, mediante
CHR; y viceversa, mediante ORD se puede pasar a un símbolo común definido en
ese lenguaje a su representación binaria.
2) Todos sabemos de la importancia de las funciones trigonométricas en varias áreas
de la ciencia y la tecnología; la función inversa de f ( x) = senx es
f −1 ( x) = arcsenx , que da respuesta a la pregunta de bajo qué ángulo , la función
seno toma determinado valor.
3) Es relativamente simple determinar la inversa de una función de una variable. Por
2x + 1
ejemplo, = considere f ( x) − {−2 / 3} → − {1} . Esta función es
, con f : 
3x + 2
biyectiva. Su fórmula inversa se determina como sigue:
 49
2x + 1 2y −1
Haga y = . Enseguida se despeja x , quedando x = . Intercambiando x
3x + 2 2(1 − y )
2x − 1
por y , se obtiene la fórmula y = . Esta última fórmula es la inversa de la función
2(1 − x)
dada.

EJERCICIO 3.3. Contestar los siguientes problemas:

1) Indicar si las funciones que se ven en la gráfica son inyectivas, suprayectivas o
biyectivas.

(a) (b)

(c) (d)

2. Indicar si existe la inversa de la función .Si no, indicar por qué no.
= =
a) f {(2,3), (5, 2), (4,1)} =
con Domf {2,5, 4} y Codf {1, 2,3,5}

=
(b)La función S iA {1,= 2,3} y B {a, b, c} y f : A → B con f = {(3, a ), (2, c), (1, b)} es un
ejemplo de función.
(d) La función f : A → B =, con A {1, = 2,3, 4,5} y B {a, b, c} , cuya regla de
correspondencia es f = {(1, a ), (2, b), (3, c), (4, a), (5, b)} .
(e) La función f :  → [0, ∞) con f ( x) = x 2
(f) La función f ( x) =  x  definida como f :  →  .

3.-Determine la inversa de la función.

2− x
f ( x) = , con Domf = − {−2 / 3} y Codf = − {−1/ 2} .
3 + 2x
 50

UNIDAD IV
TEORÍA DE GRAFOS

En esta unidad, el alumno:

 Conocerá la terminología básica de la teoría de Grafos.

 Aprenderá a representar a un grafo mediante su matriz de incidencia o mediante su
matriz de adyacencia.
 Aplicará en problemas prácticos los conceptos de caminos y circuitos eulerianos y
hamiltonianos.
 Aplicará en problemas prácticos el concepto de grafo ponderado
 Resolverá ejemplos asociados con el concepto el concepto de grafos isomorfos.
 51
La Teoría de Grafos nació en 1736, con el problema de los puentes de Königsberg
planteado y resuelto por Leonhard Euler. En la actualidad esta disciplina se aplica en la
resolución de problemas en la Computación (Estructura de Datos, Topología de Redes),
Investigación de Operaciones (Teoría de redes), Electrónica (en el área de digitalización de
imágenes e información), en la Teoría de Códigos, Física y Economía.

4.1 GRAFOS

Ejemplos cotidianos en donde se utilicen grafos:

a) Diseño de tuberías.
b) Diseño de carretera.
c) Rutas de avión.
d) Un recorrido a través de un museo.
e) La ruta que sigue un vendedor.
f) Un árbol de toma de decisiones.

Comenzamos el estudio de la teoría de los grafos con la exposición de la terminología

básica:
GRAFOS: Un grafo es una estructura que está formada por los dos conjuntos finitos
siguientes:
1.- Un conjunto no vacío V de vértices o nodos, y
2.- Un conjunto E de aristas, donde cada arista une a dos vértices o a un mismo vértice.

EJEMPLO 4.1 La figura siguiente es un grafo:

Los nodos están

representados por puntos:
v1 , v2,v3 .
Las aristas son las líneas
que unen a los vértices:
e1 , e2 , e3 , e4 , e5 , e6 .
Para trabajar con la teoría
de grafos, es necesario
familiarizarse con los
términos siguientes.
LAZO: Cuando un vértice esta unido consigo mismo. En la figura anterior, son lazos las
aristas e6 y e3 .
 52
RAMAS O ARISTAS PARALELAS: Son aquellas que unen al mismo par de vértices.
En la figura , son aristas paralelas e1 y e2 .
VÉRTICE AISLADO: Vértice que no esta unido a otro o así mismo.

GRAFO SIMPLE: Es aquel que no tiene aristas paralelas ni lazos.

VALENCIA O GRADO DE UN VÉRTICE: Sea G un grafo y v un vértice de G. El
grado de v , denotado por grad (v) es el número de aristas que salen de v . Una arista
que sea un lazo se cuenta dos veces. Por ejemplo, en la figura que nos está sirviendo de
ejemplo, observamos que :

grad (v1 ) = 5
grad (v3 ) = 2
grad (v2 ) = 5

GRAFOS BIPARTITOS Y GRAFOS COMPLETOS. Sea V un conjunto de n vértices

El grafo completo sobre V de orden n , que se denota K n , es un grafo no dirigido sin
lazos tal que para todos a, b ∈ V , a ≠ b, existe una arista {a, b} . Es decir, un grafo simple
es completo si y sólo si todos sus vértices distintos están conectados entre sí por
exactamente una arista. Por ejemplo

Grafo completo K 3 Grafo completo K 4

Se le llama Grafo bipartito si se le puede dividir en dos conjuntos ajenos V1 y V2 , de

modo que cada arista de dicho grafo conecte a dos vértices, uno que esté en V1 y el otro
en V2 . Si cada vértice de V1 está unido con los vértices de V2 , se tiene un grafo bipartito
completo. En el caso de que V1 tenga m vértices y V2 contenga n vértices, entonces
usaremos el símbolo K m ,n .

Por ejemplo, en las figuras siguientes se muestran los grafos bipartitos K 2,3 y
K 3,3 .Obsérvese como se advierten dos conjuntos de vértices V 1 ={a,b} y V2 = {c, d , e} ,para
el primer caso. Cabe aclarar que en este caso ambos ejemplos son grafos bipartitos
completos; pero quitando las aristas {b,e} y {b,d}, del primer grafo, seguiría siendo un
grafo bipartito, aunque ya no sería grafo bipartito completo.
 53

Grafo bipartito completo K 2,3 Grafo bipartito completo K 3,3

EJERCICIO 4.1
1)Dado el grafo de la figura

a) Escribir el conjunto de aristas.

b) Hallar los vértices.
c) Hallar los vértices aislados.
d) Hallar los lazos.
e) Hallar las aristas paralelas

2.- Dibujar un grafo simple con cuatro vértices y seis aristas si es que es posible.
3.-Se puede argumentar de una manera sencilla la veracidad del siguiente resultado: Sea G
un grafo con vértices v1 , v2 ..., vn . Entonces la suma de los grados de todos los vértices G es
igual a dos veces el número de aristas en G, es decir,

∑ grad ( v ) = 2 * ( número de aristas en G).Según este resultado, ¿Se puede dibujar un

i

grafo G con tres vértices v1 , v2 , v3 donde

a) grad ( v1 ) = 1
grad ( v2 ) = 2
grad ( v3 ) = 2 ?
 54
SOLUCIÓN.
No, ya que grad ( v1 ) + grad ( v2 ) + grad ( v3 ) =1 + 2 + 2 = 5 que es un número impar.
Entonces, por el teorema anterior, ese grafo no existe.
b) grad ( v1 ) = 2
grad ( v2 ) = 1
grad ( v3 ) = 3

©
¡ Intente hacer un grafo con las características del inciso (a)!. También intente hacer un
grafo con las características del inciso (b).
2.- Dibujar el grafo completo K 5

3.- Haga el dibujo del grafo bipartito K 4,2 . También haga el dibujo del grafo bipartito
completo K 4,2 .
4.2. REPRESENTACIÓN MATRICIAL DE GRAFOS.

Si G es un grafo no dirigido de n vértices y k aristas, usamos las siguientes matrices

para representar G.
Sea V = {v1 , v2 ,..., vn } .Definimos a la matriz de adyacencia A = (aij ) n×n donde
aij= 1, si {vi , v j } ∈ E y aij= 0 en otro caso.

Si E = {e1 , e2 ,..., ek }, la matriz de incidencia I es la matriz n × k (bij ) n×k tal que

bij = 1 si bij = 1 si vi es un vértice en la arista e j y bij = 0 en otro caso.

EJEMPLO 4.2.
(a) Encuentre las matrices de adyacencia e incidencia asociadas con el
grafo de la figura.
 55
Solución:
La matriz A de adyacencia es
v1 v2 v3 v4 v5
v1 0 1 1 0 1
v2 1 0 1 1 1
v3 1 1 1 1 1
v4 0 1 1 0 1
v5 1 1 1 1 1

La matriz de incidencia es I viene dada por :

e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11
v1 1 1 1 0 0 0 0 0 0 0 0
v2 0 0 1 1 1 1 0 0 0 0 0
v3 1 0 0 0 1 0 0 1 0 1 1
v4 0 0 0 0 0 1 0 1 1 0 0
v5 0 1 0 1 0 0 1 0 1 1 0

Sean x y y vértices, no necesariamente distintos, de un grafo no dirigido. Un camino

de x a y en dicho grafo es una sucesión alternada finita y sin lazos de vértices y aristas
del grafo . que comienza en el vértice x y termina en el vértice y .
La longitud de un camino es igual al número de aristas que hay en el camino.
Se puede demostrar que la potencia n de la matriz de adyacencia An , es una matriz cuya
entrada aij proporciona el número de caminos de longitud n que van del vértice i al
vértice j.
Por ejemplo, en nuestro caso A2 , es
3 2 3 3 3
2 4 4 2 4
3 4 5 3 5
3 2 3 3 3
3 4 5 3 5

La cual indica ,por ejemplo, que hay 4 caminos de longitud 2 entre el vértice
v2 y v3 .En efecto, dichos caminos son : v2v1v3, v2v4v3; v2v3v3; v2v5v3.
Además en la matriz de adyacencia , la suma de cada columna, en el caso de que no haya
lazos en el vértice correspondiente a la columna, es igual al grado de dicho vértice; en el
caso de que haya lazos,
grad (v) = {( suma de la columna para v)-1]+ 2( número de lazos en v).
 56
Por último, la suma de cada columna de I , la matriz de incidencia, es igual a 1 para un
lazo y 2 para una arista que no sea un lazo. ¿Puede decir por qué?.

EJERCICIOS 4.2.

1.- Obtenga las matrices de adyacencia A y de incidencia I para el grafo que se ve en la

figura :

(b)Obtenga A2 y diga cuántos y cuáles son los caminos de longitud 2 del vértice
v2 y v3 .

A grosso modo , un grafo es conexo si entre dos de sus vértices existe al menos una
sucesión de vértices y aristas que los conectan. En la práctica estos grafos son muy
importantes, por ejemplo, una red de computadoras es una gráfica conexa.

4.2 GRAFOS CONEXOS.

Sea G = (V, E), un grafo no dirigido. Decimos que G es conexo si existe un camino
(trayectoria) simple entre cualesquiera dos vértices distintos de G. Un grafo que no
es conexo es disconexo.
En la práctica estos grafos son muy importantes, por ejemplo, una red de
computadoras o una red de distribución de gas o petróleo, o bien una red de carreteras
son una gráfica conexa.
Continuando con nuestro tema de los caminos ( trayectorias) entre los vértices de un
grafo, nos conviene analizar las siguientes definiciones, a fin aplicarlas en el estudio
de las gráficas conexas:
 57
TRAYECTORIA: Sean u y v dos vértices de un grafo G. Como ya fue mencionado
en el parágrafo anterior, una trayectoria o camino de u a v es una sucesión alternada
de vértices y aristas de G. Esta sucesión empieza en u y termina en v.
TRAYECTORIA TRIVIAL: Si u y v son el mismo vértice, entonces la trayectoria
es trivial, sin aristas, y se denota por u o por v.
TRAYECTORIA SIMPLE: Una trayectoria simple de u a v es la que no tiene
vértices repetidos.
CIRCUITO O CICLO: Es una trayectoria que empieza y termina en el mismo
vértice y no tiene aristas repetidas.
CIRCUITO SIMPLE: Es una trayectoria que no tiene aristas ni vértices repetidos
excepto el primero y el último.
EJEMPLO 4.3. En el grafo de la figura , notamos ,por ejemplo que:

a) v1e1v2e6v4e3v3e2v2 , es una trayectoria ve v1 a v2 . Dicha trayectoria no es simple porque

se repite el vértice v2 .

b) v5e5v1e8v4e3v3e2v2e6v4e4v5 , es un circuito simple.

c) v2e2v3e3v4e4v5e5v1e1v2 , este es un circuito simple
e) v1e1v2e2v3e3v4e4v5 , es una trayectoria simple.
c) v1e8v4e3v3e7v1e8v4 , esta es una trayectoria no simple, puesto que se repite v1 .

EJERCICIO 4.3.
(a) Mostrar un ejemplo, si lo hay de trayectoria , trayectoria no simple, trayectorias simples,
circuitos y circuitos simples en el grafo dado :

(b)Identificar cuáles son trayectoria , trayectorias no simples, trayectorias simples, circuitos

y circuitos simples.
 58

CIRCUITOS EULERIANOS.
El tema de los Circuitos Eulerianos es uno de los problemas más antiguos en relación con
los grafos. Leonhard Euler, uno de los matemáticos más prolíficos de la historia, se ocupó
del problema de los Puentes de Königsberg: La historia cuenta que en Königsberg ,
existía un río en el cual había dos islas conectadas entre sí y a tierra firme como se muestra
en la figura siguiente:

La gente de ese pueblo se preguntaba si era posible caminar por cada puente una sola vez,
si se comenzara en una de las orillas o en una de las islas, y regresar al punto de partida.
Euler pensó que este problema era equivalente a analizar al grafo siguiente:

Donde A y C son las orillas del río, B es la isla más grande, D es la isla más pequeña.
Euler , en 1736 descubrió el siguiente resultado general que nos permite decidir en qué
condiciones un grafo tiene un circuito euleriano:
Sea G un grafo. G contiene un grafo euleriano si y sólo si
1.- G es conexo
2.- Cada vértice de G es de grado par.
 59
Así que llegó a la conclusión de que en el problema de los Puentes de Königsberg, no era
posible tal recorrido, puesto que , por ejemplo , el vértice D es de grado impar. Tenemos la
siguiente definición general:
Sea G un grafo. Un circuito en G que contiene a todas las aristas de G recibe el
nombre de circuito euleriano.
EJEMPLO 4.4. Encontrar un circuito euleriano en el grafo siguiente:

Solución: El grafo dado sí tiene un circuito de Euler , debido a que cada uno de sus
vértices tiene grado par. Por ejemplo el circuito v1e1v2 e8 v4 e3 v3 e2 v2 e9 v3 e7 v1e6 v4 e4 v5 e5 e5 v1 ,. Es
tipo euleriano; desde luego, usted puede encontrar alguno distinto a este.
Ahora bien, en ciertos contextos se desea saber si es posible hacer no un circuito , sino un
recorrido (un camino que puede ser abierto, no cerrado como un circuito). El resultado
siguiente impone las condiciones en las cuales eso es posible:
Un grafo no dirigido sin vértices aislados tiene un recorrido de Euler si y sólo si dicho
grafo es conexo y tiene exactamente dos vértices de grado impar.

CIRCUITOS HALMILTONIANOS 6.
Es aquel en donde todos los vértices de un grafo aparecen solo una vez, (excepto el primero
y el último, que son el mismo), y puede incluir o no a cada arista.
Por ejemplo , el grafo (a) sí tiene un circuito de Hamilton, como el que se encuentra
caminando por toda la periferia; sin embargo el circuito de la figura (b) no tiene un circuito
de Hamilton.
(a) (b)

6
Se le llama así en honor al matemático irlandés William Rowan Hamilton (1805-1864), quien presentó el
problema en 1859 en forma de un juego que consistía n visitar todas las ciudades que aparecían en forma de
punto en los vértices de un dodecaedro.
 60

EJERCICIO 4.4.
1.- Determinar cual de los grafos siguientes contiene un circuito euleriano. Si es así,
proceder a localizarlo.

2.- Encontrar un recorrido euleriano para el subgrafo que resulta de eliminar la arista e9 , en
el grafo del inciso (a) del problema anterior.
3.- Encontrar un circuito hamiltoniano para cada uno de los grafos siguientes.

(a) (b)

3.- Demostrar que el grafo siguiente no tiene un circuito hamiltoniano.

 61

4.- La figura siguiente muestra tres islas unidas a tierra firme y entre sí mediante un sistema
de puentes. ¿Podrá realizarse un paseo comenzando en cualquier punto y regresando a el
después de haber pasado por cada puente una sola vez?.

5.-En 1859, Hamilton presentó el siguiente juego que consistía en pasar por cada punto del
dodecaedro exactamente una vez y regresar al punto de partida. Encontrar un circuito de
Hamilton en dicho grafo.

4.4 GRAFOS PONDERADOS.

Un grafo dirigido conexo y sin lazos es ponderado si a cada una de sus aristas se les
asocia un número real positivo que llamaremos peso o valor, al cual denotaremos con
el símbolo p (e) o p (a, b) ,si e = (a, b) . Si x y y son vértices del grafo, pero no
están conectados entre sí (no son adyacentes), se define p ( x, y ) = ∞ .
El estudio de estos grafos está asociado a problemas de minimización de costos u
optimización de recursos. Como por ejemplo, determinar la menor cantidad de tubería
para conectar a una red de distribución de gas; o por ejemplo, la determinación del
menor costo en combustible al recorrer una ruta de distribución.
Existe un algoritmo, desarrollado por el especialista en programación Edsger Wybe
Dijkstra (1930-2002) en 1959 ,el cual proporciona el camino más corta entre
cualesquiera dos vértices de un grafo ponderado.
 62
ALGORITMO DEL CAMINO MÁS CORTO DE DIJKSTRA.
Paso 1. Haga el contador i=0 y S0 = {v0 }. Etiquete v0 con (0,-) y cada v ≠ v0 con
( ∞, − ) .
Si n=1, entonces V = {v0 } y el problema está resuelto.
Si n > 1 , continúe con el paso 2.

Paso 2 . Para cada v ∈ S i ,reemplace (cuando sea posible) la etiqueta de v por nueva
etiqueta final ( ( L(v), y ) , donde

=L (v ) mín{L(v), L(u ) + p(u, v)}

u∈Si

Y y es un vértice en Si que produce el L(v) mínimo. Si efectivamente hacemos un

reemplazo, esto se debe al hecho que podemos ir de v0 a v y recorrer una distancia más
corta si recorremos un camino que incluye una arista ( y, v) .]

Paso 3. Si cada vértice de Si (para algún 0 ≤ i ≤ n − 2 ) tiene la etiqueta (∞, −) , entonces

el grafo etiquetado contiene la información que estamos buscando.
Si no, existe al menos un vértice v ∈ S i que no está etiquetado como (∞, −) y realizamos
las siguientes tareas:
1) Seleccionamos un vértice vi +1 tal que L(vi +1 ) sea mínimo (para todo v de este tipo).
Puede haber varios de estos vértices , en cuyo caso podemos elegir cualquiera de los
posibles candidatos . el vértice vi +1 es un elemento de Si que es el más cercano a v0 .
2) Asignamos Si ∪ {vi +1 } a S i +1 .
3) Incrementamos el contador i en 1 . Si i= n − 1 , el grafo etiquetado contiene la
información deseada . Si i < n − 1 , regresamos al paso 2..

EJEMPLO 4.5. Aplicar el algoritmo del camino más corto para determinar la distancia
más corta del vértice c a cada uno de los otros cinco vértices del grafo de la figura
adjunta.

Aplicando el algoritmo Dijkstra, descrito antes, determinaremos la distancia más corta del
vértice c(v ) a cada uno de los otro cinco vértices de G .

Iniciación: ( i = 0 ) . Sea S = {c} . Etiquetamos c como (0,-) y los demás vértices de G

con ( ∞, − ) .
 63
Primera iteración: ( S = {a, b, f , g , h} ) . En este caso i = 0 en el paso 2 y encontramos por
ejemplo, que
L(a ) = mín { L(a ), L(c) + p (c, a )}

mín {∞, 0 + ∞} = ∞, misma que

L( f ) = mín { L( f ), L(c) + p(c, f )}

mín {∞, 0 + 6} =
6 misma que

Cálculos similares muestran que L(b) = L( g ) =∞ y L ( h) = 11 . Así, etiquetamos el

vértice f con (6, c) y el vértice h con (11, c) . Los demás vértices de S siguen etiquetados
con ( ∞, − ) . Véase en la figura (b), que aparece abajo.

En el paso 3 vemos que f es el vértice de v1 en el S más cercano de v por lo que

asignamos a S1 el conjunto S ∪ {c, f } e incrementamos el contador i a 1.

como i =1 < 5(=6 − 1) , regresamos al paso 2.

Segunda interación: ( S1 = {a, b, c, h}) . Ahora, i =1 en el paso 2; cada v ∈ S1 hacemos

L(v) = mín { L(v), L(u ) + p (u , v)} de donde obtenemos

L(a ) = mín { L(a ), L(c) + p (c, a ) + L( f ) + p ( f , a )}

mín {∞, 0 + ∞, 6 + 11} =
17
por lo que etiquetamos el vértice a como (17, f ) . De manera similar vemos que
L(b) = mín {∞, 0 + ∞, 6 + ∞} = ∞
L( g ) = mín { {∞, 0 + ∞, 6 + 9} =15
L(h) = mín {11, 0 + 11, 6 + 4} = 10
 64

[Con estos resultados obtenemos el etiquetado de la figura ( b)]. En el paso 3 vemos que el
vértice es v2 es h , pues h ∈ S1 y L(h) es un mínimo. Entonces asignamos aS 2 si el
conjunto S1 ∪ {h} = {c, f , h} , incrementamos el contador a 2 y como 2 < 5, el algoritmo
nos lleva de nuevo al paso 2.

( )
Tercera iteración: S 2 = {a, b, g} . Como i = 2 ene le paso 2, ahora calculamos.
L(a ) = mín { L(a ), L(u ) + p (a, u )}
mín {17, 0 + ∞, 6 + 11,10 + 11} =17
(así la etiqueta de a no cambia)
L(b) = mín {∞, 0 + ∞, 6 + 1 0, ∞} =∞
( la etiqueta de b sigue siendo ∞ ).
L( g ) = mín {15, 0 + ∞, 6 + 9,10 + 4}= 14 < 15
por lo que la etiqueta de g cambia a (14, h) puesto que 14= L(h) + p (h, g ) . Entre los
vértices de S 2 , g es el más cercano a v puesto que L( g ) es un mínimo. En el paso 3, el
vértice v3 se define como g y S3 =S 2 ∪ {g} ={c, f , h, g} . Incrementamos el contador i a
3> 5, y regresamos al paso 2.

( )
Cuarta iteración: S3 = {a, b,} . Con i =3, determinamos lo siguiente en el paso 2:

L(a ) = 17; L(b) = ∞ . (Así, las siguientes etiquetas no cambian durante esta

iteración). Hacemos v4 = a y S 4 = S3 S 4 = S3 ∑ S 4 =S3 ∪ {a} ={c, f , h, g , a} , en el paso

3. Entonces incrementa i =4 (<5) y regresamos al paso 2.

Quinta iteración: ( S = {b,})

4 en el caso, i =4 en el paso 2, y vemos que
L=(b) L(a ) + p (a, b) =17+5=22 . La etiqueta de b cambia por (22, a ). Entonces, v5 = b en
el paso 3, S5 es {c, f , h, g , a, b} e i se incrementa a 5. Pero ahora que i =5=| V |-1, el
proceso termina. Obtenemos El grafo etiquetado que se muestra en la siguiente figura.
 65

De las etiquetas de la figura anterior obtenemos las siguientes distancias más cortas de c a
los otros vértices de G .
1) d ( =
c, f ) L=
( f ) 16 2) d ( =
c, h ) L=
( h ) 10
3) d ( =
c, g ) L=
( g ) 14 4) d ( =
c, a ) L=
( a ) 17
5) d ( =
c, b ) L=
( b ) 22

Por ejemplo, para determinar un camino dirigido más corto de c a b , partimos del
vértice b , que tiene la etiqueta (22, a ) , por lo tanto, a es el predecesor de b en este
camino más corto. La etiqueta en a es (17, f ) , por lo que f procede a a en el camino.
Por último la etiqueta f es (6, c ), por lo que regresamos al vértice c y el camino
dirigido más corto de c a b determinado por el algoritmo está dado por las aristas
(c, f ), ( f , a ) y (a, b) .

EJERCICIO. 4.5
Determine el camino más corto del vértice a a los vértices c, f e i

2.- a) Aplique el algoritmo de Dijkstra al grafo de la figura siguiente, y determine la

distancia más corta del vértice a a los demás vértices del grafo.

b) Determine el camino simple más corte del vértice a a cada uno de los vértices f , g y h .
 66

3.- Determine la ruta más corta entre el nodo 1 y cualquier otro nodo de la red en la
siguiente figura.

GRAFOS ISOMORFOS.

Dos grafos G1 = (V1 , E1 ) y G2 = (V2 , E2 ) son isomorfos, si existe una función

f= V1 → V2 tal
1) que f es inyectiva; es decir; a cada vértice de V1 le asigna un vértice en V2 distinto
al asignado a cualquier otro.
2) Para todos los a, b ∈ V1 {a, b} ∈ E1 si sólo si { f (a ), f (b)} ∈ E2 .

NOTA: La correspondencia de vértices de un isomorfismo de grafos mantiene las

adyacencias y esto hace que se preserve la estructura de un grafo.

EJERCICIO. 4.6Demostrar que los grafos siguientes son isomorfos.

 67

Solución.
Si en los grafos (A) y (B) definimos f como:
f (a) = w f (c ) = y

f (b) = x f (d ) = z

b) Verifique que los siguientes grafos son isomorfos, dando una función que lo justifique

Solución. Aunque no podemos dar una función en forma directa; nos podemos dar cuenta
que los grafos son isomorfos, porque el primero al ser rotado a 90°, realmente reproduce al
segundo. De este modo podemos dar la siguiente función que los identifique.

=
f ( m) s , =
f ( n) r , =
f ( p) , =
f (q ) t

En este caso tenemos la correspondencia de aristas

{m, n} ↔ { f (m), f (n)} = {s, r},

{m, p} ↔ { f (m), f ( p )} = {s, ui},
{m, q} ↔ { f (m), f (q )} = {s, t},
{n, q} ↔ { f (n), f (q )} = {r , t},
{ p, q} ↔ { f ( p ), f (q )} ={u , t},
 68

EJERCICIO 4.7. Indicar en cada caso si son isomorfos los siguientes pares de grafos.

(a) (b)

GRAFOS PLANOS.

Un grafo (o multigrafo ) G es plano si podemos dibujarlo en el plano de modo que sus

aristas se intersecten sólo en los vértices del mismo .

EJEMPLOS.

(a) El grafo (a) es un grafo plano, en el sentido de que se puede dibujar de modo que sus
aristas se intersecten sólo en sus vértices como en el grafo (b).

(a) (b)
 69

2.- El grafo siguiente también es plano , debido a que sus aristas sólo se intersectan en
sus vértices.

Nota: Un vértice solo se considera grafo plano.

EJERCICIO 4.7
(a) Dibuje tres grafos planos.
(b)El grafo siguiente se le llama Grafo de Petersen. Comprobar que el grafo de Petersen no
es plano..

Para finalizar nuestro tema de grafos, introducimos la siguiente definición: Sea G

un grafo no dirigido y sin lazos, tal que E ≠ ∅ . Una subdivisión elemental de
G resulta cuando se elimina una arista e = {u , w} de G y entonces las aristas
{u , v}, {v, w} se añaden a G − e ,donde v ∉ V .

Los grafos no dirigidos sin lazos G1 = (V1 , E1 ) y G2 = (V2 , E2 ) son homeomorfos

si son isomorfos o si ambos pueden obtenerse del mismo grafo no dirigido sin
lazos H por una sucesión de subdivisiones elementales.
 70
Siguiendo estas definiciones se plantea el siguiente resultado , debido al matemático polaco
K. Kuratowski:
Teorema de Kuratowski. Indica que:
Un grafo no es plano si y sólo si contiene un subgrafo homeomorfo a K 5 o K 3,3

Por ejemplo los grafos G y G1 son homeomorfos, debido a que en el primero se ha hecho
una subdivisión de su arista {a, b} , mediante la introducción del vértice w . Esto hace que
se obtenga, a partir del grafo G (figura (a) ) al grafo G1 que se muestra en al figura (b).
Obsérvese que se han añadido las aristas
Por ejemplo, el grafo de Petersen de la figura (a), tiene como subgrafo a la figura (b).

(a) (b)

Se puede dar la siguiente sucesión de subdivisiones hasta al finar obtener un subgrafo

homeomorfo a K 3,3 :
 71

También se tiene el siguiente resultado debido a L. Euler sobre una relación entre el
número de regiones en que un grafo divide al plano , su número de vértices v y su número
de aristas e:
Teorema de Euler Sobre Grafos Planos. Sea G=(V,E) un grafo o multigrafo plano
conexo con V = v y E = e . Sea r el número de regiones en el plano determinadas por
una inmersión (o representación) plana de G ; una de estas regiones tiene un área infinita
y se conoce región infinita . Entonces v − e + r =2.

En efecto, considere por ejemplo el grafo plano .En este caso como puede notar existen
v=3 vérices; el número de aristas es igual a e=3; el número de regiones es r=2 (la interna
y la externa que es infinita). Por lo tanto: 3-3+2=2.

Ahora, si observamos el siguiente ejemplo, también

verificamos que v=4; e=6; r=4. Por tanto:
4-6+4=2.
 72
EJERCICIO 4.8. Indicar si los grafos siguientes cumplen con la relación de
Euler.

(a) (b)
 73

UNIDAD V
ARBOLES

Objetivo:

En esta unidad, el alumno

 Conocerá la terminología básica de la teoría de árboles.
 Aplicará la teoría de árboles para optimizar códigos (Huffman)
 Aprenderá a utilizar los árboles binarios para ordenar series de
símbolos, según alguna convención.
 Aplicará los árboles para generar notaciones para expresiones
algebraicas ( notación polaca de Lukasiewicz).
 Conocerá el algoritmo de Pri m para optimizar una ruta.
 Aplicará los árboles en el análisis de juegos.
 74

5.1 DEFINICIÓN DE UN ÁRBOL

Otra clase de grafos, llamados árboles, son grafos que no tienen circuitos ( de
modo que no pueden tener aristas paralelas ni lazos.). A menudo es necesario
utilizar árboles en la ciencia de la computación.

Propiedades de los árboles.

ÁRBOL: Sea T un grafo. T recibe el nombre de árbol si y sólo si

a) T es convexo.
b) T no contiene circuitos (excepto los triviales).

A un conjunto de árboles se le llama bosque.

EJEMPLO 5.1

Los grafos (a) y (b) y (c) son árboles.

(a) (b) (c)

Sin embargo, los grafos (d) y (e) y ( f) no son árboles, el primero porque no es
conexo, y el segundo porque tiene un lazo; mientras que el tercero no es un árbol
porque forma circuitos.

(d) (e) (f)

 75
EJERCICIOS 5.1

1.- Dibujar todos los árboles distintos que tengan tres vértices.

2.- Determinar por qué cada grafo de las siguientes figuras no presenta un árbol.

El teorema siguiente nos permite caracterizar un árbol:

Teorema: Sea un G grafo conexo que tiene n vértices. G es u árbol si sólo si

tiene exactamente n − 1 aristas.

EJERCICIO 5.2. Verifique el resultado anterior usando como grafos de prueba a

todos los grafos del ejemplo 5.1.

Existe un tipo especial de árbol, llamado árbol con raíz que es útil en la ciencia
de la computación. (A un árbol que no esté enraizado se le llama árbol libre).

Las características de un árbol con raíz son:

Raíz: Si v se distingue de los otros vértices de T , entonces T recibe el nombre

de árbol con raíz y v se denomina raíz.

Hijo: Si u es adyacente a v pero se encuentra más lejos de la raíz de lo que esta

v entonces a u se le llama hijo de v . Si u y w son los únicos hijos de v , con la u
localizado a la izquierda de u y w a la derecha de v , entonces u y w se llaman,
respectivamente hijos izquierdos y derecho de v .

Hoja: Si el vértice u no tiene hijos, entonces u se le llama hoja ( o vértice

terminal).
 76
Si u tiene uno o dos hijos, entonces u se denomina vértice interno.
Los descendientes del vértice u es el conjunto que consiste en todos los hijos de
u junto con los descendientes de esos hijos.

EJEMPLO 5.2. Considere el siguiente árbol con raíz T

a) ¿Cuál es la raíz de T ?
b) ¿Es T es un árbol binario? Si es así, encontrar los hijos izquiedo y derecho de
cada vértice.
c) Encontrar las hojas y los vértices internos de T
d) Encontrar los descendientes de los vértices a y c .

Solución:

a) El vértice a se distingue por ser el único localizado en la copa del árbol. Por
lo tanto a es la raíz.
b) Sí, cada vértice tiene dos hijos, un hijo o ninguno. La tabla siguiente indica
los hijos de cada vértice.

vértice Hijo Hijo

izquierdo derecho
a b Ninguno
b Ninguno Ninguno
c d e
d Ninguno f
e g h c) Las hojas son los vértices que
no tienen hijos. Estos son b , g
f Ninguno Ninguno
g y h . L os vértices internos son
Ninguno Ninguno
los que tienen uno o dos hijos.
h Ninguno Ninguno
Estos son c , d y e .
Los descendientes de a son b , c , d , e , f , g , h . Los descendientes de c son
d ,e, f , g ,h.

Árbol binario: Si T tiene raíz y cada vértice de T tiene hijos izquierdo y derecho,
o hijo izquierdo o hijo derecho, o no tiene hijos, entonces T se denomina árbol
binario. Por otro lado, si en el árbol binario los vértices tienen exactamente dos
hijos o ninguno se les llama árboles binarios completos.

Sea T un árbol binario y sean u y v dos vértices de T . El árbol con raíz en u es

el árbol que consiste en la raíz u , todos sus descendientes y todas las aristas que
 77
los unen. Si u es el hijo izquierdo de v , entonces el subárbol con raíz en u se
llama subárbol izquierdo de u , y si u es el hijo derecho de v , entonces el
subárbol con raíz se llama subárbol derecho de v con raíz en u . Si u es una
hoja, entonces el subárbol con raíz en u se denomina subárbol trivial.

EJEMPLO 5.3 .Considere el siguiente árbol binario.

a) Encontrar los subárboles izquierdo y derecho de v .

b) Encontrar el subárbol con raíz en r .

Solución: La raíz es el vértice v . En la siguiente figura se dan , respectivamente

los subárboles izquierdo y derecho de dicho grafo.

c) en la figura siguiente se da el subárbol con raíz en r .

 78

Continuando con la presentación de la terminología básica de la teoría de árboles,

definimos a un árbol jerarquizado cuando se establecen niveles de mayor a
menor ,partiendo de la raíz del árbol. Por ejemplo, en un organigrama:

DIRECTOR GENERAL

SUBDIRECTOR DE RECURSOS HUMANOS SUBDIRECTOS ACADEMICO SUBDIRECTOR DE VINCULACIÓN

CONTADOR MAESTROS

También , si en cada nodo de un árbol tomamos una decisión, a dicho árbol le

llamaremos árbol de decisión . Por ejemplo, un árbol como este se puede
utilizar para resolver un viejo acertijo de toma de decisiones, llamado El juego de
las ocho monedas. En tal juego, se supone que tenemos ocho monedas , una
de las cuales es falsa, por lo cual pesa más o menos que las otras siete. El juego
consiste en analizar todas las posibilidades de formas de pesar a las monedas con
una única balanza, hasta descubrir a la que es falsa. Está claro que podemos
dividir, al principio a las monedas en dos grupos de cuatro, y poniéndolas en la
balanza, podremos descubrir el grupo en la que está la moneda falsa; luego a
dicho subgrupo se le divide a su vez en otro dos subgrupos de tamaño dos, etc.
Dependiendo de cómo tomemos a las monedas, se generan las dos posibilidades
que se ven en la figura:

solución con árbol binario solución con árbol ternario

 79
BÚSQUEDAS A LO LARGO Y A LO ANCHO.

La búsqueda a lo largo o a lo ancho sirven para establecer una búsqueda de

alguna clave (nodo) ubicado en un árbol.Estos conceptos después nos servirán
para establecer recorridos en diversos órdenes a través de un árbol.

Búsqueda a lo largo (en profundidad).

Sea G = (V , E ) un grafo conexo no dirigido con r ∈ V . A partir de r , construimos

un camino simple en G , lo más largo posible. Si este camino simple incluye
todas los vértices de V , entonces el camino simple es un árbol recubridor T de
nuestro grafo.. En caso contrario, sean x, y los dos últimos vértices visitados por
este camino, con y como último vértice. Después retrocedemos al vértice x y
construimos un segundo camino simple en G, lo más largo posible, a partir de x
que no incluya a los vértices ya visitados. Si no existe tal camino, retrocedemos al
padre p de x y vemos lo lejos que podemos llegar a partir de p ,construyendo
un camino simple , lo más largo posible, sin ir a vértices ya visitados) hasta una
nueva hoja y1 . En caso de que todas las aristas que parten de p conduzcan a
vértices ya visitados, retrocedemos un nivel más y continuamos el proceso.
Puesto que el grafo es conexo y finito , este procedimiento, llamado búsqueda a
lo largo, determinará finalmente el árbol recubridor T de G, donde r se
considera la raíz de T . Por medio de T podemos ordenar los vértices de G en un
orden llamado orden previo que después definiremos.

Para mayor precisión, damos enseguida el algoritmo exacto de búsqueda a lo

largo:

Sea G = (V .E ), un grafo no dirigido, conexo, sin lazos, tal que V = n y donde

los vértices están ordenados como v1 , v2 ,..., vn . Para encontrar el árbol
recubridor en profundidad, ordenado con raíz, aplicamos el siguiente algoritmo,
donde usamos la variable v para guardar el vértice analizado en un momento
dado.

Algoritmo de Búsqueda en Profundidad o a lo Largo.

Paso 1. Se asigna v1 a la variable v y se inicializa T como un árbol que

consta solamente de este vértice . ( El vértice v1 será la raíz del árbol recubridor
que se va a desarrollar)

Paso 2. Seleccionamos el subíndice más pequeño i 2 ≤ i ≤ n , tal que y vi no

ha sido visitado todavía.
 80

Si no se encuentra tal subíndice , entonces se va al paso 3. En caso contrario ,

se hace lo siguiente: (1) Añadimos a la arista {v, vi } al árbol T; (2) asignamos vi
a v (3) regresamos al paso 2.

Paso 3. Si v = vi , el árbol T es el árbol recubridor (ordenado, con raíz ) del

orden dado.

Paso 4. SI v ≠ vi , retrocedemos desde v. Si u es el vértice asignado a v en

T , entonces asignamos u a v y regresamos al paso 2..

EJEMPLO 5. 4. Determine el árbol recubridor para el grafo siguiente mediante el

algoritmo de búsqueda a lo largo.

Solución:

En este caso el orden de los vértices es alfabético:

a, b, c, d , e, f , g , h, i, j

Asignamos primero el vértice a a la variable v e

inicializamos T sólo con dicho vértice (el cual jugará el
papel de raíz). En el paso 2 , vemos que el vértice b es el
primer vértice tal que no ha sido visitado aún, por lo que agregamos la arista
{a, b} a T , asignamos b a v y regresamos al paso 2.

Para v = b , vemos que el primer vértice ( no visitado todavía) y que proporciona

una nueva arista al árbol recubridor es d . En consecuencia, agregamos la arista
{b, d } a T , asignamos d a v y volvemos al paso 2.

Sin embargo, esta vez no existe un nuevo vértice que podamos obtener de d ,
puesto que los vértices a y b ya han sido visitados., por lo que vamos al paso
3. Pero en este caso el valor de v es d , no a ; así que vamos al paso 4.
Retroceder de h a e a b a a . Cuando v tiene asignado el vértice a por segunda
vez, se obtiene la nueva arista {e, f } y {e, h} . Después agregamos las aristas
{c, g},{g , i} y {g , j} . En este momento hemos visitado todos los vértices de G , por
lo que retrocedemos de j a g a c a a . Con v =a de nuevo, regresamos al paso
2 y de ahí al paso 3, donde termina el proceso.
 81
El árbol resultante T = (V , E1 ) aparecen en la parte (b) de la siguiente figura.

Un segundo método para buscar los vértices de un grafo no dirigido conexo con
lazos es la búsqueda en anchura. Aquí designamos un vértice como la raíz y
recorremos todos los vértices adyacentes a la raíz. Desde cada hijo de la raíz
podemos recorrer los vértices ( no visitados) que son adyacentes a uno de estos
hijos. Al continuar este proceso, nunca enumeraremos un vértice dos veces, de
modo que no se construye un ciclo; como G es finito, el proceso termina en cierto
momento.

Cierta estructura de datos es útil para desarrollar un algoritmo en este segundo

método de búsqueda. Una cola es una lista ordenada en la que los elementos se
insertan en un extremo ( el final ) de la lista y se eliminan del otro extremo ( el
frente). En consecuencia, una cola se conoce como una estructura FIFO ( “ first-in,
first-out” , primero en entrar, primero en salir).

Como en la búsqueda en profundidad, nuevamente asignamos un orden a los

vértices de nuestro grafo.
Comenzamos con un grafo no dirigido conexo sin lazos G = (V , E ) , donde | V | = n
y los vértices están ordenados como v1 , v2 , v3 ....vn . El siguiente algoritmo genera el
árbol recubridor en anchura (ordenado con raíz) T de G para el ordenador dado.

Algoritmo de búsqueda de anchura.

Paso 1: Insertemos el vértice v1 en la cola Q e iniciamos en T como el árbol

formado por este único vértice v1 ( la raíz de la versión final T .
Paso 2: Eliminamos los vértices del frente de Q . Al eliminar un vértice v1
consideremos v1 para cada 2 ≤ i ≤ n . Si la arista (v, v1 ) ∈ E y v1 no ha sido visitado,
agregamos la arista a T . Si examinamos todos los vértices ya que estaban en Q y
no obtenemos aristas nuevas, el árbol T (generado hasta este momento) es el
árbol recubridor (ordenado con la raíz) del orden dado.

Paso 3: Insertamos los vértices adyacentes a cada v ( del paso 2) en el final de la

cola Q , según el orden en que fueron visitados por primera vez. Después
regresamos al paso 2.
 82

EJEMPLO 5.4

Utilizaremos el grafo de la siguiente figura con el orden a, b, c, d , e, f , g , h, i, j para

ilustrar el uso del algoritmo de búsqueda de anchura.

a)
1.-Partimos del vértice a , Insertamos a en Q e
inicializamos T con este vértice ( la raíz del árbol
resultante).
2.- En el paso 2 eliminamos a de Q y visitamos los
vértices adyacentes a él:
b, c, d (estos vértices no han sido visitados previamente ).
Esto permite añadir las aristas {a, b} , {a, c} , {a, d } .
3.- En el paso 3, insertamos b, c, d (en este orden) en Q y
regresamos al paso 2. Ahora eliminamos estos vértices de
b Q y visitamos los vértices adyacentes a ellos (no visitados
antes de acuerdo con el orden dado de los vértices de G ,
De aquí obtenemos los nuevos vértices e, g y las aristas
{b, e} ,{c, g} que agregamos a T .
4.- Después vamos al paso 3 e insertamos e, g en Q .
Regresamos al paso 2, eliminamos cada uno de estos
vértices de Q .y encontramos, en orden, los nuevos

vértices ( no visitados previamente ) f , h, e, i . Esto nos permite añadir las aristas

al árbol T .
De nuevo regresamos al paso 3, donde insertamos los vértices f , h, e, i, j en Q .
Pero ahora cuando vamos al paso 2 y eliminamos los vértices de Q , no
encontramos vértices nuevos ( no visitados previamente). En consecuencia el
árbol T de la siguiente figura es el árbol recubridor de anchura de G , para el
orden dado. ( El árbol T1 que aparece en la parte de abajo surge con el orden
j , i, h, g , f , e, d , c, b, a. ).

ARBOLES GENERADORES MINIMALES.

Un árbol generador de un grafo G es un subgrafo del mismo el cual es un árbol

que contiene todos los vértices de G.

Si se asignan pesos p (i ) a las aristas de dicho árbol generador y la suma de

dichos pesos es la mínima posible, entonces a dicho árbol se le llama árbol
generador minimal.
 83
Los árboles generadores minimales aparecen en forma natural en varios
problemas, como por ejemplo, al diseñar una red de distribución de agua o gas,
en donde lo que interesa es ,por ejemplo, minimizar la cantidad de material
utilizado. Robert Prim dio el siguiente algoritmo para determinar a un árbol
minimal en tales casos.

5.2. ALGORITMO DE PRIM.

Paso 1: Hacemos el contador i = 1 y colocamos un vértice arbitrario v1 ∈ V en el

conjunto P . Definimos N= V − {v1} y T = ∅ .

Paso 2: 1 ≤ i ≤ n − 1 , donde | V |= n ,=sean P (= v1 , v2 ..., vi ), T {e1 , e2 ,..., ei−1} y

N= V − P añadimos a T la arista más corta ( la arista de peso minimal) de G que
conecta un vértice x en P con un vértice y (= vi+1 ) en N . Colocamos y en P y lo
eliminamos de N .

Paso 3: Incrementamos el contador en 1.

Si i = n el subgrafo de G determinado por las aristas e1 , e2 ,..., ei−1 es conexo, con n
vértices y n -1 aristas y es un árbol óptimo para G .
Si i < n , regresamos al paso 2.

EJEMPLO 5.4 Usamos este algoritmo para encontrar un árbol óptimo para el
grafo siguiente.

Solución.

. El algoritmo de Prim genera un árbol óptimo de la forma siguiente.

 84

El árbol generador minimal es el que se muestra en la figura:

EJERCICIO 5.2

2.- a) Aplique el algoritmo el algoritmo de Prim para determinar el árbol

recubridor minimal para el siguiente grafo.

2.- La siguiente tabla proporciona información acerca de la distancia existente ( en

millas ) entre pares de ciudades en el estado norteamericano de Indiana, E. U.
 85
Se construirá un sistema de carreteras para unir estas siete ciudades. Determine
las carreteras que deben construirse para minimizar el costo de construcción. (
Suponga que el costo de construcción de una milla de carretera es el mismo entre
cualquier par de ciudades ).

3.- Se desea establecer una red de comunicación por cable que enlace las
ciudades que se ven en la figura. Determine cómo deben conectarse las
ciudades de modo que se minimice la longitud total de cable que se utilice.

El algoritmo de Prim representa un ejemplo de lo que es un algoritmo voraz, en

el sentido de que en cada iteración va agotando los pesos de las aristas ,para
finalmente obtener el mejor resultado posible.
 86

5.3. TIPOS DE RECORRIDOS DE UN ARBOL.

Sea T = (V , E ) un árbol con raíz r .Si T no tienen otros vértices, entonces la

misma raíz es el recorrido en orden previo y orden posterior de T . Si |V|>1, sean
T1 , T2 , T3 ...Tk los subárboles de T de izquierda a derecha.

a) El recorrido en orden previo de T visita primero r y después

recore los vértices de T1 en orden previo, después los vértices de
T2 en orden previo y así sucesivamente, hasta recorrer los vértices de
TK en orden previo.
b) El recorrido en orden posterior de T recorre en orden posterior los
vértices de los T1 , T2 ,...Tk para después llegar a la raíz.
©recorrido de orden simetrico: Sea T = (V , E ) un árbol binario con
raíz, donde r es l raíz.

1) Si |V | =1, entonces el vértice r es el recorrido en orden simétrico de T .

2) Si |V |>1, sean T1 Y T0 los subárboles izquierdo y derecho de T .El recorrido
en orden simétrico de T recorre primero los vértices de T1 en orden
simétrico, después visita la raíz y luego recorre, en el orden simétrico, los
vértices de T0 .

EJEMPLO 5.5

Si aplicamos el recorrido en el orden simétrico al árbol binario con raíz que se

muestra en la siguiente figura, veremos que la lista de orden simétrico para estos
vértices es p, j , q, f , c, k , g , a, d , r , b, h, s, m, e, i, t , n, u. Las otras lecturas son:
Orden posterior: p,q,j,f,k,g,c,d,a,s,m,h,t,u,n,i,,e,b,r
Orden previo: r,a,c,f,j,p,q,g,k,d,b,e,h,m,s,i,n,f,u.
 87

EJERCICIO 5.2. Dar los recorridos en orden previo, posterior y simétrico para los
siguientes árboles.

(1) (2)
 88

(3)

REPRESENTACIONES PREFIJAS, INTERFIJAS Y POSTFIJAS DE UNA

EXPRESIÓN ALGEBRAICA

Los árboles binarios se usan para representar expresiones algebraicas . Los

vértices del árbol son marcados con los números, las variables u operaciones que
conforman la expresión. Las hojas de un árbol se pueden marcar únicamente con
números o variables. Las operaciones como adición, sustracción, multiplicación,
división o potenciación solo pueden ser asignadas a los vértices internos. La
operación en cada vértice afecta a sus subárboles izquierdo y derecho, de
izquierda a derecha. Los dos ejemplos siguientes ilustran estos usos de los
árboles binarios.

A una operación en donde se especifica mediante un paréntesis a cada operación

se le llama Notación totalmente parentética. Por ejemplo
[(2 x − 3) /(2 − x)] + (6 x − 3) , está escrita en esta forma. Es claro que esta forma de
2

escribir a una expresión algebraica es necesaria para evitar ambigüedades.

EJEMPLO 5.5

1.- Usar un árbol binario para representar la expresión

(a) (x + y)/z (‘’/’’significa división).

(b) [(x – y)++2]/(x + y) (‘’**’’ significa potenciación)

SOLUCIÓN:

a) En esta expresión, el primer término es x , el segundo es y y la operación es *.

Por lo tanto, este valor, que se muestra en la figura siguiente debe tener su raíz en
* y debe tener dos subárboles, uno para cada término.
 89
b) Aquí, primero se suma x con y y luego se divide entre z . Esto significa que el
árbol debe tener a / como raíz y dos subárboles<. Un subárbol izquierdo con raíz
en + que suma a x con y y un subárbol derecho con raíz en z .

b) Para obtener el primer término, que es (x-y)**2, primero se resta y de x y

luego se eleva al cuadrado. Para obtener el segundo término, que es x + y , se
suma x con y . Por último, se divide estos términos. Esto significa que el árbol
debe tener raíz en / y debe tener dos subárboles, como se muestra en la siguiente
figura:

Una vez representada la operación en un árbol binario, se puede proceder a

leerla , generando tres lecturas: la lectura en orden previo, se le llama notación
en orden prefijo ( o notación polaca); a la lectura en orden simétrico, se le
llama orden interfijo y a la lectura en orden posterior, se le llama orden postfijo
(o notación polaca inversa).

EJEMPLO 5.6. Dar la expresión en notación polaca, en orden interfijo y en orden

posterior de la expresión [( x − y ) 2 ] /( x + y ) .

Solución: El árbol y a lo hemos obtenido antes en el ejemplo anterior. Leyendo a

dicho árbol en los ordenes especificados, se obtiene:

Orden previo (notación polaca): / ∧ − xy 2 + xy

Orden interfijo: x − y ∧ 2 / x + y
Orden postfija (notación polaca inversa): xy − 2 ∧ xy + /
 90

ORDENAMIENTOS

Suponga que se tienen un conjunto de números. Se le llama claves. S e tiene

interés en dos de las diversas operaciones que se pueden realizar en este
conjunto:

1.- Ordenamiento ( o clasificación) del conjunto.

2.- Exploración del conjunto ordenado para localizar cierta clave y, en el caso de
no encontrar la clave en el conjunto, añadirla en la posición derecha de manera
que se mantenga el ordenamiento del conjunto.

EJEMPLO 5.7.

(b) Usar un árbol binario para almacenar en orden creciente los elementos de
la siguiente lista de números: 7, 10,21, 3, 24, 23.
(c) Usar el árbol construido en (a) para buscar el número 19 en la lista. Si éste
no se encuentra, actualizar la lista agregándole el número.

SOLUCIÓN:

(a) Se empieza por seleccionar cualquier número de la lista para que sea la
raíz del árbol binario. Supóngase que se elige el 10 para que sea esta raíz.
Se dibujan los hijos izquierdo y derecho de 10, como se muestra a
continuación en la figura (a).
Luego se escoge otro número de la lista, por ejemplo 3. Ahora, 3 es menor
que 10, por lo que el hijo izquierdo de 10 se marca con 3 y luego se dibujan
los hijos izquierdo y derecho de 3, como se muestra en la figura (b).
Enseguida se escoge otro número de la lista, por ejemplo 21. Para ubicar a
21 en el árbol, se empieza en la raíz 10 y se compara con 21. Como 21 es
mayor que 10, se desciende hasta el hijo derecho de 10 . Éste no esta
marcado, por lo que se marca con 21 y luego se dibujan los hijos a la
izquierdo y derecho de este vértice., obsérvese en la figura (c).
Se continua del mismo modo. Se escoge el siguiente elemento de la lista,
por ejemplo 7. De nuevo se empieza en la raíz 10 y se compara con 7.
Como 7 es menor que 10, se desciende hasta el hijo izquierdo de 10, el
cual es el vértice marcado con 3. Se compara 7 con 3. Como es mayor que
3, entonces se desciende hasta el hijo derecho de 3. Este hijo no está
marcado, por consiguiente se marca con 7 y se dibujan los hijos izquierdo y
derecho de 7 obsérvese en la figura (d).
Supóngase que el número siguiente que se escoge de la lista es 24. Debido
a que 24 es mayor que 10, se desciende hasta el hijo derecho de 10.
Puesto que 24 es mayor que 21 se desciende hasta el hijo derecho de 21.
Este hijo no está marcado. POR lo tanto, se marca con 24 y se dibujan los
hijos izquierdo y derecho de 24 obsérvese en la figura (e)
 91

Para finalizar el último número de la lista es 23. Se empieza en la raíz 10.23 es

mayor que 10, por lo que se desciende hasta el hijo derecho de 10, el cual está
marcado como 21. Puesto que el 23 es mayor que el 21, entonces se
descendiente hasta el hijo derecho de 21, el cual cuál está marcado con 24.
Debido a que 23 es menor que 24, se desciende hasta el hijo izquierdo de 24, el
cuál no está marcado. Entonces se marca con 23 y se dibuja el hijo izquierdo y
derecho de 23 el cual se observa en la figura (f). Puesto que se a llegado ha un
vértice no marcado, se concluye que el número 19 y se dibujan los hijos izquierdo
y derecho de 19 en el inciso (g). Esto añade la clave 19 a la lista a la vez que
mantiene el orde3n creciente de los números en dicha lista.

Observe que la lectura en orden simétrico genera la serie de números ordenada:

3,7,10,19,21,23,24.
 92
EJERCICIO 5.3.

1.-Leer al árbol siguiente en orden previo, simétrico y posterior.

2.- Representar a la operación ( x − 3 y )3 /(2 − x) en notación polaca.

3.- En el siguiente árbol binario encontrar la expresión algebraica representada por
el árbol.

(a) (b) (c)

(d)

3- En los siguientes problemas se da una expresión algebraica. Usar un árbol

binario para representar la expresión.

(a) [( a + b )/ c] + d
(b) {1/[(a + b )^ 2]} – [(a + b) ^ c] + b

4. Ordene, mediante el uso de un árbol binario de búsqueda a la serie

13,4,5,9,17,41,22.
 93
CODIGO HUFFMAN.

Un conjunto P de sucesiones binarias (que representa un conjunto de símbolos)

es un código prefijo si ninguna de las sucesiones de P es el prefijo de otra
sucesión de P .

David Huffman ,diseñó una forma de encontrar un código binario con cadenas de
longitud óptima,según su frecuencia de uso. Básicamente se basa en los
resultados siguientes:

Lema: Si T es un árbol óptimo para los n pesos p1 ≤ p2 ≤ ... ≤ pn , entonces existe

un árbol óptimo para T en el que las hojas de pesos p1 y p2 son hermanos en el
nivel maximal (en T ).

Con este lema vemos lo que los pesos aparecen en los niveles superiores (lo que
produce números del nivel más alto) en un árbol óptimo.

Teorema:

Sea T un árbol óptimo para los pesos p1 + p2 , p3 ... pn donde p1 ≤ p2 ≤ ... ≤ pn . En

la hoja con peso de p1 + p2 colocamos un árbol binario (completo) de peso 1 y
asignamos los pesos p1 , p2 a los hijos (hojas) de esta hoja anterior. El nuevo
árbol binario T1 construido de esta forma es óptimo para los pesos p1 + p2 , p3 ... pn .

Demostración:

Sea T2 un árbol óptimo para los pesos p1 , p2 , ... pn donde las hojas
correspondientes a los pesos p1 , p2 son hermanos. Eliminamos las hojas de pesos
p1 , p2 y asignamos el peso p1 + p2 a su padre (ahora una hoja). Este árbol binario
completo se denota con T3 y P(T2= ) P(T3 ) + p1 + p2 . Además P(T1 )= P(T ) + p1 + p2 .
Puesto que T es óptimo , P(T ) ≤ P(T3 ) . Si P(T ) < P(T3 ) , entonces P(T1 ) < P(T3 ) ,
Entonces P (T1 ) < P (T2 ) , lo que contradice la elección de T2 como óptimo. Por lo
tanto, P(T ) = P(T3 ) y en consecuencia P (T1 ) < P (T2 ) .así T1 es óptimo para los
pesos p1 , p2 , ... pn .

EJEMPLO 5.9

Construyamos un código prefijo óptimo para los símbolos a, o, q, u , y, z que

aparecen con las frecuencias 20, 28, 4, 17,12, 7, respectivamente.
La figura siguiente muestra la construcción que sigue el procedimiento de
HUFFMAN.
94
 95
En la parte (b), se combinan los pesos 4 y 7, de modo que podamos considerar la
construcción para los pesos 11,12,17, 20, 28. En cada paso ( en las partes (c)-(f)
creamos un árbol con subárboles con raíz en los dos pesos menores. Estos dos
pesos menores pertenecen a vértices que antes o estaban aislados (un árbol
solamente con una raíz) o bien eran la raíz de un árbol anteriormente obtenido en
la construcción. De este último resultado, determinamos un código prefijo como

=
a :11 =
o 01 =
q 0000 u 10 y : 001 x : 0001

Podemos obtener diferentes códigos prefijos a partir de la forma en que

seleccionan los árboles T , T ' T , T ' y se asignan como subárboles izquierdo y
derecho en los pasos 2(a) y 2(b) de nuestro algoritmo, y a partir de las
asignaciones de 0 y1 a las ramas (aristas) de nuestro árbol (de Huffman) final.

EJERCICIO 5.5

1.- Para el código prefijo de la siguiente figura, decodifique las sucesiones (a)
1001111101; (b)10111100110001101; (c) 1101111110010

2.-Determine el código de Huffman para los símbolos p,q,r,s,t,u,v , cuyas

frecuencias de aparición son, respectivamente: 12, 17, 15,19,32,18.

ARBOLES DE JUEGO

Los árboles tienen una utilidad muy amplia,una de las cuales es tomarlos como
herramientas de decisión. Un juego es básicamente una sucesión de decisiones
que toma un jugador en cada etapa del juego. Por ejemplo:

EJEMPLO 5.4. Usar árboles para analizar a los juegos propuestos.

 96
1.- Un hombre tiene tiempo para jugar ruleta cinco veces a lo sumo. En cada juego
gana o pierde un dólar. El hombre empieza con un dólar y dejará de jugar si antes
de la quinta vez pierde todo su dinero o si gana tres dólares, esto es, si tiene
cuatro. Hallar el número de casos en que la apuesta puede ocurrir.

En siguiente diagrama de árbol, describe el camino en que la apuesta puede

suceder. Cada número del diagrama denota el número de dólares que el hombre
tiene en ese punto. Observamos que la apuesta puede suceder 11 maneras
diferentes. Obsérvese que él suspenderá la apuesta antes de que los cinco juegos
se hayan realizado en solamente tres de los casos.

2.- Los equipos A y B juegan en un torneo de baloncesto. El primer equipo que

gane dos juegos seguidos o un total de cuatro juegos gana el torneo. Hallar el
número de maneras como puede suceder el torneo.

SOLUCIÓN:

14 Maneras
2.-Un hombre tiene tiempo para jugar ruleta cinco veces. Gana o pierde un dólar
en cada jugada. El hombre empieza con dos dólares y dejará de jugar a la quinta
vez si pierde todo su dinero o si gana tres dólares ( esto es, complete 5 dólares).
Hallar el número de maneras como puede suceder el juego.

SOLUCIÓN:

20 maneras (como se muestras en el siguiente diagrama):

 97

EJERCICIO 5.4. Analice mediante un árbol el llamado juego del gato.

 98

BIBLIOGRAFIA

1.- Patrick Suples. Lógica Matemática. Ed. CECSA

2.- Liu. C.L . Elements of Discrete Mathematics. Springer-Verlag.

3.- Hasser Lasalle y Sullivan. Análisis Matemático..Ed.Trillas.

4.- Jonson y Baugh. Matemáticas Discretas.Ed. Interamericana.

6.-Grimaldi,Ralph. Matemática Discreta y Combinatoria