Estructura Discretas y Grafos

REPÚBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA

EDUCACIÓN UNIVERSITARIA
CIENCIA Y TECNOLOGÍA
INSTITUTO UNIVERSITARIO POLITÉCNICO
“SANTIAGO MARIÑO”
EXTENSIÓN COL – SEDE CIUDAD OJEDA
Unidad III RELACIONES
Alumno: Juan A Díaz Pirela

C.I: 29.505.922
Codoco: 47
Materia: Estructura Discretas y Grafos
Ciudad Ojeda, Noviembre 2021

1. DEFINICIÓN DE RELACIONES
Sean A y B conjuntos finitos. Si R es un subconjunto del producto

cartesiano AxB tal que los elementos x de A cumplen la propiedad con
respecto a los elementos y de B, se dice que R es una relación definida de A
en B y se denota R:A→B al que xRy o (x,y)E R. Por lo tanto, se dice x de A
está relacionado con y de B. Al conjunto A se llama “conjunto de partida” y a
B “conjunto de llegada”.
2. PROPIEDADES DE LAS RELACIONES.
Las relaciones se pueden clasificar de acuerdo al tipo de asociación que

hay en sus elementos como: uno-a-uno 1–1, uno-a-mucho 1-M, muchos-a-
uno M-1 o muchos-a-muchos M-M. Recordemos que una relación es un
conjunto de pares ordenados.
Uno-a-muchos „1-M‟ si existen dos pares con el mismo primer elemento,
esto es existen (x,y), (x,z) distintas en la relación, con símbolos (∃ x ∈ A)(∃ y
∈ B)(∃ z ∈ B) ((x,y) ∈ R ^ (x,z) ∈ R ^ y ≠ z)
Muchos-a-muchos „M-M‟ si es muchos-a-uno y uno-a-muchos. Sea que
hay al menos dos pares con el mismo primer elemento y también hay dos
pares con el mismo segundo elemento. O sea que cumple las dos
definiciones anteriores.
Uno-a-uno „1–1′ si no es muchos-a-uno ni uno-a-muchos, o sea que no
hay dos pares con el mismo primer elemento y no hay dos pares con el
mismo segundo elemento. Esto significa que cumple las dos condiciones
siguientes (∀ x ∈ A)(∀ y ∈ B)(∀ z ∈ B)((x,y) ∈ R ^ (x,z) isin; R ⇒ y = z) (∀ x ∈
A)(∀ y ∈ B)(∀ z ∈ A)((x,y) ∈ R ^ (z,y) ∈ R ⇒ x = z)
3. CLASIFICACIÓN DE LAS RELACIONES
 Relación Binaria: Los grafos permiten visualizar cuestiones relativas a una

relación binaria, un grafo dirigido, también conocido como dígrafo, es un
par ordenado D = (A, R) donde A es un conjunto finito y R es una relación
binaria la cual es definida sobre A, y al conjunto de este, es decir, A,
recibirá el nombre de conjunto de vértices o nodos de D; y los elementos
de R recibirán el nombre de aristas o arcos del dígrafo D.
 Relación Inversa: Si R es una relación inversa, es decir, R -1, con la
siguiente propiedad:
R-1=(x, y) tal que y, x pertenecen a los reales
 Relaciones Reflexivas e Irreflexivas: La relación reflexiva se da
cuando cada elemento está relacionado consigo mismo y se escribe
como a R a para todo a que pertenece al conjunto. Sea R una
relación binaria definida en un conjunto A por lo que R es una relación
reflexiva si aRa para cada a ϵ A.
 Relaciones simétricas y antisimétricas: En una relación simétrica para
todo par de elementos, sucede que el elemento a está relacionado con
el elemento b, por lo que el elemento b está relacionado con el
elemento a, es decir, existe una relación de tipo simétrica si aRb y bRa
son a,b ϵ A.
 Relaciones Transitivas: Se llama relación transitiva la que verifica si un
elemento x está relacionado con el elemento y, además que el
elemento y está relacionado con el elemento z, por lo que el elemento
x está relacionado con el elemento z. entonces xRy aunado yRz
implica xRz para x,y,z ϵ A.
 Relaciones de Equivalencia: permiten agrupar los elementos con
