Pd mdi

Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología 1

Matemáticas discretas Programa desarrollado

Área de Ciencias Exactas, Ingenierías y Tecnología

Cuatrimestre TRES

Programa de la asignatura

Matemáticas discretas

Clave:

060910312/050910312

Agosto de 2011



SECRETARÍA DE EDUCACIÓN PÚBLICA

Alonso Lujambio Irazábal

SUBSECRETARÍA DE EDUCACIÓN SUPERIOR

Rodolfo Tuirán Gutiérrez

PROGRAMA DE EDUCACIÓN SUPERIOR ABIERTA Y A DISTANCIA

COORDINACIÓN GENERAL

Manuel Quintero Quintero

COORDINACIÓN ACADÉMICA

Soila del Carmen López Cuevas

DISEÑO INSTRUCCIONAL

Karla Contreras Chávez

EVALUACIÓN Y ACREDITACIÓN DE PROGRAMAS EDUCATIVOS

Karina Montaño

AGRADECEMOS LA COLABORACIÓN EN EL DESARROLLO DE ESTE MATERIAL A:

Mtro. Darío Ruiz Hernández

Secretaría de Educación Pública, 2011



Tabla de contenidos

I. Información general de la asignatura _________________________________________________ 6

a. Ficha de identificación ___________________________________________________________ 6

b. Descripción ___________________________________________________________________ 6

c. Propósito _____________________________________________________________________ 7

II. Fundamentación de la asignatura ____________________________________________________ 7

III. Competencia(s) a desarrollar _______________________________________________________ 7

IV. Temario _______________________________________________________________________ 8

V. Metodología de trabajo ____________________________________________________________ 9

VI. Evaluación _____________________________________________________________________ 9

VII. Materiales de apoyo ____________________________________________________________ 10

VIII. Desarrollo de contenidos por unidad _______________________________________________ 11

UNIDAD 1. SISTEMAS NUMÉRICOS __________________________________________________ 11

Propósito de la unidad ____________________________________________________________ 11

Competencia específica ___________________________________________________________ 11

Presentación de la unidad _________________________________________________________ 11

1.1. Sistemas numéricos __________________________________________________________ 12

1.1.1. Características de los sistemas numéricos _____________________________________ 12

1.1.2. Sistema decimal __________________________________________________________ 13

1.1.3. Sistema binario ___________________________________________________________ 13

1.1.4. Sistema octal ____________________________________________________________ 14

1.1.5. Sistema hexadecimal ______________________________________________________ 15

Actividad 1. Aplicación de las representaciones numéricas ______________________________ 15

1.2. Conversiones _______________________________________________________________ 16

1.2.1. Conversiones decimal-binario _______________________________________________ 16

Actividad 2. Conversión de decimal a binario ________________________________________ 19

1.2.2. Conversiones binario-octal-hexadecimal _______________________________________ 19

Actividad 3. Conversiones binario- octal-hexadecimal __________________________________ 22

1.2.3. Conversiones entre distintas bases ___________________________________________ 22

Actividad 4. Conversiones entre distintas bases ______________________________________ 25

1.3. Operaciones binarias _________________________________________________________ 25

1.3.1. Suma binaria ____________________________________________________________ 26

1.3.2. Resta binaria ____________________________________________________________ 27

Evidencia de aprendizaje. Sistema numérico de mi fecha de nacimiento _____________________ 29

Consideraciones específicas de la unidad _____________________________________________ 29

Fuentes de consulta ______________________________________________________________ 29



UNIDAD 2. GRAFOS Y ÁRBOLES ____________________________________________________ 30




2.1. Grafos _____________________________________________________________________ 31

2.1.1. Clasificación de un grafo ___________________________________________________ 32

Actividad 1. Áreas dónde se aplica la teoría de grafos _________________________________ 35

2.1.2. Representación de grafos __________________________________________________ 35

Actividad 2. Solución de problemas mediante la representación de grafos __________________ 40

Actividad 3. Matriz de adyacencia _________________________________________________ 41

2.2. Caminos y circuitos ___________________________________________________________ 41

2.2.1. Terminología básica _______________________________________________________ 41

2.2.2. Camino de Euler __________________________________________________________ 43

2.2.3. Circuitos de Euler _________________________________________________________ 44

2.2.4. Circuito de Hamilton _______________________________________________________ 45

Actividad 4. Pozos _____________________________________________________________ 46

2.2.5. Isomorfismo _____________________________________________________________ 47

2.4. Árboles ____________________________________________________________________ 49

2.3.1. Tipos de árboles __________________________________________________________ 51

Actividad 5. Árbol genealógico ____________________________________________________ 54

Evidencia de aprendizaje. Grafo de rutina cotidiana ___________________________________ 55



UNIDAD 3. RELACIONES ___________________________________________________________ 55




3.1. Introducción a la relación ______________________________________________________ 57

3.1.1. Definición de relación ______________________________________________________ 58

Actividad 1. Definición de relación _________________________________________________ 60

3.1.2. Relación binaria __________________________________________________________ 60

3.1.3. Matriz de una relación _____________________________________________________ 62

3.1.4. Grafo de una relación ______________________________________________________ 63

Actividad 2. Relaciones _________________________________________________________ 63

3.2. Propiedades de las relaciones __________________________________________________ 64

3.2.1. Reflexiva ________________________________________________________________ 64

3.2.2. Irreflexiva _______________________________________________________________ 65

3.2.3. Simétrica _______________________________________________________________ 65

3.2.4. Asimétrica _______________________________________________________________ 66

3.2.5. Antisimétrica _____________________________________________________________ 66

3.2.6. Transitiva _______________________________________________________________ 67

Actividad 3. Propiedades de las relaciones __________________________________________ 68

3.3. Operaciones con relaciones ____________________________________________________ 69

3.3.1. Operaciones con relaciones _________________________________________________ 69

Actividad 4. Operaciones con relaciones ____________________________________________ 71



3.4. Relaciones de equivalencia ____________________________________________________ 73

3.4.1. Relación de equivalencia ___________________________________________________ 73

3.4.2. Cerraduras ______________________________________________________________ 74

Actividad 5. Elementos de la relación ______________________________________________ 76

Evidencia de aprendizaje. Relación de números de lotería ________________________________ 76





I. Información general de la asignatura

a. Ficha de identificación

Área Ciencias Exactas, Ingenierías y Tecnología

Nombre del curso o asignatura Matemáticas discretas

Clave de asignatura 050910312

Seriación Sin seriación

Cuatrimestre Tercero

Horas contempladas 72

b. Descripción

Tal vez te preguntes por qué se llaman matemáticas discretas. El término discreto tiene muchos

significados que se relaciona con el contexto en el que se utiliza, por ejemplo, cuando decimos que una

persona es discreta, es porque se encuentra alejada o aislada de las demás personas. En matemáticas, el

término discreto tiene que ver con el manejo de objetos numerables, con valores distintos separables, así

como con la descripción de objetos y problemas reales de modelos abstractos.

Las matemáticas discretas proporcionan gran parte de los fundamentos de computación, como la

utilización de estructuras que pueden contabilizarse, números naturales, gráficas finitas y procesos de

razonamientos, mediante un número finito de pasos.

El enfoque que se utiliza se apega a la formalidad matemática, haciendo énfasis en las aplicaciones de

computación relevantes.

En la unidad uno se introduce a los códigos binarios y sistemas numéricos, así como la conversión entre

sistemas. La importancia de utilizar estos sistemas y códigos está en la aplicación que tiene el software y

el hardware de un sistema de cómputo, sistemas de control automáticos y comunicaciones.

La unidad dos aborda los grafos y árboles que se refieren a estructuras de datos que permiten organizar y

mantener información que usualmente es para los sistemas de cómputo; sin embargo, se extiende para

representar procesos de distintos campos como la química o la psicología.

En la unidad tres, se utilizan algunas estructuras básicas para representar relaciones entre elementos de

conjuntos. Dichas relaciones tienen una importancia fundamental tanto en la teoría como en las

aplicaciones de la informática, pues, son parte de un modelo matemático que están a menudo

implícitamente representadas por relaciones en una estructura de datos.

En general con esta asignatura tendrás la capacidad de analizar y representar situaciones reales y

problemas diversos mediante modelos, así como métodos analíticos y numéricos.

Esta asignatura se imparte en el tercer cuatrimestre de las carreras de Telemática, Desarrollo de software

y Matemáticas y contribuye con elementos para las materias de Lógica, Probabilidad I y II, Estadística,

Álgebra I y II, Análisis numérico, Álgebra lineal y Habilidades del pensamiento.



Además de los conocimientos teórico-prácticos que se adquieren con este curso, se fortalecen habilidades

del pensamiento matemático tales como el pensamiento abstracto y el razonamiento inductivo y deductivo.

c. Propósitos

Al concluir el curso el alumno:

Representará e interpretará datos que impliquen el uso de

sistemas tecnológicos.

Representará situaciones de índole tecnológica y social usando

grafos y árboles.

Relacionará componentes de distintos conjuntos.

II. Fundamentación de la asignatura

Uno de los antecedentes que permitió la estructura de la asignatura es el progreso de la informática y de

las técnicas computacionales que dio impulso y la convirtió en una de las ramas de la matemática aplicada

de gran importancia. Siendo ahora una base para el desarrollo tecnológico actual, ya que es posible

representar y analizar información con un sentido estructural.

El enfoque de la asignatura será teórico práctico, ya que es necesario poner en práctica los conceptos

teóricos para su comprobación.

III. Competencia(s) a desarrollar

General:

Desarrollar representaciones gráficas y de códigos para describir

estructuras de datos y su relación a través de la aplicación de reglas

con base en procedimientos de matemáticas abstractas.



Específicas:

Resolver operaciones aritméticas para identificar la equivalencia entre diferentes códigos numéricos

mediante la aplicación de métodos establecidos con fundamento en las reglas de conversión.

Analizar modelos de grafos para esquematizar conjuntos de datos relacionando estructuras

basadas en teoría de grafos y árboles.

Analizar estructuras básicas para identificar las clases y los tipos de relaciones, resolviendo

operaciones entre conjuntos e interpretando sus propiedades.

IV. Temario

1. Sistemas numéricos

1.1. Sistemas numéricos

1.1.1. Características de los sistemas numéricos

1.1.2. Sistema decimal

1.1.3. Sistema binario

1.1.4. Sistema octal

1.1.5. Sistema hexadecimal

1.2. Conversiones

1.2.1. Conversiones decimal-binario

1.2.2. Conversiones binario-octal-hexadecimal

1.2.3. Conversiones entre distintas bases

1.3. Operaciones binarias

1.3.1. Suma binaria

1.3.2. Resta binaria

2. Grafos y árboles

2.1. Grafos

2.1.1. Clasificación de un grafo

2.1.2. Representación de grafos

2.2. Caminos y circuitos

2.2.1. Terminología básica

2.2.2. Camino de Euler

2.2.3. Circuitos de Euler

2.2.4. Circuito de Hamilton

2.2.5. Isomorfismo

2.3. Árboles

2.4.1. Tipos de árboles

3. Relaciones

3.1. Introducción a la relación

3.1.1. Definición de relación

3.1.2. Relación binaria

3.1.3. Matriz de una relación



3.1.4. Grafo de una relación

3.2. Propiedades de las relaciones

3.2.1. Reflexiva

3.2.2. Irreflexiva

3.2.3. Simétrica

3.2.4. Asimétrica

3.2.5. Antisimétrica

3.2.6. Transitiva

3.3. Operaciones con relaciones

3.3.1. Operaciones con relaciones

3.4. Relaciones de equivalencia

3.4.1. Relación de equivalencia

3.4.2. Cerradura

V. Metodología de trabajo

Debes tener, además de tu computadora, papel y lápiz a la mano para poder realizar anotaciones y seguir

los ejemplos expuestos, así como anotar el desarrollo del procedimiento de cada ejercicio que se te

indique realizar. Es importante que te encuentres en un espacio donde te sientas cómodo y no haya

distractores. Este tipo de matemáticas requiere un grado de concentración importante para poder

comprender los procedimientos y las reglas que lo rigen, ya que el razonamiento es la característica más

importante para el buen entendimiento. Recuerda que el (la) Facilitador(a) es un(a) maestro(a) de consulta

no de dar detalles. Se ha procurado que la información puesta en este curso sea lo más clara posible; sin

embargo, si quieres profundizar en un tema en particular, consulta la bibliografía y las herramientas

tecnológicas, como los foros y wikis. La función del estudiante es cumplir con las tareas y exámenes en

tiempo y forma mostrando dedicación, responsabilidad y empeño, ya que este tipo de asignaturas

requieren de una atención extra para poder tener un desarrollo satisfactorio.

VI. Evaluación

En el marco del Programa de la ESAD, la evaluación se conceptualiza como un proceso participativo,

sistemático y ordenado que inicia desde el momento en que el estudiante ingresa al aula virtual, por lo que

se le considera desde un enfoque integral y continuo.

Por lo anterior, para aprobar la asignatura de Matemáticas discretas, se espera la participación

responsable y activa del estudiante así como una comunicación estrecha con su facilitador para que pueda

evaluar objetivamente su desempeño. Para lo cual es necesaria la recolección de evidencias que permitan

apreciar el proceso de aprendizaje de contenidos: declarativos, procedimentales y actitudinales.

En este contexto, la evaluación es parte del proceso de aprendizaje en el que la retroalimentación

permanente es fundamental para promover el aprendizaje significativo y reconocer el esfuerzo. Es requisito

indispensable la entrega oportuna de cada una de las tareas, actividades y evidencias, así como la

participación en foros, wikis, blogs y demás actividades programadas en cada una de las unidades, dentro

del tiempo especificado y conforme a las indicaciones dadas. La calificación se asignará de acuerdo con la

escala establecida para cada actividad, por lo que es importante que el estudiante la revise antes de

realizar la actividad correspondiente.



A continuación presentamos el esquema general de evaluación.

ESQUEMA DE EVALUACIÓN

Foros y Bases de datos 10%

Actividades formativas 30%

E-Portafolio 50% Evidencias

Autorreflexiones

40%

10%

Examen final 10%

Calificación final 100%

Cabe señalar que para aprobar la asignatura, se debe obtener la calificación mínima indicada por la ESAD.

VII. Materiales de apoyo

Bibliografía básica

Matousek, J. y Nesetril, J. (2008). Invitación a la matemática discreta. España: Reverte.

Morris Mano, M. (2007). Fundamentos de diseño lógico y de computadoras. España: Pearson.

Hortala González, M. T. (2008). Matemática discreta lógica matemática. España: Complutense.

Bibliografía complementaria

Malva, A. (2005). Matemática discreta: con aplicaciones a las ciencias de la programación y de la

computación. Santa Fe Universidad Nacional del litoral: ULN.

