Relaciones
Páginas: 5 (1193 palabras)
Publicado: 2 de mayo de 2015
Relaciones, Matrices y Grafos
Las relaciones entre elementos de un conjunto se dan en muchos contextos. A diario manejamos relaciones como las que hay entre un empleado y su salario, entre una empresa y su número telefónico, en matemática estudiamos relaciones como las que hay entre un entero positivo y uno de sus divisores; en informática relaciones como las que hay entre un programainformático y una de las variables que emplea o la que hay entre un lenguaje de programación y una sentencia válida en ese lenguaje.
Producto cartesiano
Definición: Dados dos conjuntos A y B distintos de vacío, llamamos producto cartesiano AxB al conjunto de pares ordenados .
Cada elemento de AxB es un par ordenado, donde la primera componente pertenece al conjunto A y la segunda componente alconjunto B.
Relación
Definición: Dados dos conjuntos A y B, no vacíos, llamamos relación de A en B a cualquier subconjunto de AxB. ( lo simbolizamos con la letra R).
En nuestro tema en particular trabajaremos con relaciones definidas en un solo conjunto y además dicho conjunto va a ser finito.
Ejemplo:
Sea y
Tomando los elementos del conjunto A como vértices o nodos de ungrafo dirigido o dígrafo y a los pares ordenados de la relación como arcos se tiene:
En una relación al conjunto del cual parten las flechas se llama “Alcance” y al conjunto al cual llegan las flechas se llama “Rango”.
“Dominio”, está formado por los elementos del alcance que participan de la relación.
“Imagen”, está formado por los elementos del rango que participan de la relación.En el grafo el “Dominio” está formado por aquellos vértices de los cuales sale por lo menos un arco y la “Imagen” por los vértices a los cuales llega por lo menos un arco.
En el ejemplo: ;
Es posible representar relaciones utilizando matrices.
Sea A un conjunto finito de n elementos y R una relación definida en A. Si mantenemos fijo el orden de los elementos de A, definimos la matriz deorden nxn de la relación R:
M(R) = ( mij ) donde i, j A y :
En el ejemplo será:
Propiedades de las relaciones
Sea R una relación definida en el conjunto A, se denomina “Reflexiva” si para todo elemento a A, el par (a,a) R ó a R a. Esto indica que cualquiera sea el elemento a de A, el par (a,a) pertenece a la relación, es decir todo elemento de a está relacionado consigo mismo.
R esreflexiva ó
Ejemplo: y
Aclaración: xmod y=0 significa que el resto de dividir x por y es igual a cero
Ejemplo: (1,1) R porque 1:1 tiene como resto cero
(3,1) R porque 3:1 tiene como resto cero
(3,1) R porque 3:1 tiene como resto cero
(6,3) R porque 6:3 tiene como resto cero
Esta relación es reflexiva.
La matriz de una relación reflexiva, tiene todos loselementos de la diagonal principal iguales a uno.
El grafo de una relación reflexiva (grafo reflexivo), tiene un bucle en cada vértice. Además Dom(R) = Img(R) = A
Una relación R definida en un conjunto A se denomina “Arreflexiva” si para todo elemento , lo que significa que ningún elemento de A está relacionado consigo mismo.
R es arreflexiva ó
Ejemplo: yLa matriz de una relación arreflexiva tiene todos los elementos de la diagonal principal iguales a cero.
El grafo de una relación arreflexiva no tiene bucles en ninguno de sus vértices.
Una relación R definida en un conjunto A se denomina “Simétrica” cuando para todos los elementos , si el par entonces el par . Esto expresa que si un par ordenado pertenece a la relación, susimétrico también debe estar.
R es “Simétrica”
Ejemplo: A=;
Los elementos ubicados en forma simétrica con respecto a la diagonal principal son iguales. Es decir la matriz de una relación simétrica verifica: si o bien
En el grafo de una relación simétrica cada vez que hay un arco de vi a vj tiene que haber un arco de vj a vi. Puede haber o no un bucle en cada vértice....
Las relaciones entre elementos de un conjunto se dan en muchos contextos. A diario manejamos relaciones como las que hay entre un empleado y su salario, entre una empresa y su número telefónico, en matemática estudiamos relaciones como las que hay entre un entero positivo y uno de sus divisores; en informática relaciones como las que hay entre un programainformático y una de las variables que emplea o la que hay entre un lenguaje de programación y una sentencia válida en ese lenguaje.
Producto cartesiano
Definición: Dados dos conjuntos A y B distintos de vacío, llamamos producto cartesiano AxB al conjunto de pares ordenados .
Cada elemento de AxB es un par ordenado, donde la primera componente pertenece al conjunto A y la segunda componente alconjunto B.
Relación
Definición: Dados dos conjuntos A y B, no vacíos, llamamos relación de A en B a cualquier subconjunto de AxB. ( lo simbolizamos con la letra R).
En nuestro tema en particular trabajaremos con relaciones definidas en un solo conjunto y además dicho conjunto va a ser finito.
Ejemplo:
Sea y
Tomando los elementos del conjunto A como vértices o nodos de ungrafo dirigido o dígrafo y a los pares ordenados de la relación como arcos se tiene:
En una relación al conjunto del cual parten las flechas se llama “Alcance” y al conjunto al cual llegan las flechas se llama “Rango”.
“Dominio”, está formado por los elementos del alcance que participan de la relación.
“Imagen”, está formado por los elementos del rango que participan de la relación.En el grafo el “Dominio” está formado por aquellos vértices de los cuales sale por lo menos un arco y la “Imagen” por los vértices a los cuales llega por lo menos un arco.
En el ejemplo: ;
Es posible representar relaciones utilizando matrices.
Sea A un conjunto finito de n elementos y R una relación definida en A. Si mantenemos fijo el orden de los elementos de A, definimos la matriz deorden nxn de la relación R:
M(R) = ( mij ) donde i, j A y :
En el ejemplo será:
Propiedades de las relaciones
Sea R una relación definida en el conjunto A, se denomina “Reflexiva” si para todo elemento a A, el par (a,a) R ó a R a. Esto indica que cualquiera sea el elemento a de A, el par (a,a) pertenece a la relación, es decir todo elemento de a está relacionado consigo mismo.
R esreflexiva ó
Ejemplo: y
Aclaración: xmod y=0 significa que el resto de dividir x por y es igual a cero
Ejemplo: (1,1) R porque 1:1 tiene como resto cero
(3,1) R porque 3:1 tiene como resto cero
(3,1) R porque 3:1 tiene como resto cero
(6,3) R porque 6:3 tiene como resto cero
Esta relación es reflexiva.
La matriz de una relación reflexiva, tiene todos loselementos de la diagonal principal iguales a uno.
El grafo de una relación reflexiva (grafo reflexivo), tiene un bucle en cada vértice. Además Dom(R) = Img(R) = A
Una relación R definida en un conjunto A se denomina “Arreflexiva” si para todo elemento , lo que significa que ningún elemento de A está relacionado consigo mismo.
R es arreflexiva ó
Ejemplo: yLa matriz de una relación arreflexiva tiene todos los elementos de la diagonal principal iguales a cero.
El grafo de una relación arreflexiva no tiene bucles en ninguno de sus vértices.
Una relación R definida en un conjunto A se denomina “Simétrica” cuando para todos los elementos , si el par entonces el par . Esto expresa que si un par ordenado pertenece a la relación, susimétrico también debe estar.
R es “Simétrica”
Ejemplo: A=;
Los elementos ubicados en forma simétrica con respecto a la diagonal principal son iguales. Es decir la matriz de una relación simétrica verifica: si o bien
En el grafo de una relación simétrica cada vez que hay un arco de vi a vj tiene que haber un arco de vj a vi. Puede haber o no un bucle en cada vértice....
Leer documento completo
Regístrate para leer el documento completo.