Relaciones binarias y grafos: definiciones, propiedades y conjunto cociente

MatemáticasActualizado el 4,31 KB

Resumen

El documento presenta las relaciones binarias sobre un conjunto y su representación mediante digrafos, incluyendo dominio, rango, grados interno y externo. Analiza las propiedades reflexiva, simétrica y transitiva, y explica el conjunto cociente y el diagrama de Hasse. También recoge conceptos básicos de grafos como grado, lazos, aristas paralelas, trayectorias, circuitos de Euler y Hamilton, y árboles.

Puntos clave

  • Una relación binaria R en A es un subconjunto del producto cartesiano AxA.
  • En un digrafo se dibuja una flecha de ai a aj si y solo si (ai,aj) pertenece a R.
  • El grado externo ge(a) cuenta los nodos b tales que (a,b) pertenece a R; el grado interno gi(a) cuenta los nodos b tales que (b,a) pertenece a R.
  • Una relación es reflexiva si todos los elementos tienen lazo; en la matriz MR, mii=1 para todo i.
  • Una relación es simétrica si cada arista (x,y) implica la arista (y,x); en la matriz, mij=mji.
  • Un grafo simple no tiene lazos ni aristas paralelas.
  • Un circuito de Euler recorre todas las aristas una sola vez y vuelve al vértice inicial; un ciclo Hamiltoniano pasa por todos los vértices una vez y vuelve al inicio.

Ponte a prueba

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.

Descargar

PDF Word HTML

Preguntas frecuentes

¿Qué es una relación binaria?

Es cualquier subconjunto del producto cartesiano AxA, siendo A un conjunto no vacío. Se escribe R ⊆ AxA.

¿Qué es un grafo simple?

Es un grafo que no tiene lazos ni aristas paralelas.

¿Qué es el diagrama de Hasse?

Es una simplificación del digrafo de una relación de orden, en la que se omiten los lazos, las aristas que se deducen por transitividad y la orientación de las flechas.

Ponte a prueba

Tarjetas de repaso

Pulsa una tarjeta para ver la respuesta.

Test

1. Según el texto, ¿qué es una relación binaria R definida en un conjunto A?
2. ¿Cuándo una relación R es reflexiva en el digrafo?
3. ¿Qué condición cumple una relación simétrica en la matriz MR?
4. ¿Cuántas aristas tiene que ver un lazo en el grado de un vértice?
5. ¿Qué es un vértice aislado?
6. ¿Qué diferencia hay entre un circuito de Euler y un ciclo Hamiltoniano?

Preguntas generadas con IA a partir del documento: comprueba las respuestas con el texto.