García, C. y Pulgjanerd. (2002). Matemática discreta. Madrid: Pearson.

Kolman. (1995). Estructuras de matemáticas discretas para la computación. Nueva York: Prentice Hall.

Rosen, K. (2004). Matemática discreta y sus aplicaciones. México: McGraw-Hill.

Biggs, N. L. (1994). Matemática discreta. Vicens Vives.

Kolman, B. y Busby, R. (1986). Estructuras de matemática discreta para la computación. México:

Prentice Hall Hispanoamericana.

Lipschutz, S. (1990). Matemática discreta. Mc-Graw-Hill.

Ross, K.A. Wright, C.R. (1990). Matemáticas discretas. Prentice Hall.

Johnsonbaugh, R. (1988). Matemáticas discretas. Grupo Editorial Iberoamericana.

Martínez, E. (1997). Elementos de matemática discreta. Prentice Hall.



VIII. Desarrollo de contenidos por unidad

UNIDAD 1. SISTEMAS NUMÉRICOS

Propósito de la unidad

El propósito de esta unidad es identificar las características

principales y aplicaciones de los sistemas numéricos actuales

(decimal, binario, octal y hexadecimal), además de realizar

operaciones para conocer la equivalencia entre ellos.

Este hecho es de gran importancia para comprender el

funcionamiento de sistemas tecnológicos tales como la computadora.

Competencia específica

Resolver operaciones aritméticas para identificar la equivalencia entre

diferentes códigos numéricos mediante la aplicación de métodos

establecidos con fundamento en las reglas de conversión.

Presentación de la unidad

Actualmente, existen varios sistemas numéricos que se han diseñado para diversos fines y bajo distintas

circunstancias. Por mencionar un ejemplo del uso de éstos, se puede decir que gran parte de los sistemas

tecnológicos y digitales manejan sistema binario y aquellos que aún no lo manejan tienden a hacerlo en el

corto plazo; de ahí la importancia de comprender e interpretar estos sistemas numéricos.



Una de las principales ventajas de estos sistemas es que pueden

manejar volúmenes grandes de información, ya sea para

almacenarla o para procesarla.

Los sistemas tecnológicos no solo ocupan sistema binario para

representar su funcionamiento, sino que utilizan también otros

sistemas (octal y hexadecimal) para poder representar grandes

volúmenes de información de forma abreviada.

1.1. Sistemas numéricos

Desde hace cientos de años, los sistemas numéricos forman parte del desarrollo de la humanidad, su

principal aplicación es la de representar cantidades, es así que se tienen el sistema numérico decimal,

maya, romano, etc.

Con la aparición de la tecnología informática fue necesario desarrollar nuevas representaciones de las

cantidades, tal es el caso de los sistemas de numeración binario, octal y hexadecimal.

En esta unidad analizaremos las características de los sistemas numéricos actuales y aplicaremos

operaciones para obtener su equivalencia entre cada uno de ellos.

1.1.1. Características de los sistemas numéricos

Un sistema numérico se define como el conjunto ordenado de símbolos o dígitos y reglas con que se

combinan para representar cantidades numéricas.

A pesar de que existe un número considerable de sistemas numéricos, los más utilizados son decimal,

binario, octal y hexadecimal. Su principal característica es que estos sistemas numéricos utilizan una base.

La base de un sistema numérico es el número de dígitos diferentes usados en ese sistema.

A continuación se ejemplifica esta definición con los sistemas numéricos más comúnmente utilizados.

Base Sistemas Dígitos

2 Binario 0,1

8 Octal 0,1,2,3,4,5,6,7

10 Decimal 0,1,2,3,4,5,6,7,8,9

16 Hexadecimal 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

A lo largo de este curso para distinguir entre los diferentes sistemas numéricos encerraremos entre

paréntesis el número y añadiremos un subíndice indicando su base. Sin embargo, si no se usa subíndice

se entenderá que el número está en base diez.



Ejemplo

A continuación se analizará con detalle los sistemas numéricos decimal, binario, octal y hexadecimal.

1.1.2. Sistema decimal

El sistema numérico que usamos todos los días en la escuela y en nuestra vida cotidiana se conoce como

sistema numérico decimal, en éste un número es representado por una cadena de dígitos y cada

posición tiene un peso asociado.

El valor del número es la suma ponderada de todos los dígitos, por ejemplo:

(2345)10 = 2*1000 + 3*100 + 4*10 + 5*1

El peso de cada potencia de 10 corresponde a la posición del dígito. Observa la siguiente tabla:

El sistema numérico decimal es expresado con una base 10, lo que significa que las cantidades son

representadas utilizando 10 dígitos (0, 1, 2, 3, 4, 5, 6, 7, 8, 9).

1.1.3. Sistema binario

La información que manejan los circuitos que contienen los sistemas de cómputo tiene señales que están

en una de dos condiciones: alto o bajo, activado o desactivado, etc. Las señales en estos circuitos

representan dígitos binarios llamados bits. Un bit es un dígito binario (abreviación del inglés binary digit),

es decir, un 0 o un 1.

Este sistema numérico utiliza la base 2, es decir, solo utiliza dos dígitos (0 y 1) para representar

cantidades; la agrupación de varios bits se conoce como byte.



Ejemplo

Byte (1101)2

El bit ubicado más a la izquierda de un número binario se llama bit de orden superior o bit más significativo

(MSB, siglas en inglés de most significant bit); y el bit más a la derecha es el bit de orden inferior o bit

menos significativo (LSB, siglas en inglés de least significant bit).

En conclusión, podemos decir que cada uno de los bits que forman un byte tiene un peso específico de

acuerdo a su posición.

1.1.4. Sistema octal

Los sistemas numéricos que utilizan la base 10 son de suma importancia, ya que se usan en la vida

cotidiana, y los de base 2 son los que pueden procesarse directamente mediante circuitos electrónicos

digitales. Aunque los números en otras bases no se procesan directamente, a menudo se utilizan para

representaciones breves que son convenientes para números con múltiples bits en un sistema digital, tal

es el caso del sistema numérico octal.

Este sistema utiliza como base el 8. El sistema octal necesita 8 dígitos (0, 1, 2, 3, 4, 5, 6, 7) para poder

representar cantidades.



Ejemplo

Múltiples bits representación breve en octal

(100011001110)2 = (4316)8

1.1.5. Sistema hexadecimal

Al igual que el sistema numérico octal, el sistema numérico hexadecimal es utilizado ampliamente como

código para representar números de múltiples bits en códigos abreviados. Este sistema tiene como base el

16, lo que significa que utiliza 16 dígitos (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F) para representar

cantidades.

Ejemplo

Múltiples bits representación breve en hexadecimal

(1010001011101000)2 = (A2E8)16

Actividad 1. Aplicación de las representaciones numéricas

Esta es la primera actividad de nuestro curso, es por eso que antes de realizar el trabajo propiamente

relacionado con el tema que acabamos de estudiar, haremos un pequeño paréntesis para dedicar un

momento a presentarnos con el grupo.

Entonces, lo primero que tienes que hacer, es ingresar al foro que lleva el mismo nombre que esta

actividad, una vez ahí, da clic sobre la entrada Presentación y dentro de ésta, agrega tu presentación en

un nuevo comentario. Considera lo siguiente:

Indica tu lugar de residencia, tus expectativas de la asignatura, que conocimientos previos tienes de

ésta, entre otros puntos que quieras compartir.

Cuando ya hayas realizado tu presentación regresa a la pantalla principal del foro y esta vez accede a la

entrada Aplicaciones de las representaciones numéricas. Posteriormente responde las siguientes

preguntas:



¿De lo que te rodea dónde puedes utilizar las representaciones numéricas?

¿Dónde has observado estos tipos de numeración?

¿Crees que estos códigos además de representar números puedan representar objetos o colores?

Consulta la Rúbrica general de participación en foros, que se encuentra en la sección Material de apoyo.

1.2. Conversiones

Para diferentes aplicaciones tecnológicas de electrónica

y computación es importante utilizar equivalencias entre

cada uno de los sistemas numéricos aplicando

conversiones; sin embargo, la conversión entre dos

bases no puede hacerse por simple sustitución, se

requiere de operaciones aritméticas.

1.2.1. Conversiones decimal-binario

Una de las conversiones más utilizadas es de decimal a binario y viceversa. Antes de realizar las

conversiones es importante mencionar que existen diferentes técnicas para conocer su equivalencia; sin

embargo, utilizaremos una técnica sencilla llamada equivalencia de acuerdo a su posición. Esta técnica

implica la suma ponderada de cada una de sus posiciones.

Las siguientes tablas contienen una serie de conversiones para los diferentes sistemas numéricos; por el

momento observa sólo la primera, que es la referente a la conversión de decimal a binario, en ella

observarás el valor en decimal que corresponde a cada posición del sistema numérico binario.



Tablas de conversión de sistemas numéricos

Tabla de conversiones de Sistema numérico decimal a binario.

Tabla de conversiones de Sistema numérico binario a octal.

Tabla de conversiones de Sistema numérico binario a hexadecimal.

Recordemos que en el sistema numérico binario se utilizan 2 dígitos (0 y 1). El 1 es utilizado para dar el

valor numérico, y el 0 para llenar la posición de la cual no necesitamos el valor.



Ejemplo 1

De acuerdo con la tabla revisada anteriormente, el valor equivalente en decimal según su posición es:

De tal forma que: (1001)2 = (9)10

Ejemplo 2

Tomando en cuenta la posición de los dígitos 1 tenemos:

La suma de las posiciones es: (190)10

Por lo tanto: (10111110)2 = (190)10

Hasta el momento hemos realizado operaciones para conocer la equivalencia de sistema numérico binario

a sistema numérico decimal. Para realizar conversiones de sistema numérico decimal a binario se utiliza

un método semejante.



Ejemplo

Tenemos el número en decimal (48)10 y necesitamos su equivalente binario utilizando la tabla de

conversiones de sistema decimal a binario. Comenzamos con la posición 6ª, que equivale al número 32 en

decimal, ya que la posición 7ª es 64 en decimal y excede el número (48)10 del cual necesitamos conocer su

equivalencia. A partir de la posición 6ª comenzaremos nuestra suma de posiciones procurando que esa

suma se ajuste al número que necesitamos conocer, recordemos que el dígito 1 en binario es el que le da

el valor a la posición y el dígito 0 es solo para llenar espacio.

Actividad 2. Conversión de decimal a binario

Ha llegado la hora de llevar a la práctica lo que acabas de aprender, para hacerlo, deberás realizar lo

siguiente:

1. En un archivo de Word, convierte los siguientes ejercicios de numeración decimal a numeración binaria.

• (135)10

• (77)10

• (83)10

• (200)10

• (15)10

2. Guarda tu documento con el nombre MDI_U1_A2_XXYZ.

3. Envía el archivo a tu Facilitador(a) y espera su retroalimentación.

1.2.2. Conversiones binario-octal-hexadecimal

Una parte importante de las conversiones es que podemos tener representaciones breves utilizando

diferentes sistemas de numeración, tal es el caso de los sistemas de numeración octal y hexadecimal, esto

se debe a que utilizan diferentes dígitos. Comencemos con la conversión de binario a octal. Recuerda

que el sistema de numeración octal utiliza 8 dígitos (0, 1, 2, 3, 4, 5, 6, 7).



Haciendo uso de la siguiente tabla, observemos la equivalencia de binario a octal.

Ejemplo:

Supón que tenemos el número en binario (10111001)2 y necesitamos su equivalente en sistema numérico

octal.

El primer paso es realizar agrupaciones de tres bits partiendo de derecha a izquierda como se muestra a

continuación:

(10 111 001)2

Utilizando la tabla, de forma directa convertimos su equivalente de binario en octal como si fueran grupos

independientes.

En resumen tenemos:

(10111001)2 = (271)8

Ahora realizaremos la conversión de binario a hexadecimal. Recuerda que el sistema numérico

hexadecimal utiliza 16 dígitos (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F).

Haciendo uso de la siguiente tabla, observemos la equivalencia de binario a hexadecimal.



Ejemplo:

Supón que tenemos el número en binario (111010111001)2 y necesitamos su equivalente en sistema

numérico hexadecimal.

El primer paso es hacer agrupaciones de cuatro bits partiendo de derecha a izquierda como se muestra a

continuación:

(1110 1011 1001)2

Utilizamos la tabla de conversiones correspondiente y de forma directa convertimos su equivalente de

binario en hexadecimal como si fueran grupos independientes.

En resumen tenemos: (111010111001)2 = (EB9)16



Actividad 3. Conversiones binario- octal-hexadecimal

Para practicar lo aprendido sobre las conversiones de binario a octal y decimal, realiza lo que se te pide a

continuación:

1. Convierte los siguientes ejercicios de numeración binaria a octal o hexadecimal.

• (110101)2 a octal

• (11001111)2 a hexadecimal

• (111111)2 a octal

• (11101110)2 a hexadecimal

2. Guarda tus ejercicios en un documento de Word con el nombre MDI_U1_A3_XXYZ y envíalo a tu

Facilitador(a).

1.2.3. Conversiones entre distintas bases

Ya hemos realizado operaciones para conocer las equivalencias de decimal a binario y viceversa, de

binario a octal y de binario a hexadecimal, pero ¿qué pasaría si quisiéramos realizar una conversión de

decimal a hexadecimal o a octal? A continuación realizaremos los procesos para llevar a cabo dichas

conversiones.

Conversión de decimal a octal

Ejemplo:

Supón que necesitamos conocer la equivalencia de (105)10 en sistema numérico octal.

El primer paso tendría que ser la conversión del sistema numérico decimal al sistema numérico binario

como se muestra a continuación:

Recuerda que este proceso ya lo analizamos en el tema 1.2.1; una vez que tenemos el código en binario lo

que resta es convertir el sistema binario en sistema octal usando la tabla correspondiente:

Como se muestra:



(1101001)2 = (151)8

Por lo tanto, en conclusión podemos decir que:

(105)10 = (151)8

Conversión de decimal a hexadecimal

El proceso para conocer el equivalente de decimal en hexadecimal es muy parecido al que se realiza para

la conversión de decimal a octal.

Ejemplo:

Supón que necesitamos conocer el número (170)10 en sistema numérico hexadecimal.

El primer paso será convertir el número decimal en número binario.

Una vez que tenemos el número en binario lo convertimos en hexadecimal usando la tabla siguiente:



De tal forma que:

Por lo tanto, en conclusión podemos decir que:



Actividad 4. Conversiones entre distintas bases

Ahora toca el turno a las conversiones entre distintas bases, realiza lo que se pide enseguida:

1. Convierte los siguientes ejercicios en el código que se te indica.

(4F)16 a binario

(101111)2 a octal

(36)8 a decimal

(69)10 a binario

