Trabajo De Grafos



República Bolivariana de Venezuela
Ministerio del poder Popular para la Educación
Instituto Universitario Politécnico Santiago Mariño





Profesora Alumno
Marivy Vivas Giuseppe Raffa
Sección G de Ing.de Sistemas C.I.: 809884

Maturín, 20-10-15
Introducción
En la realidad que nos circunda existen relaciones entre elementos, entre conjuntos y entre elementos y conjuntos. Existen relaciones de parentesco, de amistad, de paisanaje, etc., entre personas; relaciones diplomáticas, económicas, etc., entre países; relaciones deparalelismo o de perpendicularidad entre rectas de un plano; relaciones de inclusión entre conjuntos; relaciones como “mayor que” o “menor o igual que” entre números, etc. La matemática intenta, hacerse eco de tales sucesos, y mediante un proceso de abstracción, expresarlas y estudiarlas científicamente.

Relaciones
Si tenemos n conjuntos, Ai con i = 1, . . ., n, se dice que un subconjunto R ⊆ A1 ×· · · × An es una relación sobre A1, A2, . . ., An. Nos centraremos en el caso n = 2. Dados dos conjuntos A y B, una relación binaria de A en B es un subconjunto cualquiera R del producto cartesiano A × B. i el par ordenado (a, b) pertenece a R, se dirá que a está relacionado con b, y se denotará a R b. Dado un conjunto A, se llama relación en A a cualquier subconjunto R de A × A. Una relación enA es, por tanto, una relación en la que coinciden el conjunto inicial y el final.

Propiedades de las relaciones
Reflexiva: 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)} Otro ejemplo: R2 = {(1, 1), (2, 2), (3 ,3), (4, 4), (2, 3), (1, 4)}
Antirreflexiva o 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)}


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. Dicho de otra forma: ∀ x, y ∈ A se cumple quesi (x, y) ∈ R entonces (y, x) ∈ R Ejemplo: R = {(1,1), (1,3), (2,2), (2,4), (3,1), (4,2), (4,4)}
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)}
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) ∉ REjemplo: R = {(1,2), (1,3), (2,4), (4,3)}
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 =...