UNIDAD III. RELACIONES Y GRAFOS.
USO DE RELACIONES.

PRODUCTO CARTESIANO

PARES ORDENADOS: intuitivamente un par ordenado (a,b) es un par de objetos en el cual el orden en el que estos se consideran debe ser: primero a y después b . Las letras a y b se llaman la primera y la segunda componentes, respectivamente, de la pareja ordenada.

Dos pares ordenados (a, b) y (c, d) son iguales si solo si

a = c y b = d

PRODUCTO CARTECIANO: dados dos conjuntos A y B se llama producto cartesiano (o conjunto producto) de A y B, al conjunto de todos los pares ordenados (a, b) de tal forma que la primera componente a pertenece al conjunto A y la segunda componente b es elemento del conjunto B. Este conjunto se denota por A × B y se lee “A producto cartesiano de B”

Simbólicamente

A × B = {(a, b) | a ? A ? b ? B}

Ejemplos

a) Si A = {a, b, c} ; B = {x, y}

A × B = = {(a, x), (a, y), (b, x), (b, y), (c, x), (c, y)}

Nótese que el conjunto tiene seis elementos

b) Si A = {1, 2, 3} ; B = {4, 5, 6}

A × B = = {(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)}

B × A = = {(4, 1), (4, 2), (4, 3), (5, 1), (5, 2), (5, 3), (6, 1), (6, 2), (6, 2)}

Nótese que en este ejercicio cada conjunto tiene nueve elementos, y que A × B ? B × A

En general, si n(A) = p y n(B) = q entonces, n(A × B) = n(B × A) = pq

Además, el producto cartesiano No es conmutativo, es decir A x B ? B x A a menos que A = B o que uno de los conjuntos sea vacío.

Si A y B son conjuntos finitos su producto puede ser representado en el plano cartesiano colocando el conjunto A en el eje horizontal, y B en el eje vertical. A cada par ordenado (a,b) le corresponde un punto del plano.

Por ejemplo, Si A = {a1, a2, a3, a4} y B = {b1, b2, b3} , el conjunto producto consta de 12 elementos o parejas, y en su representación gráfica deben aparecer 12 puntos que forman un red, así:   

Otra forma de representar el producto A × B es mediante un diagrama de árbol.

Por ejemplo, si A = {1, 2 ,3} y B = {a, b}, la gráfica arborescente correspondiente a A × B, es:

Relacion binaria

Una relación (binaria) R de un conjunto X a un conjunto Y es un subconjunto del producto cartesiano X × Y. si (x, y) ? R escribimos xRy y decimos que x esta relacionado con y.

Una relación que es reflexiva, simétrica y transitiva en un conjunto X se llama relación de equivalencia sobre X.

Ejemplos

a) Sean los conjuntos X = {a, b, c, d} y Y = {1, 2, 3, 4}, definir una relación R de X en Y y determinar el dominio de R y lel rango de R.

R = {(a, 1), (b, 2), (c, 3), (d, 4)}

El dominio se define por el conjunto {x ? X/(x, y) ? R para algún y ? Y}

dominio de R es el conjunto {a, b, c, d}

b) La relación R sobre X = {1, 2, 3, 4} esta definida por “(x, y) ? R si x = y“ es:

R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}

el dominio de R es el conjunto {1, 2, 3, 4}

el rango de R es el conjunto {1, 2, 3, 4}

se concluye que: el dominio y el rango son iguales porque la relación está definida sobre el mismo conjunto X.

La digráfica de la relación R es la siguiente:

Matrices de relaciones

Este tema lo encontramos en la página 132, sección 3.3. Se describirá brevemente como formar una matriz de relación y se realizara ejemplos. Una matriz es una manera conveniente de representar una relación R de X a Y. Se etiquetan los renglones con elementos de X (en algún orden arbitrario), y se etiquetan las columnas con elementos de Y (orden arbitrario). Luego el elemento en el renglón x y la columna y se hace igual a 1 si xRy, y 0 de otra manera. Esta matriz se llama matriz de la relación R.

Ejemplos:

Formar la matriz de relación de los siguientes conjuntos:

a)

R = {(1, b), (1, d), (2, c), (3, c), (3, b), (4, a)}

Donde X = {1, 2, 3,4} y Y = {a, b, c, d}

Considerando los ordenes: 1, 2, 3,4 y a, b, c, d tenemos la matriz:

b)

X = {2, 3, 4} Y = {5, 6, 7, 8}

Considerando las ordenes: 2, 3, 4 y 5, 6, 7,8; definida por xRy si x divide a y

GRAFOS

Existen varios tipos de grafos:

a) Un GRAFO NO DIRIGIDO G consiste en un conjunto V de vértices (o nodos) y un conjunto E de aristas (o arcos) tal que cada arista e ? E se asocia con un par no ordenado de vértices. Entonces se puede decir que si existe una arista e entre un par de vértices v y w, esta puede ser igual a: e = ( v, w) o e = ( w, v)

Un grafo esta formado de vértices y aristas (lados), por lo tanto G = {V, E}

Los vértices del grafo G son: V_1, V_2, V_3, V_4 entonces V = {V_1, V_2, V_3, V_4}

Las aristas del grafo son: e_1, e_2, e_3, e_4 entonces E = {e_1, e_2, e_3, e_4}

Entonces podemos decir que G = {{V_1, V_2, V_3, V_4}, {e_1, e_2, e_3, e_4}}

Como el grafo G no tiene lazos ni lados paralelos entonces es un grafo simple.