2. Guarda tu documento en Word con el nombre MDI_U1_A4_XXYZ.

3. Envía los resultados a tu Facilitador(a).

1.3. Operaciones binarias

La suma y la resta de números binarios usan la misma técnica aprendida en la escuela para los números

decimales. Es importante mencionar que este tipo de operaciones se realiza con frecuencia en los

sistemas digitales tales como computadoras y sistemas de comunicación, entre otros, por lo que cobra una

mayor importancia utilizar operaciones binarias.

En la numeración decimal para representar números negativos solo hay que multiplicar por (-1) el número

positivo; sin embargo, en el sistema binario existe una representación especial para las cantidades

negativas.

En la siguiente imagen se expresan los números decimales tanto positivos como negativos y su

correspondiente en binario.



1.3.1. Suma binaria

La suma se realiza bit a bit entre columnas de derecha a izquierda, verificando si existe un acarreo.

El acarreo es un bit extra que se genera a partir de la suma de 1 + 1, este bit de acarreo se asigna a la

columna izquierda próxima.

En la tabla siguiente se muestra bajo qué condiciones se presenta un acarreo.



A continuación se presenta un ejemplo de la suma de dos números binarios:

En la primera columna de la derecha, el número 1+1=0 con acarreo 1. Ese bit de acarreo se pasa a la

siguiente columna de la izquierda para sumarlo, por lo tanto queda 1+0=1 y 1+1=0 con acarreo 1. Este bit

de acarreo pasa a la siguiente columna de la izquierda, pero en esta ocasión no tiene que sumarse con

ningún bit por lo tanto pasa hasta el resultado.

Una forma de comprobar la suma es convirtiendo los sumandos y el resultado a decimal y comprobar si

coinciden.

Ejemplo:

Otro ejemplo sería:

Realiza la siguiente operación:

Verifica el resultado convirtiendo el número binario en decimal.

1.3.2. Resta binaria

La resta de números binarios puede realizarse como si fuesen números binarios ordinarios sin signo, y

pueden formularse reglas apropiadas para detectar el desborde. El desborde es un bit final que determina

el signo del resultado. Sin embargo, la mayoría de los circuitos para resta de números binarios no realiza la

resta de forma directa; más bien niega el sustraendo y luego lo suma al minuendo con las reglas normales

de la suma.



Negar el sustraendo y sumar el minuendo puede realizarse con una sola operación de suma como sigue:

convierte a binario el sustraendo, luego súmalo al minuendo con un acarreo inicial de 1 en vez de 0.

En seguida se proporcionan algunos ejemplos:

Ejemplo 1:

En este ejemplo es importante mencionar que, para negar el sustraendo (0011)2 equivalente al +3,

simplemente se cambia el cero (0) por uno (1) y viceversa por lo tanto queda como (1100)2

Finalmente se realiza la suma bit a bit obteniendo el resultado.

Ejemplo 2:

En este ejemplo observamos la resta de dos números negativos. Utilizando la Representación de conteo

modular de números de 4 bits, que te mostramos en el Tema 1.3 “Operaciones binarias”, podemos conocer

qué combinación binaria corresponde a cada número negativo, por ejemplo -3 = (1101)2 y -8 = (1000)2.

Ahora el siguiente paso es aplicar las reglas: negar el sustraendo, es decir, en (1000)2 cambiamos ceros

por unos y viceversa quedando como resultado (0111)2; a continuación se realiza la suma bit a bit y

obtenemos el resultado.



Evidencia de aprendizaje. Sistema numérico de mi fecha de nacimiento

Como sabes, la entrega de tus Evidencias de aprendizaje es muy importante para tu evaluación final del

curso. La evidencia consta de dos partes: de las entregas que hagas de los trabajos solicitados y de las

autorreflexiones por unidad, de modo que para cada una de las unidades de la asignatura deberás cumplir

con ambas cosas.

Para comenzar con la primera parte:

1. Realiza la conversión de la fecha de nacimiento de cinco miembros de tu familia como sigue:

• El día convertirlo a sistema hexadecimal

• El mes convertirlo a sistema octal

• El año convertirlo a sistema binario

2. Averigua cuál es la fecha que se obtiene de convertir los siguientes códigos en sistema decimal.

• (1111)2 / (0B)16 / (1563)8

• (1001)2 / (09)16 / (1753)8

• (1100)2 / (0A)16 / (1436)8

3. Consulta la Escala de evaluación para conocer los criterios que debe cumplir tu actividad.

4. Cuando hayas terminado tu evidencia, guarda tu documento con el nombre MDI_U1_EA_XXYZ y

envíalo a tu Facilitador(a) para que te retroalimente. Posteriormente revisa los comentarios y atiéndelos

para mejorar tu trabajo y volverlo a enviar.

Para la segunda fase de la Evidencia de esta unidad, es importante que ingreses al foro Preguntas de

Autorreflexión y consultes las preguntas que tu Facilitador(a) formule, a partir de ellas, debes elaborar tu

Autorreflexión en un archivo de texto llamado MDI_U1_ATR_XXYZ. Tu archivo lo deberás enviar mediante

la herramienta Autorreflexiones.

Consideraciones específicas de la unidad

En el estudio de esta unidad es necesario que no recurras al uso de una calculadora, ya que el propósito

es que desarrolles la parte de razonamiento.

Fuentes de consulta

Hortala González, M. T. (2008). Matemática discreta y lógica matemática. España: Complutense.

Matousek, J. y Nesetril, J. (2008). Invitación a la matemática discreta. España: Reverte.

Morris Mano, M. (2007). Fundamentos de diseño lógico y de computadoras. España: Pearson.



UNIDAD 2. GRAFOS Y ÁRBOLES


El propósito de esta unidad es presentar una parte de las

matemáticas discretas que tiene que ver con la representación de

situaciones o procesos mediante dibujos o diagramas para

proporcionar información que permita un mayor análisis.


Construir modelos de grafos para esquematizar conjuntos de datos

relacionando estructuras mediante la teoría de grafos y árboles.


En esta unidad se proporciona una introducción formal a grafos y

árboles. Estos temas son de fácil comprensión y sus conceptos se

ilustran fácilmente con dibujos.

Aunque la exposición del tema con frecuencia sea intuitiva, no es

descuidada, a lo largo de esta unidad se va introduciendo la

rigurosidad matemática. Sin embargo, se trató de desarrollar esta

unidad de manera sencilla para adquirir práctica y sensibilidad hacia

el tipo de problemas relacionados con las matemáticas discretas.

En la presente unidad se describirá qué es y para qué es útil un

grafo y un árbol, así como sus características; de la misma manera

se describirá a los caminos y circuitos.



2.1. Grafos

Muchas situaciones de la vida real pueden ser esquematizadas por medio de diagramas construidos por

puntos (vértices o nodos) y líneas (aristas o arcos) que conectan algunos pares de vértices, aunque

eventualmente alguna línea puede unir un vértice consigo mismo.

Estos esquemas, que facilitan la comprensión del problema a resolver, aparecen frecuentemente en

disciplinas dispares y bajo nombres diversos, a saber: redes (en ingeniería, economía), sociogramas (en

psicología), organigramas (en economía y planificación) así como diagramas de flujo (en programación).

A la teoría que se ocupa del estudio de estos diagramas o esquemas se le

conoce como teoría de grafos.

La teoría de grafos desempeña un papel importante en varios campos de las

ciencias, entre ellos ciencias de la conmutación, tales como la teoría de la

conmutación y diseño lógico, inteligencia artificial, lenguajes formales, gráficos

por computadora, sistemas operativos, escritura de compiladores y

organización, así como en la recuperación de información.

Como ya se mencionó, los grafos están formados por vértices que se unen entre sí mediante aristas, tal

como se ilustra en la Figura 2.1. Por tanto, una definición matemática de grafo debe basarse en el conjunto

de vértices y en el conjunto de aristas. Toda arista está asociada con dos vértices, esto es, existe una

correspondencia entre las aristas y los pares de vértices. A continuación se da la definición formal de grafo.

Definición: Un Grafo G =(N, A, f) consta de un conjunto no vacío N

denominado conjunto de vértices del grafo, un conjunto A de

aristas del grafo y una correspondencia f del conjunto de aristas A

en un conjunto de pares ordenados o desordenados de N. Si una

arista se corresponde con un par ordenado, entonces se dice que

es una arista dirigida; en caso contrario, se denomina arista no

dirigida.

La definición de grafo implica que a toda arista del grafo G se le puede asociar una pareja ordenada o

desordenada de vértices del grafo. Si una arista e A está asociada de esta forma con un par ordenado

(u, v) o con un par desordenado {u, v}, en donde u, v N, entonces se dice que la arista e conecta los

vértices u y v. Se supondrá en todo momento que tanto el conjunto A como el conjunto N de un grafo son

finitos. Con frecuencia es conveniente escribir los grafos en una forma abreviada G = (N, A), o bien

simplemente como G. En el primer caso, cada arista se representa directamente como el par con el cual se

corresponde, lo cual obvia la necesidad de especificar f si f es una correspondencia uno a uno.



La definición de un grafo no contiene referencias de las longitudes o formas y posiciones de las aristas que

puedan conectar pares de vértices, y tampoco estipula ningún orden de las posiciones de los vértices. Por

tanto, para un grafo dado no existe un único diagrama que represente al grafo, y puede ocurrir que dos

diagramas que tengan un aspecto completamente diferente entre sí representen un mismo grafo.

En los siguientes temas se dará información precisa de algunos términos usados en la definición previa,

para su mejor comprensión y estudio.

Partes de un grafo

Como se mencionó en la sección anterior, una grafo está compuesto por puntos (también llamado vértices

o nodos) y líneas (también llamado aristas o arcos) que conectan algunos pares de vértices. Una parte

importante de los grafos son las etiquetas, que identifican a las aristas y los vértices.

En lo sucesivo utilizaremos los nombres de Vértices para referirnos a los puntos y Aristas para referirnos a

las líneas.

2.1.1. Clasificación de un grafo

En lo general, existen tres tipos de grafos:

Dirigidos: Si las aristas tienen un sentido concreto, lo cual se indica mediante una cabeza de

flecha, entonces se dice que es un grafo dirigido o dígrafo.

No-dirigidos: En este tipo de grafos las aristas no tienen un sentido.

Mixto: Cuando en un grafo existen aristas dirigidas y aristas no-dirigidas.

Ejemplos:



Una arista de un grafo que conecte un vértice o nodo consigo mismo se denominará bucle o lazo. La

dirección de un bucle no es significativa; por tanto, se puede considerar como una arista dirigida o como

una arista no-dirigida. Existen grafos que tienen más de una arista entre pares de nodos, estas aristas se

denominan arista paralela. En el caso de aristas dirigidas, las aristas entre una pareja de vértices que

tienen sentidos opuestos no se consideran paralelas.

Todo grafo que contenga aristas paralelas se

denominará multígrafo. Para este caso, la

notación abreviada G = (N, A) no basta para

representar los multígrafos, y se necesita la

notación completa G = (N, A, f). Por otra parte, si

no hay más de una arista entre pares de nodos,

entonces el grafo se denomina grafo sencillo.

Antes de continuar, se describen algunas definiciones de teoría de grafos que ayudarán a la comprensión y

estudio de este tema en las secciones posteriores.

Definiciones:

Los pares de vértices que estén conectados por una arista dentro de un grafo se denominan

vértices adyacentes.

En un grafo, un vértice que no sea adyacente a ningún otro vértice se denominará vértice aislado.

Un grafo que contenga solamente nodos aislados se denominará grafo nulo. Entonces, el conjunto

de aristas, A, de un grafo nulo está vacío.

Los grafos en los que cada arista tiene asignado un peso se denominan grafos ponderados.

Un grafo no dirigido es conexo si para cualquier pareja de vértices del grafo se puede llegar hasta el

otro vértice partiendo de cualquiera de ellos.

Definición: En un grafo dirigido, para todo vértice v el número de aristas que tienen a v como vértice inicial

se denomina grado de entrada del vértice v. El número de aristas que tienen a v como vértice terminal se

denomina grado de salida, y la suma de ambos es lo que se denomina grado total del vértice v. De manera

general, el grado total de un vértice v, δ (v), es el número de aristas dirigidas o no-dirigidas incidentes en v.

El grado total de un vértice aislado es 0, y el de un vértice con bucle y sin otras aristas que incidan en él es

2.



Definición: Sea N(H) el conjunto de vértices de

un grafo H, y sea N(G) el conjunto de vértices

de un grafo G tales que N(H) N(G). Si

además toda arista de H es también una arista

de G, entonces se dice que el grafo H es un

Subgrafo del grafo G, y esto se expresa en la

forma H G.

En la figura Grafo y algunos de sus subgrafos,

los grafos de la parte (b) son subgrafos de la

parte (a).

También, se dice que un grafo G = (N, A) es completo si todos sus vértices son adyacentes a todos los

vértices del grafo, es decir, existe una arista ente cada par de vértices distintos. Los grafos completos de n

vértices se denotan en la forma Kn.

La figura Grafos completos del 1 al 5 muestra los cinco primeros grafos completos.

Un tipo de grafo sencillo es el bipartito. Un grafo G = (N, A) se denomina grafo bipartito si el conjunto de

vértices N se puede separar en dos subconjuntos V1 y V2 de modo que cada arista en A sea incidente en

un vértice de V1 y en un vértice de V2. Dicho de otro modo, que no haya dos vértices de V1 que sean

adyacentes, ni tampoco dos vértices de V2 que sean adyacentes.

El grafo ilustrado en la figura Grafo (a) es un grafo bipartito, ya que los dos subconjuntos disjuntos de

vértices son V1 = {v1, v2} y V2 = {v3, v4, v5}, cada arista es incidente en un vértice de V1 y un vértice de V2.

Por el contrario, la figura (b) no es un grafo bipartito, puesto que no es posible descomponer el conjunto N

en dos subconjuntos disjuntos no vacíos.



Actividad 1. Áreas donde se aplica la teoría de grafos

Con el propósito de proporcionar ejemplos de campos donde es posible aplicar la teoría de grafos para

representar situaciones y dar solución, ya sea en el ámbito científico o social, debes participar en el foro:

Áreas donde se aplica la teoría de grafos. En vista de lo anterior, realiza lo que se te indica.

1. Ingresa al foro y contesta las siguientes preguntas:

¿En qué áreas del ámbito científico se pueden aplicar los grafos?

¿Será posible hacer grafos del funcionamiento del cuerpo humano?

¿Será posible hacer grafos de tu rutina diaria?

2. Recuerda retroalimentar la participación de mínimo dos de tus compañeros(as).

Puedes consultar la Rúbrica de participación general del foro, que se encuentra en la sección Material de

apoyo.

2.1.2. Representación de grafos

Hasta ahora se ha representado a los grafos mediante diagramas o esquemas; sin embargo, en muchos

casos, como por ejemplo al utilizar una computadora para analizar un grafo, es necesaria una

representación más formal. La representación más formal de un grafo es mediante su matriz de

adyacencia, o mediante su matriz de incidencia.

Matriz de adyacencia

Para obtener la matriz de adyacencia, considerando el grafo de la figura mostrada. Primero se debe elegir

un orden para los vértices, por ejemplo: a, b, c, d, e. Posteriormente, construir una matriz y etiquetar los

renglones y las columnas con los vértices ordenados. La entrada en esta matriz es un 1 si los vértices del

renglón y la columna son adyacentes y 0 en caso contrario.



Figura a) Representación de un grafo.

La matriz de adyacencia del grafo de la figura anterior es la que a continuación se presenta:

Observa que se puede obtener el grado de un vértice v en un grafo sencillo sumando el renglón v o

columna v en la matriz de adyacencia. Ejemplo: el grado total del vértice b es 3.

Además, aunque la matriz de adyacencia permite representar bucles, no permite representar aristas

paralelas; sin embargo, si modificamos la definición de una matriz de adyacencia para que ésta pueda

contener enteros no negativos arbitrarios, podemos representar las aristas paralelas. En la matriz de

adyacencia modificada, interpretamos la entrada ij-ésima especificando el número de aristas entre i y j.

Considerando el grafo de la figura inferior para obtener la matriz de adyacencia, siguiendo la metodología

del ejemplo anterior, la matriz de adyacencia es la que se muestra como A.

Figura b) Representación de un grafo.



Utilizando el ejemplo previo, se mostrará que si A es la matriz de adyacencia de un grafo sencillo G, las

potencias de A, A, A2, A3,…, cuentan el número de caminos de diversas longitudes. Más precisamente, si

los vértices de G se etiquetan 1, 2,…, la entrada ij-ésima en la matriz An es igual al número de caminos de

i a j de longitud n. Por ejemplo, supón que se obtiene el cuadrado de la matriz A del ejemplo de la figura

b).

Al considerar la entrada del renglón a, columna c en A2, obtenida al multiplicar por pares las entradas del

renglón a por las entradas de la columna c de la matriz A y sumando:

La única forma en que un producto distinto de cero podría aparecer en esta suma es cuando ambas

entradas por multiplicar son iguales. En este ejemplo la suma es 2 pues existen dos caminos de longitud 2

de a a c.

(a, b, c) y (a, d, c)

En general, la entrada en el renglón x y la columna y de la matriz A2 es el número de caminos de longitud

2 del vértice x al vértice y.

Las entradas de la diagonal de A2 proporcionan los grados de los vértices (cuando el grafo es sencillo).

Considerando el vértice c en el ejemplo de la figura b) el grado de c es 3 pues c es incidente en las tres

aristas (c, b), (c, d), (c, e). Pero cada una de estas aristas se puede convertir en un camino de longitud 2

de c a c.

(c, b, c), (c, d, c) y (c, e, c)



Teorema: Si A es la matriz de adyacencia de un grafo sencillo, la entrada ij-ésima de An es igual al

número de caminos de longitud n del vértice i al vértice j, n = 1, 2,…

Matriz de incidencia

Otra manera de representar un grafo es mediante la matriz de incidencia. Para obtener la matriz de

incidencia, considera el grafo de la siguiente figura. Primero se debe construir una matriz y etiquetar los

renglones con los vértices y las columnas con las aristas en algún orden arbitrario. La entrada del renglón v

y la columna e es 1 si e es incidente en v y 0 en caso contrario.

Figura c) Representación de un grafo.

La matriz de incidencia del grafo de la figura es la que a continuación se da:

La matriz de incidencia permite representar las aristas paralelas y los bucles. La columna como e7

representa un bucle. Obsérvese que en un grafo sin bucles, cada columna tiene dos 1s y que la suma de

los elementos de un renglón proporciona el grado del vértice identificado con ese renglón. Las aristas

paralelas en este ejemplo son e1 y e2.



Ejemplos complementarios de la sección

Problema: elabora un grafo que represente un mapa de carreteras y ciudades, considera 5 ciudades (A, B,

C, D, E), con las siguientes características: 1) hay dos rutas que unen las ciudades A y B, 2) no existe una

ruta entre A y D, 3) existe un camino que pasa por B, C y D, 4) la ciudad E está aislada.

Solución: una posible solución al ejercicio, es la que se muestra en la figura siguiente. Se usa un grafo no

dirigido puesto que el problema no plantea alguna dirección para alguna carretera. Las aristas representan

a las carreteras y los vértices representan a las ciudades. Para cumplir con el requisito 1), se usan aristas

paralelas.

Figura 2.11. Grafo representando un mapa de carreteras y ciudades.

Problema: la figura 2.12 (a) muestra una parte del plano de una ciudad, en el cual las flechas denotan

calles de dirección única. Elabora un grafo que represente esta parte del plano. Este grafo puede ser útil

para los servicios de emergencia públicos, como los bomberos y la policía.

Solución: según el plano, existen calles con dirección única y otras que no, por lo tanto, el tipo de grafo

requerido es mixto. Para este caso, las aristas representarán a las calles y los vértices representarán las

esquinas o intersecciones entre calles. El grafo obtenido es el que se muestra en la figura 2.12 (b).



Figura 2.12. Representación gráfica del sistema de calles de una ciudad.

Actividad 2. Solución de problemas mediante la representación de grafos

Esta actividad tiene como fin que construyas un grafo mediante el siguiente planteamiento: Karla, Manuel,

Juan, Mónica, Eliangel e Iliana, van a subir a un juego mecánico en forma circular, se sabe que:

Karla conoce a Juan y a Mónica

Manuel conoce a Juan y a Eliangel

Iliana conoce a Eliangel y a Mónica

¿Es posible sentarlos de forma que las personas que estén sentadas juntas se conozcan?

1. Construye un grafo donde se represente la solución del planteamiento.

2. Menciona el número de vértices del grafo que construiste.

3. Guarda tu documento en un archivo .doc con el nombre MDI_U2_A2_XXYZ y envíalo a tu Facilitador(a)

a través de la sección de Tareas.



Actividad 3. Matriz de adyacencia

Con el fin de reforzar tus conocimientos sobre la representación de un grafo con una matriz de adyacencia,

realiza lo que se te pide:

1. Representa el siguiente grafo utilizando una matriz de adyacencia:

2. Guarda tu documento con el nombre MDI_U2_A3_XXYZ y envíalo a tu Facilitador(a) a través de la

sección de Tareas. Espera su retroalimentación y considérala para mejorar tu trabajo.

2.2. Caminos y circuitos

Si se piensan a los vértices de un grafo como ciudades y las aristas como carreteras, un camino

corresponde a un viaje que comienza en cierta ciudad, pasa por varias ciudades y termina en alguna

ciudad. A continuación se dan las definiciones formales de caminos y circuitos.

2.2.1. Terminología básica

Definición: Sea G = (N, A, f) un dígrafo sencillo. Se dice que una sucesión de aristas es un Camino de G

si y sólo si el vértice terminal, vt, de cada arista del camino es el vértice inicial, vi, de la próxima arista del

camino.

Un ejemplo de camino sería: {(vi1, vi2), (vi2, vi3),…, (vik-2, vik-1), (vik-1, vik)}

Se puede escribir de la siguiente forma: {(vi1, vi2,…, vik-1, vik)}

Un camino de un dígrafo con aristas distintas se denomina camino sencillo.

Un camino en el que todos los vértices son diferentes se llama camino elemental.

El número de aristas que aparecen en la sucesión de un camino se denomina longitud del

camino.



Definición: A un camino que comienza y acaba en un mismo vértice se le denomina circuito o ciclo. Un

circuito se denomina sencillo si ninguna arista del circuito aparece más de una vez en el camino y se

denomina elemental si no pasa por ningún vértice más de una vez.

En un circuito el nodo inicial aparece al menos dos veces aun cuando se trate de un circuito elemental.

Algunos circuitos presentes en el grafo de la figura anterior son:

Circuito 1: {1, 2, 3, 8, 1}

Circuito 2: {1, 2, 4, 5, 7, 8, 1}

Circuito 3: {1, 2, 3, 8, 1, 2, 3, 8, 1}

Un grafo sencillo que no tenga ningún ciclo/circuito se denomina acíclico, naturalmente, los grafos

acíclicos no pueden tener bucles.

La definición de camino requiere que las aristas que aparezcan en la sucesión tengan un vértice inicial y

uno terminal bien definidos.

En el caso de un grafo sencillo no-dirigido, una arista está dada por una pareja no ordenada, y cualquiera

de los vértices de esa pareja no ordenada se puede considerar como vértice inicial o final de la arista.

Para aplicar la misma definición de camino a un grafo no-dirigido, se puede considerar que todas las

aristas del grafo no-dirigido se sustituirán por dos aristas dirigidas de sentidos opuestos. Una vez hecho

esto, se tiene un grafo dirigido, y las definiciones de camino, circuito, etc., pueden ser aplicadas.



2.2.2. Camino de Euler

El Camino de Euler está definido como un camino a través del grafo G que recorre todas las aristas del

grafo solamente una vez, pero que su vértice de inicio y final son diferentes.

Para ejemplificar la anterior definición, analizamos el grafo de la

figura del lado derecho, el cual tiene un camino de Euler.

El camino de Euler en dicho grafo es (4, 3, 5, 2, 3, 1, 2, 4, 5).

Observa que los vértices 4 y 5 tienen grado impar.

Las condiciones para la existencia de un camino de Euler están dadas en el siguiente teorema.

Teorema: Si G es un grafo y no tiene vértices aislados, entonces, éste tiene un camino de Euler si y sólo si

las siguientes dos propiedades se cumplen:

1) El grafo G está conectado.

2) El grafo tiene exactamente dos vértices de grado impar.

Para comprobar dicho teorema, veamos el grafo de la figura del lado

izquierdo.

Este grafo está completamente conectado, es decir, no tiene vértices

aislados, y tiene exactamente dos vértices de grado impar, vértice 2 y 6.

Por lo que se puede suponer que el grafo tiene un camino de Euler. El

camino de Euler en dicho grafo es (2, 5, 4, 1, 2, 3, 6, 5, 8, 4, 7, 8, 9, 6).



2.2.3. Circuitos de Euler

El primer artículo en teoría de grafos fue el escrito por

Leonhard Euler en 1736. El artículo presentó una teoría

general que incluía una solución a lo que ahora se llama

el problema de los puentes de Königsberg. El problema

de los puentes de Königsberg consiste en determinar un

circuito a partir de un modelo gráfico representando a los

puentes de Königsberg, que incluya todas las aristas y

todos los vértices del grafo.

Por lo tanto, en honor a Euler, un circuito de un grafo que

incluya todas las aristas y todos los vértices de G se le

denomina Circuito de Euler.

Un circuito de Euler debe cumplir con el siguiente teorema:

Teorema: Si G es un grafo conexo y todo vértice tiene grado par, entonces G tiene un circuito de Euler.

O en su caso, Teorema: Si un grafo G tiene un circuito de Euler, entonces G es conexo y todo vértice tiene

grado par.

Usamos el ejemplo de la figura siguiente para verificar si éste tiene un circuito de Euler. Observando el

grafo se determina que es conexo, y como el grado de cada vértice es par, basados en el teorema previo

decimos que el grafo tiene un circuito de Euler.

Los grados de cada uno de los vértices son:

δ(v1) = δ(v2) = δ(v3) = δ(v5) = 4, δ(v4) = 6, δ(v6) = δ(v7) = 2.

Por inspección se determina que el circuito Euler es el siguiente:

(v6, v4, v7, v5, v1, v3, v4, v1, v2, v5, v4, v2, v3, v6).



2.2.4. Circuito de Hamilton

Sir William Rowan Hamilton lanzó al mercado a mediados del siglo XIX un juego en forma de dodecaedro.

Juego de Hamilton

a)

b)

Cada esquina del dodecaedro llevaba el nombre de una ciudad y el problema era partir de cualquier

ciudad, recorrer las aristas, visitar cada ciudad exactamente una vez, y regresar a la ciudad inicial.

El grafo de las aristas del dodecaedro se muestra en la figura a. Entonces, podemos resolver el juego de

Hamilton si podemos determinar un circuito en el grafo de la figura b que contenga a cada vértice solo una

vez, excepto por el vértice inicial y final que aparece dos veces.

Por lo tanto, en honor de Hamilton, se dice que un circuito en un grafo G que contenga cada vértice solo

una vez, excepto por el vértice inicial y final que aparece dos veces, es un circuito Hamiltoniano.

Una solución al grafo del juego de Hamilton se

ilustra en la figura siguiente:

Solución al juego de Hamilton



El problema de determinar un circuito Hamiltoniano en un grafo parece similar al de determinar un circuito

de Euler. Un circuito de Euler visita cada arista una vez, mientras que un circuito Hamiltoniano visita cada

vértice una vez; sin embargo, en realidad estos problemas son un poco distintos. Además, a diferencia de

los circuitos de Euler, no se conocen condiciones necesarias y suficientes fácilmente verificables para la

existencia de un circuito Hamiltoniano en un grafo.

Los siguientes ejemplos muestran un caso de grafo con circuito Hamiltoniano y otro que no lo tiene. El

grafo de la figura (a) tiene un circuito Hamiltoniano, el circuito (1, 2, 3, 4, 5, 1) es un circuito Hamiltoniano.

El grafo de la figura (b) no tiene un circuito Hamiltoniano; para producir un circuito Hamiltoniano en este

grafo será necesario eliminar dos aristas, una incidente en el vértice v2 y otra incidente en el vértice v4.

Grafo (a) con circuito Hamiltoniano, y (b) sin circuito Hamiltoniano

Actividad 4. Pozos

La siguiente actividad tiene como propósito que representes un grafo mediante el siguiente planteamiento:

Se tienen tres casas y tres pozos.

Con base en lo anterior:

1. Intenta dibujar senderos que unan cada casa con cada pozo de tal manera que no se crucen.

2. Guarda tu documento en un archivo de Word con el nombre MDI_U2_A4_XXYZ.

3. Envía tus resultados a tu Facilitador(a) mediante la sección de Tareas y espera su retroalimentación.



2.2.5. Isomorfismo

Definición: Dos grafos G1 y G2 son isomorfos si existe una función uno a uno y sobre, f, de los vértices de

G1 a los vértices de G2 y una función uno a uno y sobre, g, de las aristas de G1 a las aristas de G2, de

modo que una arista e es incidente en v y w en G1 si y sólo si la arista g(e) es incidente en f(v) y f(w) en G2.

El par de funciones f y g es un isomorfismo de G1 sobre G2.

