Prezi

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in the manual

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

¡Relaciones, Funciones, Grafos y Árboles en Matemáticas Discretas!

En esta presentación veremos ejemplos y conceptos de Relaciones, Funciones, Grafos y Árboles.
by Anel Acevedo on 2 December 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of ¡Relaciones, Funciones, Grafos y Árboles en Matemáticas Discretas!

¡Relaciones, Funciones, Grafos y Árboles!
Anel Joana Acevedo Santana.
Elizabeth Bolaños Alegre.

Especialidad: Informática.
Aplicación de Matemáticas Discretas
Profesora: Adriana Álvarez Gutierrez.
Alumnas: Anel Acevedo Santana y Elizabeth Bolaños Alegre.
Grupo: 2105.
Material: Internet, Computadora.
:]
Unidad de aprendizaje 3 Desarrollo de Relaciones y Grafos en la Resolución de Problemas.

Resultado de Aprendizaje 3.1 Representa relaciones y funciones mediante la correspondencia de sus elementos y propiedades.

Actividad de Evaluación 3.1.1 Presenta soluciones de problemas con tablas de arreglos en la que aplica lo siguiente
Una relación matemática es la correspondencia entre los elementos de dos conjuntos que forman parejas ordenadas.


Todas las Relaciones pueden ser graficadas en el Plano Cartesiano.

Dados dos conjuntos A y B una relación definida de A en B es un conjunto de parejas ordenadas (par ordenado) que hacen verdadera una proposición; dicho de otro modo, una relación es cualquier subconjunto del producto cartesiano A x B
Uso de Relaciones:

.
Producto Cartesiano:
Si A = {2, 3} y B = {1, 4, 5}, encontrar tres relaciones definidas de A en B.
Solución
El producto cartesiano de A x B está conformado por las siguientes parejas o pares ordenados.
A x B = {(2, 1), (2, 4), (2, 5), (3, 1), (3, 4), (3, 5)}
Y cadzza uno de los siguientes conjuntos corresponde a relaciones definidas de A en B:



La relación R1 se puede definir como el conjunto de pares cuyo segundo elemento es 1, esto es, R1 = {(x, y) / y = 1}.

Y la relación R3 está conformada por todos los pares que cumplen con que el segundo componente es dos unidades mayor que el primer componente, dicho de otro modo, R3 = {(x, y) / y = x + 2}
Ejemplo:


La relación R2 está formada por los pares cuyo primer componente es menor que el segundo componente, R2 = {(x, y) / x < y}
Así, se puede continuar enumerando relaciones definidas a partir de A x B. Como se puede ver, la regla que define la relación se puede escribir mediante ecuaciones o desigualdades que relacionan los valores de x e y. Estas reglas son un medio conveniente para ordenar en pares los elementos de los dos conjuntos.
R1 = {(2, 1), (3, 1)}
R3 = {(2, 4), (3, 5)}
R2 = {(2, 4), (2, 5), (3, 4), (3, 5)}
Introducción:
En esta presentación hablaremos sobre el uso de las Relaciones, Funciones, Grafos y Árboles, al igual que tendremos ejemplos como conceptos para que sea mas entendible el contenido de cada una.
La clase m´as importante de relaciones es la de las relaciones binarias. Debido a que este tipo de relaciones
son las m´as frecuentes, el t´ermino “relaci´on” denota generalmente una relaci´on binaria; adoptaremos este
criterio cuando no haya confusi´on y especificaremos las que no sean binarias con t´erminos tales como
“ternaria” o “n-aria”.
Relación Binaria:
Si (a, b) R diremos que a est´a relacionado con b y lo notaremos por aRb.
Si (a, b) / R, escribiremos aR/ b y diremos que a no est´a relacionado con b.
Ejemplo 1: Sea A = {huevos, leche, ma´ız} y B = {vacas, cabras, gallinas}.
Escribir la relaci´on R de A a B def inida por: (a, b) R a es producido por b