características en común en los conjuntos. es la que cumple sobre un
conjunto relaciones de tipo reflexiva, simétrica y transitiva.
4. RELACIÓN DE ORDEN PARCIAL (EJEMPLOS).
Un orden parcial es una relación R en un conjunto A si R es reflexiva,

antisimétrica y transitiva. El conjunto A junto con el orden parcial R se llama
conjunto parcialmente ordenado y se expresa (A, R).
Ejemplo 1: Sea "E" la relación de inclusión en P(A). Esta relación es un
orden parcial en P(A). Por lo tanto es un conjunto parcialmente ordenado.
5. RELACIÓN DE EQUIVALENCIA (EJEMPLOS).
Una partición de un conjunto es una colección de subconjuntos disjuntos

no vacíos de que tienen a como su unión, en otras palabras, la colección de
subconjuntos Ai, i I (donde I es un índice del conjunto) forma una partición si
y solo sí.
Ejemplo:
Sea ={a, b, c, d, … , z} y sean

W1 = {a, e, i, o, u}
W2 = {w, c}
W3 = {b, f, g, h, j, k, l}
W4 = {m, n, ñ, p, q}
W5 = {r, s, t, v}
W6 = {x, y}
W7 = {d, z}
= W1 W2 W3 W4 W5 W6 W7 o bien
={{a, e, i, o, u}, {w, c}, {b, f, g, h, j, k, l}, {m, n, ñ, p, q}, {r, s, t, v}, {x, y}, {d, z}}
6. GRAFO DIRIGIDO (EJEMPLOS).
G consta de un conjunto V de vértices y un conjunto E de lados, tal que e

E está asociado a un par ordenado único de vértices v y w y se escribe e =
(v, w).
Ejemplo:
Este grafo G consta de un conjunto V de vértices

V = {S, T, U, V, W, X, Y, Z}
y el conjunto de lados
E = {e1, e2, e3, .... , e11 }.
El lado e1 está asociado con el par no ordenado {T, U}, el lado e10 está
asociado al par no ordenado {S, X}. El lado e1 se denota por (U, T) o bien (T,
U). El lado e4 es incidente en los vértices Y y Z por lo que Y y Z son vértices
adyacentes.
7. TRAYECTORIA DE GRAFOS DIRIGIDOS.
 Una trayectoria en un grafo es una secuencia de aristas que permiten

viajar de un vértice a otro de manera continua.
 La longitud de una trayectoria es su número de aristas.
 A una trayectoria de k aristas se le llama k trayectoria.
 A una trayectoria que comienza y termina en el mismo vértice se le llama
circuito.
 A una trayectoria que no incluye la misma arista más de una vez se le
llama simple.
REALIZAR UN MAPA CONCEPTUAL DEFINIENDO RELACIONES. ESTE MAPA DEBE SER LO MÁS
EXPLICATIVO POSIBLE A FIN DE DEJAR CLARO EL CONCEPTO.
Resolver los siguientes ejercicios

Estructura Discretas y Grafos

Cargado por

Copyright:

Formatos disponibles

Estructura Discretas y Grafos

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Estructura Discretas y Grafos

Cargado por

Copyright:

Formatos disponibles

REPÚBLICA BOLIVARIANA DE VENEZUELA

MINISTERIO DEL PODER POPULAR PARA LA

Unidad III RELACIONES

Alumno: Juan A Díaz Pirela

Ciudad Ojeda, Noviembre 2021

Sean A y B conjuntos finitos. Si R es un subconjunto del producto

2. PROPIEDADES DE LAS RELACIONES.

Las relaciones se pueden clasificar de acuerdo al tipo de asociación que

3. CLASIFICACIÓN DE LAS RELACIONES

 Relación Binaria: Los grafos permiten visualizar cuestiones relativas a una

4. RELACIÓN DE ORDEN PARCIAL (EJEMPLOS).

Un orden parcial es una relación R en un conjunto A si R es reflexiva,

5. RELACIÓN DE EQUIVALENCIA (EJEMPLOS).

Una partición de un conjunto es una colección de subconjuntos disjuntos

Sea ={a, b, c, d, … , z} y sean

6. GRAFO DIRIGIDO (EJEMPLOS).

G consta de un conjunto V de vértices y un conjunto E de lados, tal que e

Este grafo G consta de un conjunto V de vértices

7. TRAYECTORIA DE GRAFOS DIRIGIDOS.

 Una trayectoria en un grafo es una secuencia de aristas que permiten

También podría gustarte