Dicho de manera menos abstracta, dos grafos son isomorfos si tienen una estructura idéntica, aunque

sean representados gráficamente de manera diferente; o, dos grafos son isomorfos si existe un

renombramiento de los vértices de los grafos tal que ambos sean idénticos.

En la figura de al lado, se muestran dos grafos

isomorfos, ambos tienen una estructura idéntica aunque

gráficamente son representados de manera diferente, y

aunque tengan nombres de vértices diferentes.

Un isomorfismo para los grafos de la figura se define

como: f(a) = A, f(b) = B, f(c) = C, f(d) = D,

f(e) = E, g(xi) = yi, i = 1, …, 5.

Teorema: Dos grafos sencillos G1 y G2 son isomorfos si y sólo si para cierto orden de sus vértices, las

matrices de adyacencia son iguales.

Para ejemplificar dicho teorema, daremos las matrices de adyacencia de los grafos mostrados en la figura

anterior, Grafos isomorfos. La matriz de adyacencia del grafo de la figura (a) con respecto del orden de los

vértices a, b, c, d, e, es el siguiente:

Y se puede observar que es igual a la matriz de adyacencia del grafo de la figura (b) con respecto del

orden de los vértices A, B, C, D, E, que es el siguiente:

Por lo tanto, ambos grafos de la figura son isomorfos.



Para demostrar que dos grafos sencillos G1 y G2 no son isomorfos, se determina una propiedad de G1 que

G2 no tenga, pero que G2 tendría si G1 y G2 fuesen isomorfas. Tal propiedad es un invariante. Más

precisamente, una propiedad P es un invariante, si siempre que G1 y G2 sean grafos isomorfos. Si G1 tiene

la propiedad P, entonces G2 también tiene la propiedad P.

Según la definición previa de isomorfismo, si dos grafos G1 y G2 son isomorfos, entonces existen

funciones uno a uno y sobre de las aristas de G1 en las aristas de G2. Así, si G1 y G2 son isomorfos,

entonces G1 y G2 tienen el mismo número de aristas y el mismo número de vértices. Por tanto, si e y n

son enteros no negativos, las propiedades “tiene e aristas” y “tiene n vértices” son invariantes.

Para ilustrar la propiedad de invariante, se hace uso de los

grafos de la figura de al lado.

Los grafos de la figura no son isomorfos, pues el grafo de la

figura (a) tiene siete aristas y el de la figura (b) tiene seis

aristas, y “tener siete aristas” es un invariante.

Ejemplos complementarios de la sección

Ejemplo: De un conjunto de caminos dados, pertenecientes al grafo ilustrado en la figura siguiente, Grafo

no-dirigido, identificar si es un camino sencillo, o si es un circuito, o un circuito sencillo. Aplicando las

definiciones y teoremas descritos en la sección, los resultados son los que se muestran en la tabla.

Grafo no-dirigido.



Camino ¿Es un camino

sencillo?

¿Es un circuito? ¿Es un circuito

sencillo?

(6, 5, 2, 4, 3, 2, 1) NO NO NO

(6, 5, 2, 4) SI NO NO

(2, 6, 5, 2, 4, 3, 2) NO SI NO

(5, 6, 2, 5) NO SI SI

(7) SI NO NO

2.3. Árboles

Los árboles forman una subclase de grafo de uso amplio. Los árboles se utilizan en muchos otros campos

de aplicación. Por ejemplo, en ciencias de la computación, desglosar problemas complejos y

representarlos mediante una estructura en forma de árbol, son algunas de las aplicaciones.

En general, hay dos grupos de árboles, los árboles libres y los árboles con raíz. Un árbol libre es una clase

especial de grafo no dirigido, y un árbol con raíz es un caso especial de un grafo dirigido.

Definición:

Un Árbol Libre T es un grafo sencillo no dirigido que es a la vez conexo y acíclico, es decir, es un grafo

que no contiene circuitos o ciclos y todos sus pares de vértices están conectados.

Un Árbol con Raíz es un árbol en el cual un vértice particular se designa como la raíz.

Propiedades de un árbol

Teorema: Todo árbol que contenga n vértices debe de tener n-1 aristas.

En la figura de abajo se muestra varios ejemplos

de árboles libres, los cuales cumplen con su

definición y con el teorema previo.

En la figura de abajo se muestra un ejemplo típico

de árbol con raíz, el cual tiene un vértice definido

como tal.

Como el camino sencillo de la raíz a cualquier vértice es único, cada vértice está en un nivel determinado

de manera única. Decimos que el nivel de la raíz es el nivel 0. Los vértices debajo de la raíz están en un

nivel 1, y así sucesivamente. Así, el nivel de un vértice v es la longitud del camino sencillo de la raíz a v. La

altura de un árbol con raíz es el número máximo de nivel que aparece en dicho árbol.

Ejemplo: Examinando el árbol T mostrado en la figura (a) de abajo y designando al vértice e como el

vértice raíz, se obtiene el árbol con raíz T’ mostrado en la figura (b). Los vértices a, b, c, d, e, f, g, h, i, j

están en los niveles 2, 1, 2, 1, 0, 1, 1, 2, 2, 3, respectivamente. La altura del árbol T’ es 3.



Figura (a). Un árbol T, y figura (b). Un árbol con raíz T’.

T’ se obtiene de T designando a e como la raíz.

Con frecuencia, un árbol con raíz se utiliza para especificar relaciones jerárquicas. Cuando un árbol se

utiliza de esta manera, si el vértice a está en el siguiente nivel arriba del vértice b y, además, a y b son

adyacentes, entonces a está “justo arriba” de b y existe una relación lógica entre a y b: a domina a b o

b está subordinado a a de alguna manera. Un ejemplo de árbol con raíz especificando relación jerárquica,

es el que se muestra en la siguiente figura, es un organigrama de una universidad.

Ejemplo de organigrama



2.3.1. Tipos de árboles

Árbol de expansión

Un problema importante que está asociado a una red representada por un grafo consiste en obtener un

árbol de expansión para el grafo. Este árbol de expansión debe contener todos los vértices del grafo y

algunas de sus aristas, para asegurar su conectividad.

Definición: Un Árbol de Expansión de un grafo conexo no dirigido G = (N, A) es un árbol libre con el

conjunto de vértices N que es un subgrafo de G; esto es, un árbol de expansión es conexo, acíclico y tiene

a todo N como vértices y aparte de A como conjunto de aristas.

Teorema: Un grafo G tiene un árbol de expansión si y sólo si G es conexo.

Hay muchos enfoques para generar un árbol de expansión correspondiente a un grafo dado. Un enfoque

consiste en eliminar las aristas que pertenezcan a circuitos uno tras otro hasta que no queden circuitos en

el grafo. Si solo se eliminan aristas de circuitos, entonces el grafo seguirá siendo conexo, y esto es

esencial para la generación de un árbol de expansión.

Un ejemplo de este enfoque se ilustra en la siguiente figura. En este caso se decide eliminar los pares de

aristas siguientes: {2, 5}, {2, 6}, {3, 6}, {3, 7}, {4, 7}, {6, 7}. Obsérvese que se podrían generar muchos

árboles de expansión a partir del grafo dado.

Ejemplo de obtención de un árbol de expansión a partir de un grafo.

Árbol binario

Otra clase de árbol es el árbol binario. Los árboles binarios son de los tipos particulares más importantes

de árboles con raíz. Cada vértice de un árbol binario tiene a lo más dos hijos. Además, cada hijo se

designa como hijo izquierdo o como hijo derecho. Al trazar un árbol binario, un hijo izquierdo se dibuja a la

izquierda y un hijo derecho se dibuja a la derecha. La definición formal de árbol se da a continuación.

Definición: Un Árbol Binario es un árbol con raíz en el cual cada vértice tiene cero, uno, o dos hijos. Si un

vértice tiene un hijo, ese vértice se designa como un hijo izquierdo o como un hijo derecho, pero no ambos.

Si un vértice tiene dos hijos, uno de ellos se designa como hijo izquierdo y el otro como hijo derecho.



En la figura de al lado se muestra un ejemplo de árbol

binario. El vértice b es el hijo izquierdo y el vértice c

es el hijo derecho del vértice a. El vértice d es el hijo

derecho del vértice b; el vértice b no tiene hijo

izquierdo. El vértice e es el hijo izquierdo del vértice

c; el vértice c no tiene un hijo derecho.

Árbol binario

El árbol binario completo es un árbol binario en el cual cada vértice tiene dos o cero hijos. Un resultado

fundamental acerca de los árboles binarios completos es el siguiente teorema.

Teorema: Si T es un árbol binario completo con i vértices internos, entonces T tiene i+1 vértices

terminales y 2i + 1 vértices en total. El vértice raíz es considerado un vértice interno.

Isomorfismo

Al igual que los grafos, los árboles también presentan la propiedad de isomorfismo. Como un árbol libre es

un grafo sencillo, los árboles T1 y T2 son isomorfos si y sólo si existe una función, f , uno a uno y sobre el

conjunto de vértices de T1 al conjunto de vértices de T2 que preserva la relación de adyacencia, en el

sentido de que los vértices vi y vj son adyacentes en T1 si y sólo si los vértices f(vi) y f(vj) son

adyacentes en T2.

Ejemplo: la siguiente figura muestra un caso de isomorfismo. La función f del conjunto de vértices del árbol

T1 al conjunto de vértices del árbol T2 es una función uno a uno, sobre, que preserva la relación de

adyacencia. Por lo tanto, los árboles T1 y T2 son isomorfos.

f(a) = A, f(b) = B, f(c) = C, f(d) = D, f(e) = E



Árboles libres isomorfos.

Al igual que en el caso de grafos, se puede mostrar que dos árboles no son isomorfos si exhiben un

invariante no compartido por los árboles. Esto se puede ilustrar en la figura siguiente, en donde los árboles

T1 y T2 no son isomorfos, pues T2 tiene un vértice x de grado 3, pero T1 no tiene un vértice de grado 3.

Árboles libres no isomorfos.

Definición: Sea T1 un árbol con raíz r1 y sea T2 un árbol con raíz r2. Los árboles con raíz T1 y T2 son

isomorfos si existe una función f, uno a uno y sobre el conjunto de vértices de T1 en el conjunto de vértices

de T2 tal que:

a) Los vértices vi y vj son adyacentes en T1 si y sólo si los vértices f(vi) y f(vj) son

adyacentes en T2.

b) f(vi) = r2.

Decimos que la función f es un isomorfismo.

A continuación se dan dos ejemplos de árboles con raíz para identificar si tienen la propiedad de

isomorfismo.

Los árboles con raíz de la figura de abajo son isomorfos. Un isomorfismo es:

f(a) = A, f(b) = B, f(c) = C, f(d) = D, f(e) = E, f(f) = F, f(g) = G



Árboles con raíz isomorfos.

Los árboles con raíz de la siguiente figura no son isomorfos, pues la raíz de T1 tiene grado 3 y la raíz de T2

tiene grado 2. Estos árboles son isomorfos como árboles libres.

Árboles con raíz no isomorfos. Los árboles son isomorfos como árboles libres.

Actividad 5. Árbol genealógico

Con el fin de representar una secuencia genealógica utilizando árboles, realiza lo que se te pide a

continuación:

1. Utiliza un árbol para representar la secuencia genealógica de tu familia desde tus bisabuelos hasta la

última generación.

2. Guarda tu documento en un archivo de Word con el nombre MDI_U1_A5_XXYZ.

3. Envía tu archivo a tu Facilitador(a) mediante la sección de Tareas y espera su retroalimentación



Evidencia de aprendizaje. Grafo de rutina cotidiana

Con el fin de poner en práctica lo aprendido a lo largo de la presente unidad, lleva a cabo la evidencia de

aprendizaje, siguiendo las indicaciones:

1. Realiza un grafo de tu rutina diaria con al menos 10 actividades desde que te levantas de tu cama en la

mañana hasta que regresas a ella por la noche.

2. Usa un grafo simple para describir las actividades de un día normal. Las actividades corresponderán a

los vértices y se unirán mediante arcos.

3. Utiliza flechas en los arcos para indicar cómo se van desarrollando las actividades y resuelve cuál es el

grado de cada vértice del grafo.

4. Usa una matriz de adyacencia para representar el grafo.

5. Guarda tu documento con el nombre MDI_U2_EA_XXYZ y envíalo a tu Facilitador(a) mediante el

portafolio de evidencias.

6. Consulta la escala de evaluación para conocer los criterios que debe cumplir tu evidencia.

*Recuerda que debes hacer tu Autorreflexión al terminar la evidencia. Para ello, Ingresa al foro de

Preguntas de Autorreflexión y a partir de las preguntas presentadas por tu Facilitador(a), realiza tu ejercicio

y súbelo en la sección Autorreflexiones.


Es necesario tener a la mano papel y lápiz para poder resolver algunas operaciones, una recomendación

es utilizar el software Paint de Office para poder hacer los grafos.

Fuentes de consulta

Grassmann, W. & García, B. (2003). Matemática discreta y lógica. Madrid: Pearson Educación, S.A.

Johnsonbaugh, R. & Palmas, V. (1999). Matemáticas discretas (4ª ed.). México: Prentice Hall-

Hispanoamericana, S. A.

McEliece, R. (1989). Introduction to discrete mathematics. New York: Random House.

Skiena, S. (1990). Implementing discrete mathematics: Combinatoric and graph theory with mathematica.

California: Addison-Wesley Pub. Co.



UNIDAD 3. RELACIONES


El propósito de esta unidad es analizar el concepto de relación y

establecer distintos tipos de relaciones a conjuntos; así como

representar mediante grafos o matrices dichas relaciones, con la

finalidad de establecer las características específicas de los

elementos.


Analizar estructuras básicas para identificar las clases y los tipos de

relaciones, resolviendo operaciones entre conjuntos e interpretando

sus propiedades.


En Física y Matemáticas (y en particular en Ciencias

Computacionales) siempre estamos comparando cosas, escribiendo

“relaciones” entre diferentes cantidades. Usualmente, al

compararlas utilizamos símbolos para denotar que son iguales,

mayores o menores unas con respecto a otras. Pero la idea de

relación puede ir más allá e implicar diferentes asociaciones.

En esta unidad estudiaremos las diferentes asociaciones que dan origen a relaciones particulares, cómo se

definen formalmente éstas de manera matemática y sus propiedades.

Primero las explicaremos de forma que podrá parecer un poco descuida y poco formal, pero que redundará

en beneficio del lector que por primera vez tiene contacto con esta materia y posteriormente se introducirá

la definición rigurosa en el lenguaje de las matemáticas abstractas para que puedas profundizar en el

tema.



3.1. Introducción a la relación

El concepto de relación implica un nivel de abstracción elevado, sin embargo es esencial en una gran

variedad de temas. Coloquialmente, la palabra “relación” tiene muchos significados y diferentes

