3.4. GRAFOS Y DIGRAFOS
87
6. Sea R una relación sobre un conjunto A. Muestre que R es reflexiva si y sólo si
{(a, a) : a ∈ A} ⊆ R.
7. En los siguientes ejercicios daremos una “demostración” que debe ser corregida. Justifique su respuesta.
a) Afirmación: Si la relación R es simétrica y transitiva, entonces también es reflexiva.
“Demostración”: Ya que R es simétrica, tenemos que si (x, y) ∈ R, entonces
(y, x) ∈ R. Luego como (x, y), (y, x) ∈ R y R es transitiva, entonces (x, x) ∈ R y
por lo tanto R es reflexiva.
2
b) Afirmación: Si las relaciones R y S son transitivas, entonces la relación R ∩ S
es transitiva.
“Demostración”: Supongamos que (x, y) ∈ R ∩ S y (y, z) ∈ R ∩ S. Entonces
(x, y) ∈ R y (y, z) ∈ S. Luego (x, z) ∈ R ∩ S.
2
c) Afirmación: Si las relaciones R y S son simétricas, entonces la relación R ∩ S es
simétrica.
“Demostración”: Sea
R = {(1, 2), (2, 1), (1, 1), (3, 2), (2, 3), (2, 2)}
y
S = {(2, 3), (3, 2), (2, 2), (3, 4), (4, 3)}.
Entonces R ∩ S = {(2, 3), (3, 2), (2, 2)}. Tenemos que R, S y R ∩ S son simétricas.
2
3.4.
Grafos y Digrafos
Las relaciones binarias sobre un conjunto pueden ser representadas gráficamente a través
de unos diagramas que se conocen como digrafos. Veamos un ejemplo: consideremos la
relación R sobre A = {1, 2, 3, 4} dada por
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.
Ya vimos que R corresponde a la relación de divisibilidad sobre A. Para establecer el digrafo
de esta relación, marcamos primero puntos o vértices que representan los elementos de A,
en este caso debemos dibujar 4 puntos. A continuación, si un par (x, y) está en la relación,
se traza una flecha (llamada arco dirigido) desde x hasta y. En nuestro caso, tenemos el
siguiente digrafo
4
1
2
3