Relaciones grafos digrafos

RELACIONES

Sean A y B conjuntos no vacíos. Una relación ℜ de A a B es un subconjunto de A x B.
Notación:
 Si (a, b) ∈ a ℜ, entonces lo denotamos a R b
 Si (a, b) ∉ a ℜ, entonces lo denotamos a ℝb
Si A es igual a B, se dice que ℜ es una relación sobre A.
Ejemplo: Sea A = B = {1, 2, 3, 6, 7} a R b si y sólo si a + b < 9.
Entonces:
ℜ = {(1, 1), (1,2), (1,3), (1,6), (1,7), (2,1), (2,2),(2,3),(2,6), (3,1), (3,2), (3,3), (6,1), (7,1)}
Dominio de ℜ = {1, 2, 3, 6, 7}
Rango de ℜ = {1, 2, 3, 6, 7}
Dada una relación ℜ existen varias formas de representarla usando:
 Sistema cartesiano
Representación sagitaria
 Matriz booleana de adyacencia
 Dígrafo
 Diagrama Cartesiano:
Sea A = B = {1, 2, 3, 6, 7} a R b si y sólo si a + b < 9.

ℜ = {(1, 1), (1,2), (1,3),
(1,6), (1,7), (2,1), (2,2),(2,3), (2,6), (3,1), (3,2),
(3,3), (6,1), (7,1)}
Representación Sagitaria:
Sea A = B = {1, 2, 3, 6, 7} a R b si y sólo si
a + b < 9

ℜ = {(1, 1), (1,2), (1,3),
(1,6), (1,7), (2,1), (2,2),
(2,3),(2,6), (3,1), (3,2),
(3,3), (6,1), (7,1)}

Matriz de una relación:
Dados dos conjuntos finitos A = {a1, a2,..., am} y B = {b1, b2,..., bn} que contienen m y n elementos respectivamente y R una relaciónde A a B, la matriz booleana de adyacencia de la relación, MR, se define por:

Para el ejemplo: A = B = {1, 2, 3, 6, 7} y
ℜ = {(1, 1), (1, 2), (1, 3), (1,6), (1,7), (2,1),
(2,2), (2,3), (2,6),(3,1), (3,2), (3,3), (6,1),
(7,1)}

Dígrafo (gráfica dirigida)

Si A es un conjunto finito y R es una relación sobre A. R también puede representarse gráficamente a través de vértices y arcos, de lasiguiente manera:
 Dibuje un vértice para cada elemento de A y márquelo con su valor correspondiente.
 Si ai R aj trace un arco del vértice ai al vértice aj.

Dígrafo: Para el ejemplo: A = {1, 2, 3, 6, 7}y
ℜ = {(1, 1), (1,2), (1,3), (1,6), (1,7), (2,1), (2,2),
(2,3), (2,6), (3,1), (3,2), (3,3), (6,1), (7,1)}

• Grado Interno:
Número de arcos que terminan en el vértice.

• Grado Externo:
Número de...