interpretaciones dependiendo del contexto en el que se le utilice. Por ejemplo, antiguamente se aplicaba al

relato de un viaje o una crónica. En el contexto de las matemáticas, una relación se entiende más como la

existencia de una conexión entre dos entidades matemáticas, ya sean números o símbolos.

Muchas veces se emplea el concepto de relación sin siquiera tenerlo en

cuenta de manera explícita o definirlo. Esto sucede en los pares

ordenados, que describen las coordenadas cartesianas en un plano. De

la misma manera, una función establece una relación entre dos o más

cantidades.

Como veremos a lo largo de esta unidad, existen diferentes tipos de relaciones y éstas a su vez pueden

ser de extensión finita o infinita dependiendo del número de elementos entre los cuales se establezca la

relación que se quiera definir.

En este curso nos limitaremos a estudiar las características de las

relaciones aplicadas a colecciones o conjuntos finitos; de hecho,

en la unidad anterior ya hemos utilizado las relaciones a la hora

de definir los grafos, o bien, dicho de otra forma, los grafos

pueden ser dibujados a partir de relaciones como veremos a lo

largo de esta unidad.

Las relaciones son definidas sobre colecciones (o conjuntos) de objetos. Los objetos son usualmente

números, pero en general puede ser cualquier cosa. Como ejemplo consideremos el conjunto de

elementos {1, 2, ☺, ¬_¬, ^_^, 123}, esta es una colección finita, con un número determinado de elementos,

en particular nuestra colección contiene solo seis elementos. A pesar de que el símbolo “¬_¬” está formado

por tres caracteres sigue siendo un único elemento de la colección, de la misma forma que el número 123

se considera un solo elemento, pero se requieren tres caracteres para representarlo.



Entonces, por relación entendemos, por ejemplo, una colección

de pares ordenados de los objetos que se encuentran en la

colección: = {(1, ☺), (123, ^_^), (2, 1)}.

De la colección anterior podemos decir que 1 está relacionado

con ☺, 2 está relacionado con 1, pero ☺ no está relacionado con

¬_¬.

Sin embargo, usar esta nomenclatura para establecer o

mencionar la existencia de una relación entre dos objetos es poco

elegante y tedioso.

En la literatura, los autores usan diferente nomenclatura y simbología para denotar una relación entre dos

objetos, por ejemplo, (1, ☺) pertenece a la relación . Sin embargo, esta forma de enunciarlo aún sigue

siendo larga y puede hacerse más compacta utilizando el símbolo que entenderemos como “pertenece

a”, así (1, ☺) . Otra forma común y más compacta de escribir esto mismo corresponde a 1☺.

Dependiendo de la relación que se establezca entre dos objetos podemos representarla de manera más

compacta definiendo un símbolo en particular para esa relación, de esta manera podemos decir 1~☺, que

significaría 1 está relacionado con ☺ a través de la relación . En muchos casos ya existe un símbolo

predeterminado para un tipo particular de relación como veremos más adelante.

3.1.1. Definición de relación

Antes de pasar a definir de manera formal lo que se entiende por relación, abordaremos una operación

lógica esencial en la secuencia conceptual de los conceptos que discutiremos en este apartado, nos

referimos al Producto Cartesiano.

Seguramente ya hay una familiaridad con el producto convencional entre

dos números normales (escalares), probablemente también sea conocido

el producto punto o escalar entre dos vectores y el producto vectorial o

producto cruz. De la misma manera, puede ser posible que ya se haya

comenzado el estudio del producto de matrices. Éste no es más que una

generalización del producto escalar, también conocido como producto

interno. Existen otros tipos de productos y el producto cartesiano es uno

de ellos.

La operación definida como producto cartesiano recibe su nombre del

matemático francés René Descartes, quién desarrolló la formulación de la

Geometría Analítica, introduciendo de esta manera el concepto de par

ordenado en las coordenadas cartesianas.



El producto directo de dos conjuntos es lo que se conoce como producto cartesiano en la teoría de

conjuntos. Si tenemos dos colecciones o conjuntos, su producto directo generará un nuevo conjunto

formado por los pares ordenados de cada elemento del primer conjunto y un elemento del segundo

conjunto. De esta manera si se tienen dos conjuntos con n y m elementos su producto directo generará n

m elementos (n, m). Donde se ha escogido el símbolo “ ” para denotar el producto directo.

Ejemplo de producto cartesiano

Se tienen dos colecciones:

F = (manzana, durazno)

C = (verde, amarillo, rojo).

Encuentra su producto cartesiano.

Solución.

Calculamos este producto como:

R = FC = {(manzana, verde), (manzana, amarillo), (manzana, rojo), (durazno, verde), (durazno, amarillo),

(durazno, rojo)}.

El producto cartesiano en general no es conmutativo.

A continuación definiremos formalmente el producto cartesiano de manera general.

Definición. Sean los conjuntos 1 2, ,..., nX X X , el producto cartesiano n-ario de estos, denotado por

1 2 ... nX X X , es el conjunto de todos los pares ordenados en los cuales el primer elemento se

encuentra en el conjunto X1, el segundo en el conjunto X2, y así sucesivamente, de tal forma que:

1 2 1 2 1 1 2 2... , ,..., ... .n n n nX X X x x x x X x X x X

Para el ejemplo que se ha dado, con solo dos elementos se tiene que:

Definición. El producto cartesiano de dos conjuntos X y Y, denotado por XY, es el conjunto de todos los

pares ordenados en los cuales el primer elemento se encuentra en el conjunto X y el segundo en el

conjunto Y:

, .X Y x y x X y Y

Con los conceptos que acabamos de revisar, ya es posible dar una definición formal de relación.

En el caso del producto cartesiano primero definiremos una relación entre cualquier número de conjuntos y

posteriormente trataremos el caso particular de solo dos conjuntos, como se ejemplificó de manera

informal al inicio de la unidad.

Definición. Sean los conjuntos 1 2, ,..., nX X X . Una relación n-aria en estos conjuntos es un subconjunto

del producto cartesiano n-ario 1 2 ... nX X X . Los conjuntos 1 2, ,..., nX X X son llamados el dominio y n

se conoce como el grado de la relación. Simbólicamente:

1 2 ... .nX X X



Si = 0, llamaremos a esta relación, una relación vacía. Si = 1 2 ... nX X X , será una relación

universal, mientras que en el caso particular en que solo tengamos tres conjuntos será una relación

ternaria y para dos conjuntos una relación binaria. Estas últimas tienen mayor interés para nuestro curso

ya que, por ejemplo, el espacio cartesiano tridimensional se forma al multiplicar (producto cartesiano) el

conjunto de los números reales por sí mismo tres veces y de forma análoga el plano cartesiano, cuando el

conjunto de los números reales se multiplica por sí mismo una vez. Otro ejemplo de una relación binaria la

encontramos cuando se hizo el producto cartesiano de la colección de colores por la colección de frutas.

El resto de esta unidad estará dedicado a relaciones binarias, a sus propiedades y a las operaciones que

son posibles llevar a cabo con ellas.

Actividad 1. Definición de relación

Con el propósito de construir una definición general de relación, que incluya las relaciones matemáticas y

las relaciones entre personas, debes de participar colaborativamente en el espacio del Foro que lleva el

mismo nombre que esta actividad. Para ello realiza lo siguiente:

1. Ingresa al foro y responde a lo siguiente:

¿Qué características esenciales definen las relaciones entre las personas?

¿Qué características básicas tienen las relaciones matemáticas?

¿Será posible relacionar los números y el comportamiento de las personas?

2. Recuerda comentar respetuosamente la participación de mínimo dos de tus compañeros(as).

Puedes consultar la Rúbrica de participación general del foro, que se encuentra en la sección Material de

apoyo.

3.1.2. Relación binaria

El grado dos de una relación es usualmente el más común, ya que cuando se empieza a estudiar el

comportamiento de un fenómeno o la influencia de una cantidad con respecto a otra, es conveniente sobre

simplificarlo y estudiar la relación que existe entre un par de colecciones o conjuntos, dando origen de esta

manera a una relación binaria. En lo sucesivo nos referiremos a una relación binaria simplemente como

una “relación”, en caso de que el grado de la relación sea diferente de dos se mencionará explícitamente.

Definición. Sean los conjuntos X y Y. Una relación binaria en estos conjuntos es un subconjunto del

producto cartesiano binario X Y . Simbólicamente:

X Y



En el ejemplo anteriormente mencionado, sobre las frutas y colores, se calculó el producto cartesiano. El

conjunto solución tiene seis elementos pero una relación definida en ese conjunto puede tener un número

menor o igual de elementos dependiendo de las condiciones establecidas. Por ejemplo, supón que se pide

que las frutas sean rojas, entonces la relación estará dada por el subconjunto {(manzana, rojo),

(durazno, rojo)}. Esta relación solo tiene dos elementos y podemos decir que “manzana rojo” pero

“manzana verde”.

Ejemplo.

Sea el conjunto A = {1, 2, 3} y la relación = {(3, 2), (3, 1), (2, 1)}. Menciona qué característica satisface la

relación.

Solución.

La relación es un subconjunto del producto cartesiano AA y se pude expresar como:

, .a b a b

Es importante aclarar que en este caso se debe entender el elemento a como un elemento cualquiera del

conjunto A y el elemento b es otro elemento cualquiera del conjunto A, sin embargo puede o no ser igual a

a, en nuestro ejemplo en particular necesariamente tiene que ser diferente de a.

Definición. Para cualquier relación X Y :

El subconjunto de X ; , , ,x x X y Y x y es llamado el dominio de .

El subconjunto de Y ; , , ,y y Y x X x y es llamado el rango de .

En otras palabras, esto significa que todos los elementos del conjunto X que forman parte de la relación

serán el dominio. Mientras que todos los elementos del conjunto Y que forman parte de la relación

serán el rango.

Ejemplo. Sea la relación = {(3, 2), (3, 1), (2, 1)}. ¿Cuál es su dominio y cuál su rango?

Solución. El dominio y el rango estarán dados por: dominio = {2, 3}, rango = {1, 2}.



3.1.3. Matriz de una relación

El concepto de representar una relación en términos de matrices es muy

similar al visto en la unidad dos: Grafos y árboles, en los temas Matrices

de adyacencia y Matrices de incidencia. Curiosamente ahí se partió de

una representación visual e intuitiva y se llegó a su equivalente matricial,

en esta sección, por el contrario, empezaremos con la representación

matricial de una relación y en la sección siguiente se describirá su grafo o

gráfica directa.

Como hemos procedido hasta el momento, primero daremos un ejemplo para que se visualice

directamente el procedimiento y posteriormente se entienda la definición formal sin mucho problema.

Retomando el ejemplo de las frutas y colores, con el que ya estamos familiarizados, tenemos el producto

cartesiano R = FC = {(manzana, verde), (manzana, amarillo), (manzana, rojo), (durazno, verde),

(durazno, amarillo), (durazno, rojo)}.

Recordando que la relación pide que las frutas sean rojas, entonces

estará dada por el subconjunto {(manzana, rojo), (durazno, rojo)}.

La representación matricial se escribe como sigue: las filas serán los

elementos de F y las columnas los elementos de C, si en la (fila,

columna) existe un elemento de en la matriz se colocará un 1, de

lo contrario será un cero.

De esta manera vemos que es muy sencillo generar la matriz asociada a una relación.

Definición. Una relación entre conjuntos finitos puede ser representada mediante una matriz de

ceros y unos. Sea una relación entre un conjunto X = {x1, x2,…, xm} y un conjunto Y = {y1,

y2,…, yn}. La relación puede ser representada por la matriz ,ijm M donde:

1, si , ,

0, si , .

i j

ij

i j

x ym

x y

Es decir, que el elemento (xi, yj) será 1 si existe “xi yj” y 0 cuando “xi yj”. Es claro que esta

representación depende totalmente de la forma en que se asigna, por convención, el conjunto X y el

conjunto Y en filas y columnas, respectivamente; así como del orden en que los elementos de cada uno de

estos conjuntos son listados. Usualmente, el dominio es subconjunto de X y el rango es subconjunto de Y.

Ejemplo de relación entre conjuntos finitos.

Encuentra la representación matricial de la relación entre los conjuntos A = {1, 2} y B = {1, 3, 2} que

contiene los elementos (a, b) sí , y a A b B a b . Además: a1 = 1, a2 = 2, b1 = 1, b2 = 3 y b3 = 2.



Solución. Primero escribimos los elementos de la relación = {(1, 3), (1, 2), (2, 3)} y ahora la

representamos matricialmente:

Nota que en este caso el conjunto B no tiene sus elementos ordenados ascendentemente y

consecuentemente se nombró b2 = 3. En general las matrices pueden ser más grandes pero dado que lo

importante es entender el concepto, trataremos de limitarnos a matrices de doce elementos como máximo.

3.1.4. Grafo de una relación

En esta sección discutiremos el problema inverso al revisado en la unidad dos, es decir, en vez de

representar un grafo como matriz, acá partiremos de la relación y dibujaremos el grafo. El grafo en este

contexto también es conocido como gráfica directa o para abreviar digráfica.

Definición. La digráfica es un conjunto de vértices (o nodos) V junto con un conjunto E de pares

ordenados de elementos de V llamados arcos (o aristas dirigidas). El vértice a es llamado el vértice inicial

del arco (a, b) y el vértice b es llamado el vértice terminal.

El caso en que se tiene un elemento de la relación de la forma (a, a) también está comprendido en la

digráfica y se representa por un vértice que se conecta consigo mismo a través de un lazo.

Ya que este tema se estudió a mayor detalle y profundidad en la unidad dos, aquí solo daremos un

ejemplo sencillo.

Ejemplo.

Dibuja la digráfica de la relación = {(1, 3), (1, 2), (2, 3)}.

Solución. La digráfica de esta relación se muestra en la figura siguiente:

Actividad 2. Relaciones

Esta actividad tiene como finalidad que realices ejercicios sobre los tipos de relaciones estudiados en lo

que va de la unidad.

1. Responde a los siguientes planteamientos:

¿Cuál será el número de elementos de un producto cartesiano entre los conjuntos A = {a1, a2, a3, a4} y

B = {b1, b2}?

Encuentra todos los elementos del producto cartesiano AB de los conjuntos dados en el

planteamiento anterior.



Dada la relación = {(1, 2), (3, 4), (5, 6)}, menciona cuál es su dominio y cuál su rango. ¿Cuáles son

los dos conjuntos más pequeños posibles tales que su producto cartesiano genera esta relación como

un subconjunto de éste?

Da la matriz asociada a la relación = {(1, ), (7, 2e), (4, 0), (4, 2)}, si los conjuntos que la generaron

