Grafo de una relación

    Como se sabe, una relación binaria es un criterio que, aplicado a un conjunto, permite saber si dos elementos cualesquiera del mismo están o no asociados entre sí, mediante esa relación. Generalmente, el símbolo de relación se indica por R y el de no relación por /R, por lo que:

    a R b

    significa que los elementos a y bestán relacionados, mientras que:

    a /R b

    indica que los elementos a y bno están relacionados.

    Por ejemplo, si se considera el conjunto: {España, Francia, Inglaterra, Madrid, París, Londres} y se establece en él la relación “ser capital de”, lo que significa que dos elementos están relacionados cuando uno es la capital del otro, se tendrá que:

    Madrid R España

    París R Francia

    Londres R Inglaterra

    Madrid /R Francia

    España /R Inglaterra

    El grafo de una relación es una representación gráfica de las relaciones binarias, que sirve para visualizar los elementos que están asociados entre sí y los que no lo están. Para ello, los elementos relacionados se unen mediante una flecha. Esta representación se llama sagital. Por ejemplo, en el caso anterior, el grafo sería:

    España

    Madrid

    Francia

    París

    Londres

    Inglaterra


    Las relaciones binarias definidas en un conjunto C pueden tener las siguientes propiedades:

    1. Reflexiva. Cuando , se verifica que a R a. Por ejemplo, en un conjunto de personas, la relación “tener la misma estatura que”, posee esta propiedad, ya que toda persona tiene la misma estatura que él mismo. Cuando existe esta propiedad, en el grafo correspondiente, todo elemento recibe una flecha en forma de bucle que nace y muere en el mismo elemento.

    a

    1. Antirreflexiva. Cuando , se verifica que a /R a. Por ejemplo, en un conjunto de personas, la relación “tener mayor estatura que” tiene la propiedad antirreflexiva, ya que nadie tiene mayor estatura que él mismo. Gráficamente se observa la existencia de esta propiedad porque en el correspondiente grafo ningún elemento posee bucle alguno.

    2. No reflexiva. Cuando no siempre un elemento está relacionado consigo mismo. Es decir, cuando:

    a R a

    es cierto unas veces, pero no otras. Por ejemplo, si en un conjunto de personas se establece que “dos personas están relacionadas cuando el color de la chaqueta de la primera coincida con el color del pantalón de la segunda”, esta relación es no reflexiva, ya que un elemento sólo estará relacionado consigo mismo cuando el color de su chaqueta sea igual que el de su pantalón, lo cual, en general, no sucederá.

    1. Simétrica. Cuando , a R b b R a. Por ejemplo, la relación, en el conjunto de las rectas del plano, “ser paralelas” posee esta propiedad, ya que si a es paralela a b, entonces b es paralela a a. Si esta propiedad existe, en el correspondiente grafo, siempre que dos elementos estén relacionados, habrá entre ellos dos flechas en sentidos contrarios.

    a b

    1. Antisimétrica. Cuando , a R b a /R b. Por ejemplo, en el conjunto C = {1, 2, 3, 4}, la relación “ser menor que” posee la propiedad antisimétrica, ya que si a es menor que b, nunca podrá ser bmenor que a. Gráficamente, esta propiedad se pone de relieve cuando entre dos elementos relacionados hay una flecha de ida, pero no de vuelta. El ejemplo anterior de las naciones y sus capitales es un caso de esta propiedad.

    2. Transitiva. Cuando , el hecho de que :

    a R b

    a R c

    a R c

    Por ejemplo, en un conjunto de personas, la relación “ser hermano de” tiene esta propiedad, ya que si a es hermano de b y éste, a su vez, lo es de c, entonces a y c deben ser hermanos. En el correspondiente grafo, esto se verá por la siguiente estructura:

    a b

    c

    1. No transitiva. Cuando de:

    a R b y b R c

    no se deduce que a y c estén relacionados.

    Las relaciones binarias que cumplan las propiedades reflexiva, simétrica y transitiva se llaman de equivalencia. En ellas, cabe distinguir su relación complementaria, la cual se denomina relación de diferencia. Por ejemplo, la relación de diferencia de la relación de equivalencia “tener la misma estatura que” sería “tener distinta estatura que”.

    Las relaciones binarias que poseen las propiedades antirreflexiva, antisimétrica y transitiva se llaman de orden estricto. Las relaciones binarias que presentan las propiedades reflexiva, antisimétrica y transitiva se denominan de orden total.

    Finalmente, las que poseyendo las propiedades anteriores no relacionan entre sí a todos los elementos reciben el nombre de relaciones de orden parcial. Por ejemplo, en el conjunto {2, 3, 6, 9, 24}, la relación “dividir exactamente a” tiene las propiedades reflexiva, antisimétrica y transitiva, pero no relaciona a todos los elementos entre sí, ya que, por ejemplo:

    1. R 6

    pero:

    2 /R 9