Soluci´on
La relaci´on ser´ıa:
R = {(huevos,gallinas),(leche,vacas),(leche,cabras)}
veremos una de las formas de representar una relaci´on entre dos conjuntos f initos, como es su matriz booleana.
Matriz de Una Relación:
Definición:
Directamente de la def inici´on dada se deduce que la matriz de una relaci´on binaria es cuadrada.
Un grafo dirigido o digrafo es un par ordenado D = (A,R) donde A es un conjunto finito y R es una relaci´on binaria definida sobre A. Al conjunto A lo llamaremos conjunto de nodos o v´ertices de D. A los elementos de R los llamaremos arcos o aristas del digrafo D. Un grafo dirigido caracteriza a una relaci´on, es decir, conociendo la relaci´on se conoce el digrafo y
conociendo el digrafo, puede establecerse la relaci´on. Si GR es el grafo dirigido de una relaci´on en un conjunto f inito A, entonces el dominio y la imagen de R est´an formados por los puntos que son, respectivamente, extremo inicial y f inal de alg´un arco.
Grafo de una Relación:
En la f igura mostramos una representaci´on gr´afica del digrafo D = (A,R), siendo A el conjunto {a, b, c, d} y R = {(a, a),(a, c),(b, c)}.
Ejemplo:
Las aristas son (a, a),(a, c) y (b, c). d es un v´ertice aislado.
Los grados de entrada son: gre (a) = 1, gre(b) = 0, gre(c) = 2,gre (d) = 0 y los de salida, grs (a) = 2, grs (b) = 1, grs (c) =0, grs (d) = 0
Tipos de Relaciones:
Recorrido(Inicio, Info, Indice, Elemento)

Apuntador - Inicio

Repetir mientras Apuntador Nill

Si Elemento = Info[Apuntador] entonces:

Imprimir Info[Apuntador]

Regresa Apuntador

Apuntador - Indice[Apuntador]

Fin del ciclo

Regresar Apuntador
Ejemplo de una lista enlazada:
Ejemplo de Relaciones en las Bases de Datos:
En bases de datos, una relación o vínculo entre dos o más entidades describe algúna interacción entre las mismas. Por ejemplo, una relación entre una entidad "Empleado" y una entidad "Sector" podría ser "trabaja_en", porque el empleado trabaja en un sector determinado.
Las relaciones se describen en la estructura de la base de datos empleando un modelo de datos.
Las relaciones son muy empleadas en los modelos de bases de datos relacional y afines.
En SQL las relaciones son llamadas tablas.
Qué es una relación en base de datos?
Qué es una lista enlazada?
Una lista enlazada tiene un conjunto de nodos, los cuales almacenan 2 tipos de información: El dato que contienen y un puntero al siguiente nodo en la lista. El último nodo de la lista tiene como siguiente nodo el valor NULL. Entonces las listas enlazadas simples solo pueden ser recorridas en una dirección, apuntando al nodo siguiente, mas no a un nodo anterior.
Una base de datos es una colección de información organizada de forma que un programa de ordenador pueda seleccionar rápidamente los fragmentos de datos que necesite. Una base de datos es un sistema de archivos electrónico.
Qué es una base de datos?


En matemática, una función (f) es una relación entre un conjunto dado X (llamado dominio) y otro conjunto de elementos Y(llamado condominio) de forma que a cada elemento x del dominio le corresponde un único elemento f(x) del condominio (los que forman el recorrido, también llamado rango o ámbito).
Qué es una funcion?
Composición de Funciones


En matemáticas, se dice que una magnitud o cantidad es función de otra si el valor de la primera depende exclusivamente del valor de la segunda.