son A = {1, 4, 7} y B = {2, , 2e, 0} y los elementos de la relación están formados por los elementos (a,

b) si ,a A b B . Enumera los elementos tal como están enlistados para representar la matriz.

Dada la matriz:

1 0

0 1

0 1

1 0

M Escribe los elementos de la relación asociada, si los conjuntos que la

generaron son A = {a1, a2, a3, a4} y B = {b1, b2}.

Dada la relación = {(1, 1), (1, ), (7, 2), (2, 4), (4, 2), (e, e)}. Dibuja su digráfica.

2. Guarda tu documento con el nombre MDI_U3_A2_XXYZ y envíalo a tu Facilitador(a) a través de la

sección de Tareas, espera su retroalimentación para complementar tu aprendizaje.

3.2. Propiedades de las relaciones

Los elementos que forman una relación a veces presentan particularidades especiales que los hacen

susceptibles para realizar ciertas operaciones sobre relaciones de manera más rápida o eficiente. Como

estas características son inherentes a los elementos que forman la relación y no a las relaciones en sí, es

posible generalizarlas y emplearlas para clasificar las relaciones en diferentes grupos de acuerdo, como ya

se dijo, a las características de sus elementos. En este tema veremos algunas de las propiedades más

usadas para clasificar las relaciones originadas sobre un producto cartesiano con sí mismo. Es decir,

Definición. Una relación sobre un conjunto X es una relación de X a X.

Esto significa que las relaciones bajo estudio en esta sección serán siempre un subconjunto del producto

cartesiano de un conjunto con sí mismo .X X Estas propiedades de las relaciones no son

necesariamente excluyentes unas con otras, en algunos casos una relación puede tener dos o más

propiedades al mismo tiempo.

3.2.1. Reflexiva

Definición. Una relación sobre un conjunto A, se llama reflexiva si el elemento (a, a) pertenece a la

relación. Es decir, a a a A .

Lo esencial para que una relación sea reflexiva es que contenga todos los elementos de su dominio

relacionados consigo mismos. La existencia en la relación de otros elementos del conjunto generado por el

producto cartesiano de A con A no es de importancia en la definición.



Ejemplo. ¿Cuáles de las siguientes relaciones son reflexivas sobre el conjunto A = {1, 2, 3, 4}?

1 = {(1,1), (2, 2), (3, 3), (4, 4)}

2 = {(1,1), (1, 2), (2, 3), (3, 1), (3, 3), (4, 4)}

3 = {(1,1), (1, 2), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 3), (4, 1), (4, 4)}

4 = {(1, 2), (2, 1), (2, 2), (2, 4), (3, 1), (3, 3), (4, 1)}.

Solución. La relación 1 es la esencia de la definición de reflexiva, ya que contiene puros elementos de la

forma (a, a) y son todos los que se pueden generar con los elementos del conjunto A. Las relaciones 2 y

4 no son reflexivas. En el primer caso porque el elemento (2, 2) está ausente y en el segundo porque no

se encuentra el elemento (1, 1) ni el elemento (4, 4). Finalmente, 3 es reflexiva ya que los cuatro

elementos de la forma (a, a) que pueden obtenerse del conjunto A están presentes en la relación.

3.2.2. Irreflexiva

Definición. Una relación sobre un conjunto A, se llama irreflexiva si el elemento (a, a) no pertenece a la

relación. Es decir, , ,a A a a .

Este caso es muy claro, la única condición que se pide para que la relación sea irreflexiva es que no haya

elementos conectados consigo mismos, es decir, de la forma (a, a). De esta manera la propiedad reflexiva

y la irreflexiva son mutuamente excluyentes en una relación.

Ejemplo. ¿Cuáles de las siguientes relaciones son irreflexivas sobre el conjunto A = {1, 2, 3, 4}?

1 = {(1,1), (2, 2), (3, 3), (4, 4)}

2 = {(1, 2), (2, 3), (3, 1), (3, 4)}

3 = {(1, 2), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 3), (4, 1)}

4 = {(1, 2), (2, 1), (2, 4), (3, 1), (4, 1)}.

Solución. 1 no es irreflexiva pues todos sus elementos son de la forma (a, a). 2 es irreflexiva, no hay

elementos de la forma (a, a). 3 no es irreflexiva ya que se encuentra el elemento (2, 2) y (3, 3). 4 es

irreflexiva, ya que no contiene elementos de la forma (a, a).

3.2.3. Simétrica

Definición. Una relación sobre un conjunto A, se llama simétrica si el elemento (a, b) pertenece a la

relación y también el elemento (b, a) está en la relación. Es decir, , ,a b b a a b .



Al analizar esta definición, la única condición que se pide es que cada elemento de la relación debe de

tener un elemento cuyos componentes estén “invertidos”. Además, la posibilidad de que b = a no está

excluida. Si todos los elementos de la relación son de la forma a b , basta con contarlos y si son un

número impar la relación no puede ser simétrica.

Ejemplo. De las siguientes relaciones sobre el conjunto E = {, , }, ¿cuáles son simétricas?

1 = {(, ), (, ), (, ), (, )}

2 = {(, ), (, ), (, ), (, ), (, ), (, ) }

3 = {(, ), (, ), (, ), (, ), (, )}

4 = {(, ), (, ), (, ))}

Solución. La relación 1 no es simétrica, ya que no contiene el elemento (, ). Las relaciones 2 y 3

son simétricas. 2 posee todas las posibles permutaciones sin repetición de nuestros tres “emoticones”.

3 es simétrica ya que el elemento (, ) es él mismo la inversión por ser de la forma (a, b) con b = a.

Finalmente, 4 es evidentemente no simétrica, pues ningún elemento tiene su contraparte.

3.2.4. Asimétrica

Definición. Una relación sobre un conjunto A, se llama asimétrica si el elemento (a, b) pertenece a la

relación pero el elemento (b, a) no está en la relación. Es decir, , ,a b b a a b .

Esta definición no excluye la posibilidad de que a = b, así pues los elementos de la forma (a, a) no pueden

estar en la relación asimétrica, ya que son la contra parte de sí mismos. En algunos textos la relación

asimétrica también es llamada no simétrica.

Ejemplo. De las siguientes relaciones sobre el conjunto E = {, , }, ¿cuáles son asimétricas?

1 = {(, ), (, ), (, )}

2 = {(, ), (, ), (, ), (, ), (, ), (, ) }

3 = {(, ), (, ), (, )}

Solución. 1 no es asimétrica ya que se encuentra el elemento (, ). 2 no es asimétrica pues cada

elemento tiene su contraparte como por ejemplo (, ) y (, ). 3 es la única relación asimétrica.

3.2.5. Antisimétrica

Definición. Una relación sobre un conjunto A, se llama antisimétrica si el elemento (a, b) pertenece a la

relación, si también se encuentra el elemento (b, a) en la relación entonces debe de cumplirse que a = b.

Es decir, , ,a b b a a b a b .



Esta definición es un tanto abstracta, ya que pide la condición de un elemento de la forma (a, b), y además

si en la relación también existe un elemento de la forma (b, a) entonces éste debe de satisfacer que a = b.

La condición de la definición también es equivalente a decir que si el elemento (a, b) se encuentra en la

relación y a b , entonces (b, a) no puede estar en la relación para que sea del tipo antisimétrico.

Ejemplo. De las siguientes relaciones sobre el conjunto E = {, , }, ¿cuáles son antisimétricas?

1 = {(, ), (, ), (, )}

2 = {(, ), (, ), (, ), (, ), (, ), (, ) }

3 = {(, ), (, ), (, ), (, )}

4 = {(, ), (, ), (, ))}

Solución. 1 es antisimétrica, el primer elemento es de la forma (a, a) y los otros dos de la forma (a, b) sin

que exista su contraparte (b, a) siendo a b . Por ejemplo 1 pero 1 . 2 y 3 no son

antisimétricas ya que existen elementos (a, b) y también (b, a) siendo a b . 4 sí es antisimétrica porque

todos sus elementos son de la forma (a, b) sin que exista su contraparte (b, a) siendo a b .

3.2.6. Transitiva

Definición. Una relación sobre un conjunto A, se llama transitiva si el elemento (a, b) pertenece a la

relación y también se encuentra el elemento (b, c) en la relación entonces debe de cumplirse (a, c) también

esté en la relación. Es decir, , , ,a b b c a c a b c .

Naturalmente, si se encuentra un elemento de la forma a = b, éste automáticamente satisface la condición

de transitividad. Esta condición es más fácil de visualizar con números que con símbolos.

Ejemplo. ¿Cuáles de las siguientes relaciones son transitivas sobre el conjunto A = {1, 2, 3, 4}?

1 = {(1,1), (2, 2), (3, 3), (4, 4)}

2 = {(1,1), (1, 2), (2, 3), (1, 3), (3, 3), (4, 4)}

3 = {(1, 2), (1, 4), (2, 1), (2, 2), (2, 3), (3, 4), (3, 3), (4, 1), (4, 4)}

4 = {(1, 2), (2, 1), (2, 2), (2, 4), (3, 3), (1, 4), (1, 1)}.

Solución. 1 , 2 y 4 son relaciones transitivas. La primera porque todos sus elementos son de la forma

(a, a). 2 porque entre los elementos de la forma (a, b) siendo a b se cumple que (a, b), (b, c) y (a, c) se

encuentran en la relación, en particular (1, 2), (2, 3) y (1, 3) satisfacen esta condición. 4 es transitiva ya

que: (1, 2), (2, 1) y (1, 1); (1, 2), (2, 4) y (1, 4) están en la relación. 3 no es transitiva porque (1, 2) y (2, 1)

están en la relación pero (1, 1) no está en la relación. De la misma forma (2, 3) y (3, 4) están en la relación

pero (2, 4) no está.



Para terminar este tema, es importante mencionar que todas estas propiedades de las relaciones

presentan características muy particulares a la hora de ser dibujadas como digráficas.

Actividad 3. Propiedades de las relaciones

Con la finalidad de que realices relaciones binarias de conjuntos, lleva a cabo lo que a continuación se te

pide:

1. Realiza lo siguiente:

Dados los conjuntos: , escribe las relaciones:

A x B=

A x C =

C x A =

A x D =

Dadas las siguientes relaciones sobre el conjunto C ={ , , , }.

1 = {( , ), ( , ), ( , ), ( , ), ( , )}

2 = {( , ), ( , ), ( , ), ( , ), ( , )}

3 = {( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , )}

4 = {( , ), ( , ), ( , ), ( , ), ( , ), ( , )}

5 = {( , ), ( , ), ( , ), ( , ), ( , ), ( , )}

Contesta las siguientes preguntas acerca de las propiedades de las relaciones:

- ¿Cuál(es) de las relación(es) anterior(es) es reflexiva?

- ¿Cuál(es) de las relación(es) anterior(es) es transitiva?

- ¿Cuál(es) de las relación(es) anterior(es) es simétrica?

- ¿Cuál(es) de las relación(es) anterior(es) es irreflexiva?

- ¿Cuál(es) de las relación(es) anterior(es) es asimétrica?

Elabora el ejemplo de una relación que sea reflexiva, simétrica y antisimétrica al mismo tiempo, sobre el

conjunto C ={ , , , }.

2. Guarda y envía tu documento como MDI_U3_A3_XXYZ. Recuerda que tu archivo no debe pesar más de

4MB.

3. Espera la retroalimentación de tu Facilitador(a), y si fuere necesario corrige tu actividad.



3.3. Operaciones con relaciones

Una relación se puede identificar como un conjunto de pares

ordenados, en el cual se pueden realizar operaciones de una

relación de dos conjuntos.

Existen, además, algunas operaciones que no son tan

comunes en los cursos básicos de teoría de conjuntos, mismas

que se presentarán en este tema.

3.3.1. Operaciones con relaciones

A continuación revisaremos las operaciones más comunes, mediante un ejemplo.

Dadas las relaciones:

1 = {(1,1), (1, 2), (2, 3), (1, 3), (3, 3), (4, 4)}

2 = {(1, 2), (1, 4), (2, 1), (2, 2), (2, 3), (3, 4), (3, 3), (4, 1), (4, 4)}.

Encuentra:

a) la unión 1 2 ,

b) la intersección 1 2 ,

c) la diferencia de 1 2 y

d) la diferencia de 2 1 .

Solución.

La unión de dos conjuntos consiste en crear un nuevo conjunto que contenga todos

los elementos de los que lo generan, sin repetir ningún elemento aunque éste esté

en ambos conjuntos generadores. La unión en este caso es:

1 2 = {(1,1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 3), (3, 4), (4, 1), (4, 4)}.

La intersección consistirá en un nuevo conjunto formado por los elementos que

aparecen en los dos conjuntos que le dieron origen:

1 2 = {(1, 2), (2, 3), (3, 3), (4, 4)}.



La diferencia de conjuntos es retirar de un conjunto (minuendo) los elementos de

otro (sustraendo) si es que están presentes en el conjunto minuendo. De tal forma

que:

1 2 = {(1,1), (1, 3)}.

En este caso:

2 1 = {(1, 4), (2, 1), (2, 2), (3, 4), (4, 1)}.

Existen otras operaciones que se aplican con la unión de las operaciones básicas de relaciones, en las

cuales se forma un conjunto nuevo a partir de conjuntos universales.

Ahora se presentarán dos operaciones que se aplican en el Álgebra Booleana y en particular en

conjuntos. La diferencia simétrica y la diferencia compuesta.

Diferencia simétrica

La diferencia simétrica de A y B, denotada por la forma A B , es el conjunto que contiene los elementos

que se encuentran ya sea en A o en B, pero no en ambos.

Ejemplo. Encuentra la diferencia simétrica 1 2 de los conjuntos:

1 = {(1,1), (1, 2), (2, 3), (1, 3), (3, 3), (4, 4)}

2 = {(1, 2), (1, 4), (2, 1), (2, 2), (2, 3), (3, 4), (3, 3), (4, 1), (4, 4)}.

Solución. Si analizamos los conjuntos, identificamos que existen relaciones entre estos dos, en los cuales

ciertas coordenadas se encuentran tanto en el conjunto 1 como en el conjunto 2 . En este caso la

operación simétrica es la combinación de dos operaciones, la unión y la intersección:

1 2 1 2 1 2 .

Además, por la forma en que fue definida la operación, vemos que es conmutativa. Es decir, 1 2 =

2 1 . El conjunto resultante de esta operación será:

1 2 = {(1,1), (1, 3), (1, 4), (2, 1), (2, 2), (3, 4), (4, 1)}.

Diferencia compuesta

Cuando se tienen tres conjuntos y estos se relacionan entre sí, se toman elementos de los tres conjuntos y

se forma una operación compuesta, ya que participan en la operación tres conjuntos con sus elementos

respectivos.

Definición: Si tomamos a como una relación entre el conjunto A y B, y sea una relación del conjunto