Otro ejemplo de grafo no dirigido es el siguiente:

Clasificacion ce tipos de relaciones

a) Reflexiva

La relación R del ejemplo anterior dada por:

R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}

se dice que es reflexiva por que cada elemento x ? X, (x, x) ? R; los pares ordenados (1, 1), (2, 2), (3, 3) y (4, 4) están en R. Si observamos la digráfica de la relación reflexiva, encontramos que tiene un lazo sobre cada vértice.

b) Simétrica

Tomando la relación R del ejemplo anterior dada por:

R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}

“no es simétrica”, por cuanto no cumple la definición que dice: “si para cada x, y ? X, si (x, y) ? R, entonces (y, x) ? R”.

c) Transitiva

Tomando la relación R del ejemplo anterior dada por:

R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}

“es una relación transitiva R sobre el cojunto X”, por cuanto cumple la definición que dice: “x, y, z ? X, si (x, y) y (y, z) ? R, entonces (x, z) ? R”.

Específicamente tenemos (1, 2), (2, 3) se tiene (1, 3); (1, 3), (3, 4) se tiene (1, 4); (2, 3), (3, 4) se tiene (2, 4) todos pertenecen a R.

d) Antisimétrica

Tomando la relación R del ejemplo anterior dada por:

R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}

“la relación R sobre el cojunto X es antisimétrica”, por cuanto cumple la definición que dice para toda: “x, y X, si (x, y) ? R y x ? y, entonces (x, y) ? R”. Específicamente tenemos (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) pertenecen a R, pero (2, 1), (3, 1), (4, 1), (3, 2), (4, 2), (4, 3) no pertenecen a R.

e) Inversa

Tomando la relación R del ejemplo anterior dada por:

R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}

La relación inversa de R que se denota por R-1, esta dada por:

R - 1 = {(1, 1), (2, 1), (3, 1), (4, 1), (2, 2), (3, 2), (4, 2), (3, 3), (4, 3), (4, 4)}

Ejercicio 1

A partir del siguiente dígrafo, resuelva las siguientes instrucciones:

1. Escriba R como un conjunto de pares ordenados

R ={(3, 5), (4, 4), (5, 5), (3, 5), (3, 4), (4, 5)}

2. Escriba una relación reflexiva sobre G1

R = {(3,3), (4,4), (5,5)}

3. Escriba una relación simétrica sobre G1

R = {(3,3), (4,4), (5,5)}

4. Escriba una relación antisimétrica sobre G1

R = {(3, 5), (3, 4), (4, 5)}

5. Escriba una relación transitiva sobre G1

R ={(3, 4), (4, 5), (3, 5)}

6. Escriba R-1 como un conjunto de pares ordenados

R-1 = {(3, 3), (4, 3), (4, 4), (5, 4), (5, 5), (5, 3)}

EMPLEO DE GRAFOS

Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.

Ejemplos

G1 = (V1, A1)

V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}

G2 = (V2, A2)

V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)}

G3 = (V3, A3)

V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> }

Gráficamente estas tres estructuras de vértices y arcos se pueden representar de la siguiente manera:

 

Algunos de los principales tipos de grafos son los que se muestran a continuación:

Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.

Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular

Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto

Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es

Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn.

A continuación pueden verse los dibujos de K3, K4, K5 y K6

Un grafo bipartito regular: se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices.

A continuación ponemos los dibujos de K1,2, K3,3, y K2,5

Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.

Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.

Caminos

Sean x, y " V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. En este caso

x e y se llaman los extremos del camino

El número de aristas del camino se llama la longitud del camino.

Si los vértices no se repiten el camino se dice propio o simple.

Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.

Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.

Llamaremos ciclo a un circuito simple

Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo

Camino.

Es un conjunto de vértices y aristas que llevan a un punto del grafo.

Clasificación de grafos.

Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos.

Grafo regular: Aquel con el mismo grado en todos los vértices

Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto.

Grafo completo: Aquel con una arista entre cada par de vértices.

Un grafo bipartito regular: se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices.

Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.

Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.

Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.

GRAFOS EULERIANOS.

Aquellos que contienen un camino euleriano.

GRAFOS CONEXOS

Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro.

ÁRBOLES

Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también acíclico, pero a su vez es conexo.

BOSQUES DE ÁRBOLES.

Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos.

RECORRIDO DE UN GRAFO.

Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodo de salida. Las dos principales técnicas para recorrerlo son: recorrido en anchura y recorrido en profundidad.

GRAFO
Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (arcs en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole. Un grafo simple está formado por dos conjuntos:
Un conjunto V de puntos llamados vértices o nodos.
‘’‘Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados. De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos.’‘’

GRAFOS DIRIGIDOS
Un grafo en el cual toda arista es dirigida se denominará "digrafo" o bien "grafo dirigido". Un grafo dirigido o dígrafo consiste de un conjunto de vértices V y un conjunto de arcos A.
Los vértices se denominan nodos o puntos; los arcos también se conocen como aristas o líneas dirigidas que representan que entre un par de vértices existe una relación univoca.

GRAFOS NO DIRIGIDOS:
Un grafo en el cual todas las aristas son no dirigidas se denominará "grafo no dirigido". El grafo no dirigido es aquel que no tiene sentido su arista. Un grafo no dirigido G representa elementos, y una arista (v, w) representa una incompatibilidad entre los elementos v y w.
Si en un Grafo hay aristas dirigidas y aristas no dirigidas, entonces el grafo se denomina "mixto".

NODO
Nodos (también llamados vértices) se representan con puntos en el grafo.