Las funciones se clasifican según su dominio y codominio en:
*Función inyectiva,(Cuando todos los elementos del codominio tienen a lo sumo uno en la imagen)
*Funcion sobreyectiva(Cuando todos los elementos del codominio tienen por lo menos uno en la imagen
*Funcion biyectiva (cuando todos los elementos del codominio tienen una y solo una en la imagen.
Además existen ciertas funciones que pueden definirsi mediante formulas matematicas que relacionan ambas variables:
Funcion afin: Y=a.X
Funcion cuadratica:Y=a.X^2 +b.x +c
Funcion exponencial :Y=a^X
Funcion inversa:F^-1= 1/x
Funcion identidad :Y=X
Tipos de Funciones:
Dada una función f entre los conjuntos A y B, diremos que es invertible si su relación inversa también es función. En tal caso, a la relación inversa de f, la notaremos f 1 y la llamaremos función inversa de f, estando definida en la forma.
Funciones Invertibles:
Aplicación de las Funciones:

Generalmente se hace uso de las funciones reales en el manejo de cifras numéricas en correspondencia con otra, debido a que se está usando subconjuntos de los números reales. Las funciones son de mucho valor y utilidad para resolver problemas de la vida diaria, problemas de finanzas.
http://cb.mty.itesm.mx/tc1003/lecturas/tc1003-102p.pdf
http://es.answers.yahoo.com/question/index?qid=20060923174242AAaf4fa
http://es.scribd.com/doc/55499353/40/Relaciones-Irre%EF%AC%82exivas
http://es.wikipedia.org/wiki/Funci%C3%B3n_matem%C3%A1tica
http://matematica.laguia2000.com/general/isomorfismo
http://mx.answers.yahoo.com/question/index?qid=20080812194739AAc62hA
http://ronnyml.wordpress.com/2009/07/04/listas-enlazadas-clase-lista-en-c/
http://www.buenastareas.com/ensayos/Tipos-De-Relaciones-Matematicas-Discretas/3121713.html
http://www.csi-csif.es/andalucia/modules/mod_ense/revista/pdf/Numero_23/SERGIO_BALLESTER_SAMPEDRO01.pdf
http://www.dma.fi.upm.es/gregorio/Discreta/PlanarDis03.PDF
http://www.fcen.uba.ar/museomat/grafos/grafos.htm
http://www.htmlpoint.com/sql/sql_05.htm
http://www.masadelante.com/faqs/base-de-datos
http://www.matediscreta.8k.com/grafos.htm
http://www.profesorenlinea.cl/matematica/Funciones_matematicas.html
http://www.profesorenlinea.cl/matematica/Relaciones_y_funciones.html
http://www.programacionfacil.com/estructura_de_datos:listas_enlazadas
http://www.slideshare.net/zamanthag/grafos-1670638
http://www.vitutor.com/fun/2/c_1.html
http://www2.uca.es/dept/matematicas/Docencia/ESI/1711003/Apuntes/Leccion9.pdf
http://www2.uca.es/matematicas/Docencia/ESI/1711003/Apuntes/Leccion6.pdf
Referencias:
Empleo de grafos
¿Qué es un grafo?
Un grafo es un conjunto de puntos en el espacio, que están conectados por un conjunto de líneas.
Partes de un grafo
Un grafo se compone de dos partes las cuales son: las vértices o nodos y las aristas o arcos, las vértices son las "esquinas" del grafo y los arcos son las líneas que unen las vértices.
Vértices
Aristas
Tipos de grafos
Multigrafo:
es un grafo con varias aristas entre dos vértices.
Pseudografo: es un grafo en el que hay aristas que tienen el mismo extremo.
Digrafo: es un grafo donde a cada arista se le indica un sentido mediante una flecha.
Multidigrafos: son combinaciones de los anteriores.
Grafo no orientados: es un grafo donde es irrelevante el sentido los arcos, al representarlo los arcos no tienen flechas.
Representación matricial de grafos
La representación matricial permite establecer si hay alguna relación entre cada vértice del grafo y los demás. Para esto se utiliza una matriz cuadrada y un arreglo bidimencional, esto significa que la representación matricial es una representación secuencial. A partir de un grafo siempre es posible definir un orden arbitrario de los vértices.
Caminos y Circuitos
Si en un grafo simple se van recorriendo sucesivamente sus aristas de modo que concurran al mismo vértice por el que se pasa de una a la otra, se está recorriendo o determinando un camino.
Cuando cierta trayectoria comienza y termina en el mismo nodo decimos que es un circuito.
El término “isomorfismo” quiere decir “igual forma”, con ello se busca destacar la idea según la cual existen similitudes y correspondencias formales entre diversos tipos de sistemas.
Dos estructuras matemáticas entre las que existe una relación de isomorfismo se llaman isomorfas.
Grafo plano:
Un grafo plano es aquel que puede ser trazado sin que ninguna arista se corte, un grafo no plano es aquel que puede ser trazado sin que sus aristas se corten.
Árboles
Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también acíclico, pero a su vez es conexo. Tal es el caso de los siguientes dos grafos en donde se puede notar que ninguno de los dos contiene repeticiones (ciclos).
Bosques de árboles.
Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos.
See the full transcript