B y C. La operación compuesta de y es la relación consistente de pares ordenados (a, c), donde

,a A c C y para la cual existe un elemento b B tal que ,a b y ,b c . La compuesta de

con se denotará .



Ejemplo 1:

Encuentra B o A para los conjuntos:

A = {(1, 4), (2, 6), (3, 2), (5, 1), (7, 3)}

B = {(6,1), (2, 4), (1, 3), (3, 4)}.

Solución.

El elemento (1, 4) del conjunto A no puede ser compuesto con ningún elemento del conjunto B, ya que en

éste no hay elementos de la forma (4, x). El elemento (2, 6) de A puede ser compuesto con el elemento (6,

1) en B y el resultado será (2, 1). El elemento (3, 2) en A puede ser compuesto con el elemento (2, 4) en B,

el resultado será (3, 4). De la misma manera (5, 1) y (1, 3) dará (5, 3) y finalmente (7, 3) y (3, 4) generará

(7, 4). Por lo tanto,

B A = {(2, 1), (3, 4), (5, 3), (7, 4)}.

Ejemplo 2:

Encuentra 2 para la relación = {(1,1), (1, 2), (2, 3), (1, 3), (3, 3), (4, 4)} definida sobre el conjunto A = {1,

2, 3, 4}.

Solución.

Cuando se busca una relación en un conjunto particular, es decir la relación con él mismo, la operación

compuesta es denominada potenciación.

Definición: Sea una relación sobre un conjunto A, las potencias n , n = 1, 2, 3, …, están definidas

recursivamente por:

1 2 3 2 1, , , .n n

Se buscan las relaciones de cada elemento de con sus consecutivos.

Haremos la composición entre dos conjuntos iguales. Esto es, el elemento (1, 1) será compuesto con los

elementos (1, 1), (1, 2), (1, 3). El elemento (1, 2) con los elementos (2, 3) y así sucesivamente. Entonces,

el conjunto solución sería: 2 = {(1, 1), (1, 2), (1, 3), (2, 3)}.

Como comentario diremos que este ejemplo de relación corresponde al que se dio para una relación con

propiedad transitiva. La potenciación de estas relaciones siempre da como resultado un subconjunto de sí

misma. A continuación daremos el teorema sin hacer la demostración, ya que ver la demostración formal

está más allá de los objetivos de este curso.

Teorema. La relación en un conjunto A es transitiva si y solo si n para n = 1, 2, 3,…

Actividad 4. Operaciones con relaciones

Con la realización de esta actividad pondrás en práctica lo visto hasta este momento, para hacerlo:

1. Resuelve los siguientes problemas:



Dadas las siguientes relaciones:

1 = {(, ), (, ), (, ), (, ), (, ), (, ) }

2 = {(, ), (, ), (, ), (, ), (, )},

sobre el conjunto E = {, , }. Encuentra:

- La unión 1 2 .

- La intersección 1 2 .

- La diferencia de 1 2 y 2 1 .

- La diferencia simétrica 1 2 .

Encuentra n para la relación = {(1, 1), (1, 2), (2, 3), (1, 3), (3, 3), (4, 4)} definida sobre el conjunto

A = {1, 2, 3, 4}.

Con el propósito de verificar la solución de problemas con el uso de relaciones, resuelve la

demostración de la siguiente relación:

- Demuestra las dos contenencias:

.

En la prueba anterior, si se invierte el sentido de las implicaciones se obtiene la demostración de la

parte (b).

Completa la demostración del teorema anterior.

Demuestra por inducción que:

.

Por último, al invertir las parejas de una relación R obtenemos otra relación, llamada la relación inversa de

R.




4MB.

3. Espera la retroalimentación de tu Facilitador(a), y si fuere necesario corrige tu actividad.

3.4. Relaciones de equivalencia

Como se estudió en el tema anterior, las propiedades de las

relaciones no son siempre mutuamente excluyentes. Es decir, una

misma relación puede presentar varias propiedades a la vez. Este

tipo de relaciones son de particular importancia en las bases de

datos y se aplican en ciencias computacionales para minimizar y

optimizar tiempos de búsqueda o tiempos de ejecución en

programación.

A veces es deseable comparar dos diferentes relaciones que aparentemente no tienen ninguna conexión

en particular. Es posible hacer este tipo de comparaciones con relaciones que satisface varias condiciones

o propiedades a la vez, ya que podemos establecer una comparación o equivalencia entre ambas

relaciones y sus elementos, estas relaciones son llamadas relaciones equivalentes, sobre las cuales se

abordará a continuación.

3.4.1. Relación de equivalencia

Definición. Una relación sobre un conjunto A, es llamada relación equivalente si es reflexiva, simétrica y

transitiva al mismo tiempo.

Definición. Dos elementos a y b relacionados en una relación equivalente son llamados equivalentes y

será denotado a~b.

Usualmente para indicar que dos elementos están relacionados en una relación de equivalencia se utiliza

la notación a~b, debe entenderse con esta relación que existe una relación sobre un conjunto A tal que

,a b A y a b. Además, esta relación es reflexiva, simétrica y transitiva, es decir, es una relación

equivalente.

En una relación equivalente para cualquier elemento de la relación a~a, dicho elemento está relacionado

consigo mismo (propiedad reflexiva). Para un elemento a~b debe de existir su contraparte b~a (propiedad

de simetría). Y la propiedad transitiva existe, si a está relacionado con b y b está relacionado con c,

entonces a está relacionado con c, a~b y b~c entonces a~c.

Ahora daremos un ejemplo sencillo de una relación equivalente:

Ejemplo. Sea el conjunto A = {1, 2, 3, 4}, entonces la siguiente relación es equivalente sobre A: = {(1, 1),

(2, 2), (3, 3), (4, 4), (1, 2), (2, 3), (1, 3), (2, 1), (3, 2), (3, 1)}. Explica por qué.



Solución. Los primeros cuatro elementos de la relación son esenciales para que se cumpla la reflexividad,

ya que son todas las posibilidades de la forma a~a dados los elementos del conjunto A. Los elementos (1,

2), (2, 3) y (1, 3) cumplen transitividad y los elementos (2, 1), (3, 2) y (3, 1) son la contraparte de los

anteriores (simetría). Además, de estos mismos vemos que (3, 2) y (2, 1) generan a (3, 1) por transitividad.

En el siguiente tema se revisará cómo generar una relación equivalente a partir de una que no lo es. Por

ejemplo, si la relación bajo estudio no tiene transitividad o simetría, con base en los elementos que ya se

encuentran en la relación, se explicará cómo agregar nuevos elementos a la relación tal que la nueva

relación sea equivalente.

3.4.2. Cerraduras

Como ya hemos visto, las relaciones no siempre tienen las propiedades que hemos descrito anteriormente.

A veces es conveniente generar una nueva relación “auxiliar” que sí satisfaga alguna de las reglas dadas

para las diferentes propiedades estudiadas. A esta acción de “a completar” una relación para que tenga

una propiedad en particular se le conoce como cerradura.

En general, sea una relación sobre un conjunto A. puede o no, tener alguna propiedad P, tal como

reflexividad, simetría o transitividad. Si existe una relación C con la propiedad P conteniendo a , tal que

C es un subconjunto de cada relación con propiedad P conteniendo a . Entonces, C es llamada la

cerradura de con respecto a P. No siempre es posible encontrar una cerradura para una propiedad en

particular dada una relación . Al respecto, nos enfocaremos solamente en las propiedades de

reflexividad, simetría y transitividad.

Reflexividad

Si se tiene una relación que no es reflexiva la condición de cerradura será muy simple, basta con

agregar todos los elementos de la forma (a, a) que puedan ser formados con los elementos del conjunto A

sobre el cual se ha definido y que no se encuentren desde el inicio en . La cerradura de reflexión en

estará dada por , donde ,a a a A . Los elementos de se conocen como diagonales.

Ejemplo. Sea una relación = {(1, 2), (2, 2), (3, 1), (4, 3)}, sobre un conjunto A = {1, 2, 3, 4}. Encuentra la

cerradura reflexiva.

Solución. La cerradura reflexiva será un conjunto que contenga todos los términos de la relación , más

los términos de la forma (a, a) que no se encuentren en pero que sean parte del conjunto A. En este

caso los términos agregados para completar la cerradura se han puesto en negritas:

= {(1, 1), (1, 2), (2, 2), (3, 1), (3, 3), (4, 3), (4, 4)}.

Simetría

Antes de mostrar cómo generar una cerradura de simetría, definiremos la relación inversa.

Definición. Sea una relación de un conjunto A a un conjunto B. La relación inversa de un conjunto B a

un conjunto A, denotada por 1 , es el conjunto de pares ordenados , ,b a a b .



La relación inversa es una operación que cambia el orden de los pares ordenados en una relación dada.

Ahora bien, si se desea agregar la propiedad de simetría a una relación , es necesario crear un nuevo

conjunto que contenga todos los pares ordenados de la forma (b, a) siempre que en la relación original se

encentren los elementos de la forma (a, b). En otras palabras, la cerradura de simetría se genera con la

unión de la relación y su relación inversa, 1 .

Ejemplo. Sea una relación = {(1, 1), (1, 2), (2, 2), (3, 1), (3, 3), (4, 3), (4, 4)}, sobre un conjunto A = {1,

2, 3, 4}. Encuentra la cerradura de simetría.

Solución. Para poder obtener la cerradura de simetría requerimos agregar todos los términos de la forma

(b, a) si en la relación se encuentra el correspondiente término de la forma (a, b). De tal manera que: 1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (1, 3), (3, 3), (4, 3), (3, 4), (4, 4)}.

Transitiva

La cerradura transitiva es la más complicada de construir puesto que se tienen que agregar términos de la

forma (a, c) siempre y cuando en la relación se encuentren los términos de la forma (a, b) y (b, c). Nótese

que al agregar nuevos términos de la forma (a, c) es posible que éstos a su vez tengan que cumplir una

nueva relación de cerradura con otros términos ya existentes en , este proceso será entonces iterativo y

se detendrá hasta que no haga falta agregar nuevos términos. Al respecto, se debe de tener mucho

cuidado para no omitir ninguna relación transitiva entre todos los elementos de la cerradura.

Ejemplo. Sea una relación = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (1, 3), (3, 3), (4, 3), (3, 4), (4, 4)}, sobre

un conjunto A = {1, 2, 3, 4}. Encuentra la cerradura transitiva.

Solución. En este caso notamos que para (3, 1) y (1, 2) hace falta el término (3, 2). Para el (4, 3) y (3, 1)

faltaría el término (4, 1). Para (2, 1) y (1, 3) se genera (2, 3). Así, una relación intermedia, reordenando

términos, será:

T1 = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 3), (4, 4)}

En este caso, la introducción del término (4, 1) hace necesario introducir un nuevo término (4, 2) puesto

que (4, 1) y (1, 2) lo generarían por transitividad. Los otros términos introducidos (2, 3) y (3, 2) no generan

nuevos términos que no estén ya incluidos en la relación T1.

T2 = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3), (3, 4), (4, 4)}.

Revisando la relación de cerradura que acabamos de obtener, notamos que ya no es necesario agregar

nuevos términos pues todos los que están presentes cumplen la transitividad entre ellos.

Posiblemente se haya notado que hemos ido tomando los conjuntos generados de cada uno de los

ejemplos previos, es decir, el que se formó de la relación del inicio de la sección para que tuviera la

propiedad de reflexión , luego se utilizó para hacer la cerradura de simetría 1 y finalmente se

le impuso la cerradura de transitividad. Sin embargo, la última relación NO es una relación equivalente,



pues al introducir los términos para formar la transitividad se ha perdido la simetría, si introducimos los

términos adicionales para volver a obtener la simetría, hay que revisar que no se haya perdido la

transitividad y así sucesivamente.

Actividad 5. Elementos de la relación

Con el propósito de que elabores ejercicios sobre los elementos de la relación, realiza lo que se te pide:

1. Resuelve las operaciones de relaciones de los siguientes conjuntos. Considera las siguientes relaciones:

*( ) ( ) ( ) ( )+ *( ) ( ) ( ) ( )+

2. Resuelve los siguientes problemas:

Dada la relación = {(, !), (, ?), (!, $)} sobre el conjunto A = {, ?, !, $}. Encuentra la cerradura

reflexiva.

Dada la relación = {(, ), (, !), (, ?), (, $), (!, $)} sobre el conjunto A = {, ?, !, $}. Encuentra la

cerradura simétrica.

Dada la relación = {( , ), ( , ), ( , ), ( , ), ( , )} sobre el conjunto C ={ , , , }.

Encuentra la relación inversa 1 .

Dada la relación = {( , ), ( , ), ( , ), ( , ), ( , )} sobre el conjunto C ={ , , , }.

Encuentra la cerradura transitiva.


4MB.

4. Espera la retroalimentación de tu Facilitador(a), y toma en cuenta sus observaciones para fortalecer tu

aprendizaje.

Evidencia de aprendizaje. Relación de números de lotería



Ha llegado el momento de realizar la última Evidencia de la asignatura, con la que se pretende verificar tu

dominio sobre los temas estudiados. Para hacerlo, utilizarás los números de lotería y pondrás en práctica

los conocimientos adquiridos. A continuación se presentan los lineamientos:

1. Consigue los números de lotería que salen los días martes y domingo de la semana en que te toca

entregar la evidencia. Al obtener los números de lotería, realiza:

Relaciones: Reflexiva, irreflexiva, simétrica y asimétrica.

Un grafo correspondiente usando la relación asimétrica.

Una relación de equivalencia.

Una matriz de relación con los conjuntos.

2. Consulta la Escala de evaluación para conocer los criterios que debe cumplir tu actividad.

3. Guarda tu trabajo con la siguiente nomenclatura MDI_U3_EA_XXYZ.

4. Envía tu reporte al portafolio de evidencias y espera la retroalimentación de tu Facilitador(a), atiende sus

comentarios y de ser necesario reenvía una nueva versión de tu evidencia.

Al terminar lo anterior, ingresa al foro Preguntas de Autorreflexión, consulta las preguntas planteadas por

tu Facilitador(a) y, con base en ellas, realiza tu ejercicio de Autorreflexión para subirlo en la sección de

Autorreflexiones.


Esta unidad es de las más complejas debido a la cantidad de información que maneja, por lo que te

recomendamos utilices un lugar donde no existan distractores, ya que es muy fácil equivocarse, también

ten a la mano papel y lápiz porque son necesarios para hacer anotaciones y diagramas.

Fuentes de consulta

Johnsonbaugh, R. (1999). Matemáticas Discretas. Prentice Hall.

Mattson, H. F. Discrete Mathematics with Applications. Wiley and Sons.

Rosen, K. H. (2007). Discrete Mathematics and Its Applications. McGraw-Hill.

Education

Pd mdi