Relaciones Binarias y Grafos: Definición, Propiedades y Aplicaciones

Relación binaria

Sea A un conjunto no vacío. Una relación R binaria definida en A es cualquier subconjunto del producto cartesiano AxA. Simbólicamente: R ⊆ AxA

Digrafo (o Grafo Dirigido)

Si A es un conjunto finito y R una relación definida en A, llamamos DIGRAFO (o GRAFO DIRIGIDO) de R a la representación gráfica que se realiza siguiendo los siguientes pasos:

• Se representa con un círculo o un punto a cada elemento de A.
• Se dibuja una flecha del vértice ai al vértice aj si y solo si (ai,aj)∈R

Sea R definida en A. Llamamos dominio de R al conjunto de las primeras componentes de los pares ordenados de R y rango de R al conjunto de las segundas componentes. Sea x un elemento de A. Se define conjunto relativo a “x”, R(x), al conjunto de elementos “y” relacionados con “x”. Simbólicamente: R(x) = { y / xRy }

Grado externo de a: Cantidad de nodos b ∈ A tal que (a, b)∈R. Lo representaremos como ge(a)

Grado interno de a: Cantidad de nodos b ∈ A tal que (b, a)∈R. Lo representaremos como gi(a)

Propiedades

Propiedad reflexiva: En el digrafo, R es reflexiva si y solo si todos los elementos tienen lazos. En la matriz MR, R es reflexiva si y solo si mii=1 i

Propiedad de simetría: En el digrafo, R es simétrica si y solo si cada vez que una arista (x,y) aparezca en él entonces también la arista (y,x) debe estar presente. En la matriz MR, R es simétrica si y solo si mij=mji i,j

Propiedad transitiva: En el digrafo, R es transitiva si y solo si cumple que, si existen las aristas (x,y) e (y,z), entonces también existe (x,z)

Conjunto cociente

Llamamos Conjunto Cociente al conjunto formado por todas las clases de equivalencia distintas generadas por una Relación de Equivalencia R en un conjunto A. Se denota A/R. Es una simplificación del grafo dirigido de una relación de orden donde se dan por sobreentendidos los lazos, las aristas que son consecuencias de la transitividad y la orientación de las flechas. Estas consideraciones se pueden hacer ya que el grafo no posee ciclos de longitud mayor que 1. El grafo originado es más simple y recibe el nombre de Diagrama de Hasse.

Grafo

Grado de un vértice: número de aristas que inciden en él.

Bucle o lazo: arista de un vértice a sí mismo. Contribuye en dos unidades al grado del vértice.

Vértice aislado: es un vértice de grado 0.

Aristas paralelas: Dos aristas que inciden en los mismos vértices.

Grafo Simple: Aquel que no tiene lazos ni aristas paralelas.

Un circuito simple o ciclo es aquel circuito que no repite vértices.

Trayectorias y Ciclos

Una trayectoria o camino en G es una sucesión finita de vértices donde cada uno es adyacente al siguiente y donde no se repiten aristas. La longitud de un camino es el número de aristas que hay en él. En caso de un grafo con aristas paralelas, la secuencia debe indicar las aristas e inevitablemente las aristas deben estar etiquetadas. Un circuito es un camino que comienza y termina en el mismo vértice. Un camino simple es el camino donde todos los vértices son distintos.

Dada una gráfica G, se dice que posee una trayectoria de Euler si posee una trayectoria que incluye todas las aristas sólo una vez.

Dada una gráfica G, se dice que posee un Circuito de Euler si posee una trayectoria de Euler que es a la vez un circuito, o sea, comienza y termina en el mismo vértice. Una trayectoria Hamiltoniana para un grafo G es aquella que contiene todos los vértices de G una vez. Un ciclo Hamiltoniano es una trayectoria de Hamilton que comienza y termina en el mismo vértice.

Árboles

Ninguna arista entra a vo pero pueden salir varias, que se trazan hacia abajo. Los vértices terminales de las aristas que comienzan en vo son los vértices del nivel 1. Cada vértice del nivel 1 no tienen otras aristas que entren en él, pero cada uno de estos vértices pueden tener varias aristas que salen de él. Se trazan las aristas que salen del nivel 1 hacia abajo y terminan en vértices que estarán en el nivel 2. Y así sucesivamente con cada nivel. De este modo el nivel de un nodo está dado por el número de aristas que deben ser recorridos para llegar a él desde el vértice raíz. La altura de un árbol es el nivel más grande del mismo.