Loading presentation...

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 our knowledge base article

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

Copy of Relaciones y grafos, la solución de problemas

Correspondencia de sus elementos y propiedades de Relaciones, Grafos, junto con la aplicación de árboles.
by

Ana Frederico

on 15 January 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Copy of Relaciones y grafos, la solución de problemas

1) Elementos de una relación
Definición de relación

Producto cartesiano

Relación binaria

Matriz de una relación

Grafo de una relacion 1. Producto de más de dos conjuntos
Si se tienen n conjuntos A1, A2, . . . , An, entonces definimos
A1 × A2 × A3 × • • • × An = (. . .((A1 × A2) × A3) × • • •) × An.
Producto cartesiano generalizado Definición de relación Producto cartesiano 2. Sea I un conjunto de índices, de modo que para cada i I existe un único Ai
.
Definimos Y
iI
Ai
como el conjunto de todas las funciones
f : I
[
iI
Ai
tales que, para cada i I, se tenga f(i) Ai
.
O sea, un elemento de
Y
iI
Ai
le asigna a cada elemento i I un elemento f(i).
Ejercicio. Explique por que A × B y (A × B) × C son casos particulares de esta definicion. 3. Así como es posible generalizar la unión y la intersección, también podemos generalizar la
idea de producto cartesiano. Una relaci´on (binaria) de A en B es un subconjunto de A × B.
Una relaci´on (binaria) en A es un subconjunto de A × A. Relación binaria Notación. en vez de escribir (x, y) R, usualmente escribiremos xRy. En vez de escribir (x, y) /
R, escribiremos x R y Propiedades de las relaciones binarias Sea R ⊆ A × A. Dependiendo de las propiedades que satisfaga R, diremos que esta es:
Refleja si ∀x ∈ A(xRx).
Irrefleja si ∀x ∈ A(xR x 6 ).
Simétrica si ∀x, y ∈ A(xRy → yRx).
Antisimetrica si ∀x, y ∈ A((xRy ∧ yRx) → x = y).
Transitiva si ∀x, y, z ∈ A((xRy ∧ yRz) → xRz). Dados dos conjuntos finitos, no vac´ıos,
A = {a1, a2, . . . , am} y B = {b1, b2, . . . , bn}
y una relacion R cualquiera de A a B, llamaremos matriz de R a la matriz booleana siguiente:
MR =(rij): rij= 1, si (ai, bj ) R
0, si (ai, bj ) / R
donde i = 1, 2, . . . . . . , m; j = 1, 2, . . . . . . , n Matriz de una relación Tipos de relaciones Una relación cuando todo elemento de un conjunto A está relacionado consigo mismo, esto es, cuando se cumple que ara para todo elemento de A. Una característica de este tipo de relación es que su matriz correspondiente contiene unos en toda su diagonal principal y los elementos restantes de la matriz pueden ser unos o ceros. Reflexiva Uso de relaciones Irreflexiva Se dice un relación es irreflexiva cuando ningún elemento del conjunto A esta relación consigo mismo ((a, a) є R). En este caso la matriz de la relación deberá contener únicamente ceros en la diagonal. Si la diagonal de la matriz tiene ceros y unos, la relación correspondiente no es reflexiva ni irreflexiva. Simétrica Es simétrica cuando se da que si un elemento está relacionado con otro mediante R, entonces ese otro también está relacionado con el primero.
Es decir, que R cumple con la propiedad de simetría.
La aplicación de cualquier relación R sobre un conjunto A, se representa con el par ordenado (A, R). Asimétrica Cuando una relación es lo opuesto a una simétrica, es decir, cuando se da que si un elemento está relacionado con otro mediante R, entonces ese otro no está relacionado con el primero, entonces decimos que es asimétrica.
En este caso, decimos que R cumple con la propiedad de asimetría Antisimétrica Una relación binaria sobre un conjunto es antisimétrica cuando se da que si dos elementos de se relacionan entre sí mediante , entonces estos elementos son iguales.
Es decir, que cumple con la propiedad de antisimetría.
La aplicación de cualquier relación sobre un conjunto, se representa con el par ordenado. Transitiva Una relación binaria sobre un conjunto es transitiva cuando se cumple: siempre que un elemento se relaciona con otro y éste último con un tercero, entonces el primero se relaciona con el tercero.
Esto es:
Dado el conjunto A y una relación R, esta relación es transitiva si: a R b y b R c se cumple a R c Lista enlazada Relaciones en las
bases de datos Una lista enlazada es una colección lineal de elementos donde el orden de los mismos se establece mediante punteros. La idea básica es que cada componente de la lista incluya un puntero que indique donde puede encontrarse el siguiente componente por lo que el orden relativo de estos puede ser fácilmente alterado modificando los punteros lo que permite, a su vez, añadir o suprimir elementos de la lista. Lista enlazada Por tanto, una lista enlazada no está limitada a contener un número máximo de componentes; puede expandir o contraer su tamaño mientras se ejecuta el programa. Es un conjunto de datos pertenecientes a un mismo contexto y almacenados sistemáticamente para su posterior uso. En este sentido, una biblioteca puede considerarse una base de datos compuesta en su mayoría por documentos y textos impresos en papel e indexados para su consulta. Base de datos Actualmente, y debido al desarrollo tecnológico de campos como la informática y la electrónica, la mayoría de las bases de datos están en formato digital (electrónico), que ofrece un amplio rango de soluciones al problema de almacenar 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. Relación en base de datos Aplicación de matematicas
discretas. Profesora: Adriana Álvarez Gutierrez Alumnos: Prisciliano Lopez y Julio Solorio Quintana Especialidad: Informatica Material: Computadoras e internet Una relación es la correspondencia que se establece en un conjunto o en varios conjuntos. A. Empleo de Grafos Definición de grafo
Partes de un grafo.
Tipos de grafos.
Representación matricial.
Caminos y circuitos.
Isomorfismo.
Grafos planos.
Ejemplos ¿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 puntas 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. Isomorfismo 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. ¿Que es una función? 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 codominio) de forma que a cada elemento x del dominio le corresponde un único elemento f(x) del codominio (los que forman el recorrido, también llamado rango o ámbito). Composición de una función La composición es una operación entre funciones que se establece de lasiguiente manera:
Dadas dos funciones f y g , se define como la composición de la función f con la función g , a la función denotada f o g Las funciones se clasifican segun su dominio y codominio en:
-Funcion 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. Tipos de funciones Funciones Invertibles 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. 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 muy utilizadas en economía, estadística, ingeniería, medicina, etc. http://www.dcb.fi-c.unam.mx/CoordinacionesAcademicas/Matematicas/CalculoDiferencial/Composicion.pdf
http://www.es.answers.yahoo.com/question/index?qid=20081030080018AAPWSgN
http://www.fcen.uba.ar/museomat/grafos/grafos.htm
http://www.matediscreta.8k.com/grafos.htm
http://www.matematica.laguia2000.com/general/isomorfismo
http://www.monografias.com/trabajos16/grafos/grafos.shtml#ARBOL
http://www.profesorenlinea.cl/matematica/Funciones_matematicas.html
http://www.profesorenlinea.cl/matematica/Funciones_tipos.html
http://www.profesorenlinea.cl/matematica/Relaciones_y_funciones.html
http://www.slideshare.net/zamanthag/grafos-1670638
http://www.vitutor.com/fun/2/c_1.html
www2.uca.es/dept/matematicas/Docencia/ESI/1711003/Apuntes/Leccion9.pdf
http://www.xcocumaxpoli.blogspot.mx/
Referencias:
Full transcript