REALIZADO POR:

Jacqueline Vargas RodríguezJimmy Vargas Jimenez

RELACIÓN ENTRE

CONJUNTOS

Un grafo consta de un conjunto de nodos(o vértices) y un conjunto de arcos (o aristas). Cada arco de un grafo se especifica mediante un par de nodos.

GRAFOS

Mapas conceptuales - Sociograma de una red social - Isómeros - Circuito eléctrico - Plano de autopistas

Es un punto de intersección o unión de varios elementos que confluyen en el mismo lugar.

En redes de computadoras cada una de las máquinas es un nodo, y si la red es Internet, cada servidor constituye también un nodo. El concepto de red puede definirse como "conjunto de nodos interconectados. Un nodo es el punto en el que una curva se intersecta a sí misma. Lo que un nodo es concretamente, depende del tipo de redes a que nos refiramos".

En estructuras de datos dinámicas un nodo es un registro que contiene un dato de interés y al menos un puntero para referenciar (apuntar) a otro nodo. Si la estructura tiene sólo un puntero, la única estructura que se puede construir con él es una lista, si el nodo tiene más de un puntero ya se pueden construir estructuras más complejas como árboles o grafos.

Que es un nodo?

Si los pares de nodos que forman los arcos son ordenados, es decir, un nodo puede ser apuntado por otros nodos, se representa con u v

El conjunto de vértices V = {C,D,E,F,H} yel conjunto de arcos A = {(C,D),(D,F),(E,H),(H,E),(E,C)} forman el grafo dirigido G = {V, A}.

Nodo o Grafo dirigido

Nodo o Grafo no dirigido o aislado

Un grafo no dirigido es el que tiene los arcos formados por pares de nodos no ordenados, un nodo está relacionado con otro nodo, se representa con u v

El conjunto de V= {1,4,5,7,9} y el conjunto de arcos A={(1,4),(5,1),(7,9),(7,5),

(4,9), (4,1),(1,5),(9,7),(5,7),(9,4)} forman el grafo no dirigido G = {V, A}.

Para ejemplificar las propiedades de las relaciones utilizaremos el conjunto A={1,2,3,4}.

Propiedad reflexiva (o idéntica):

Una relación R sobre un conjunto A es reflexiva si para todo x ∈ A entonces (x,x) ∈ R. En otras palabras una relación es reflexiva si todo elemento del conjunto sobre el que está definida, está relacionado consigo mismo.∀ x ∈ A se cumple que (x,x) ∈ R.

Ejemplo: R={(1,1),(2,2),(3,3),(4,4)}

Propiedades

Conjunto A={1,2,3,4}.

Propiedad antirreflexiva, también llamada irreflexiva:

Una relación R sobre un conjunto A es antirreflexiva si para todo x ∈ A se cumple que (x,x) ∉ R, es decir que ∀ x ∈ A se cumple que x no está relacionado consigo mismo.

Ejemplo: R= {(1,2), (2,1), (1,3), (1,4), (2,3), (2,4), (3,4)}

Propiedades

Conjunto A={1,2,3,4}.

Propiedad simétrica:

Una relación R sobre un conjunto A es simétrica si para todo x ∈ A, y ∈ A, si (x,y) ∈ R entonces (y,x) ∈ R.Dicho de otra forma: ∀ x,y ∈ A se cumple que si (x,y) ∈ R entonces (y,x) ∈ R.

Ejemplo: R= {(1,1), (1,3), (2,2), (2,4), (3,1), (4,2), (4,4)}

Propiedades

Conjunto A={1,2,3,4}.

Propiedad antisimétrica:Una relación R sobre un conjunto A es antisimétrica si para todo x ∈ A, y ∈ A, si x R y e y R x entonces x=y.De nuevo: ∀ x,y ∈ A se cumple que si (x,y), (y,x) ∈ R entonces x=y.

Ejemplo: R={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4),(1,1),(2,2),(3,3),(4,4)}

Propiedades

Conjunto A={1,2,3,4}.

Propiedad asimétrica:

Una relación R sobre un conjunto A es asimétrica si para todo x ∈ A, y ∈ A, si (x,y) ∈ R entonces (y,x) ∉ R.Dicho de otra forma: ∀ x,y ∈ A se cumple que si (x,y) ∈ R entonces (y,x) ∉ R

Ejemplo: R = {(1,2), (1,3), (2,4), (4,3)}

Los pares (n,n) no pueden estar, por definición. Las relaciones asimétricas son antirreflexivas.

Propiedades

Conjunto A={1,2,3,4}.

Propiedad transitiva:Una relación R sobre un conjunto A es transitiva si para todo x ∈ A, y∈ A, z∈ A si (x,y) ∈ R y (y,z) ∈ R entonces (x,z) ∈ R.∀ x,y,z ∈ A se cumple que si (x,y), (y,z) ∈ R entonces (x,z) ∈ R.

Ejemplo: R={(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)}

Propiedades

Está basado en una idea intuitiva, la representación de relaciones del tipo: ciudades en una misma región, alumnos de la misma clase, instrucciones dentro del mismo bloque de código, entre otros.

Una partición de un conjunto C es una colección s de subconjuntos no vacíos de C tal que todo elemento en C pertenece exactamente a un miembro de s.

Relación de Equivalencia y Particiones

Dada una relación de equivalencia R sobre un conjunto A, llamaremos clase de equivalencia del elemento “a” de A, y lo indicaremos [a]R ó Ca , al subconjunto de A integrado por los elementos relacionados a dicho elemento. O sea: [a]R ={x ∈ A / x R a}

Propiedades:

1. Las clases de equivalencia no son vacías, ya que por lo menos la integra el elemento que le da nombre.

2. [a]R =[b]R ⇔ a R b, es decir que dos clases de equivalencia son iguales si (a,b) ∈ R.

3. [a]R ≠ [b]R ⇔ [a]R ∩[b]R=∅

Dado un conjunto A, una partición de A es una colección de subconjuntos de A que cumplen: 1) los subconjuntos no son vacíos,2) los subconjuntos son disjuntos dos a dos,3) la unión de todos los subconjuntos son el conjunto A, o sea:

Veamos primero un ejemplo: A={1,2,3,4}. Una partición de A es B={2} C={1,3,4} 1. B≠∅, C≠∅2. B ∩ C=∅3. B∪C=A

Una partición de un conjunto S es una colección de subconjuntos disjuntos no vacios de S que tienen a S como su unión, sea S una partición sobre un conjunto X. Decimos que x R y si para algún A en S x, y   A.

Ejemplo:

Sea X= {1,2,3,4,5,6} y sea S={{1,3,5},{2,6},{4}} una partición de X.

La relación R definida por el teorema anterior es:R={(1,1), (1,3), (1,5), (3,1), (3,3), (3,5), (5,1), (5,3), (5,5), (2,2), (2,6), (6,2), (6,6), (4,4)}

Una relación R que es reflexiva, simétrica y transitiva, sobre un conjunto X, se conoce como una relación de equivalencia sobre X. La cual, por la definición anterior es una relación de equivalencia. Si se representa por medio de digrafos tenemos que: