grafos

1. Relaciones y Grafos
1.1 Relaciones
1.1.1 Órdenes parciales
1.1.2 Relaciones de Equivalencia
1.1.3 Matriz de una relación
1.1.4 Relación de Conectividad
1.2 Trayectorias en relaciones y Digrafos
1.2.1 Por producto booleano
1.2.2 Teoría de grafos
1.2.3 Puentes de Königsberg
1.2.4 Circuito de Hamilton
1.2.5 Grafo Conexo
1.2.6 Caminos y Circuitos
1.2.7 Circuito

2. Relaciones yDigrafos
Conjuntos producto y particiones

Conjuntos producto
Un par ordenado (o pareja ordenada) (a, b) es un listado de los objetos a y b en una orden prescrito, donde a aparece en primer término y b, en segundo. En consecuencia, un par ordenado (o pareja ordenada) simplemente es una secuencia de longitud 2. A partir del análisis anterior de las secuencias, se desprende que los pares ordenados(a1, b1) y (a2, b2) son iguales si y solamente si a1 = a2 y b1 = b2.
Si A y B son dos conjuntos no vacíos, se define el conjunto producto o producto cartesiano A X B como el conjunto de todos los pares ordenados (a, b) con a  A y b  B. Así
A X B = {(a,b)| a  A y b  B}

Ejemplo 1. Sean
A = {1,2,3} y B = {r,s}
entonces
A X B = {1, r}, (1, s), (2, r), (2, s), (3, r), (3, s)}.Observa que los elementos de A X B pueden ser dispuestos en forma tabular conveniente como se muestra en la siguiente figura.
B


A
r
s
1
(1,r)
(1,s)
2
(2,r)
(2,s)
3
(3,r)
(3,s)

Ejemplo 2. Si A y B son como en el ejemplo 1, entonces
B X A = {(r, 1), (s, 1), (r, 2), (s, 2), (r, 3), (s, 3)}

De los ejemplos 1 y 2, se ve que A X B no necesita ser igual a B X A.

Teorema 1.Para dos conjuntos finitos no vacíos cualesquiera A y B, |A X B| = |A||B|.

Demostración. Supóngase que |A| = m y |B| = n. Para formar un par ordenado (o pareja ordenada) (a,b), a  A y b  B, se debe realizar dos tareas sucesivas. La tarea consiste en escoger un primer elemento del conjunto A, y la tarea 2, en escoger un segundo elemento de B. Hay m maneras de efectuar la tarea 1 y n manerasde efectuar la tarea 2; por tanto, por el principio de la multiplicación, existen m X n maneras de formar un par ordenado (o pareja ordenada) (a,b). En otras palabras, |A X B| = mn = |A||B|

Ejemplo 3. Si A = B = R, el conjunto de todos los números reales, entonces R X R, también denotado por R2, es el conjunto de todos los puntos del plano. El par ordenado (o pareja ordenada) (a, b) da lascoordenadas de un punto plano.

Ejemplo 4. Una compañía de investigación de mercados clasifica a una persona de acuerdo con los siguientes criterios:
Genero: masculino (m), femenino (f).
Máximo nivel de educación terminado: escuela primaria (e); secundaria (h); universidad (c); posgrado (g)

Sean S = {m, f} y L = {e, h, c, g}. Entonces, el conjunto producto de S X L, contiene todas lascategorías en las que se clasifica la población. En consecuencia, la clasificación (f,g) representa una mujer que ha terminado alguna especialización, es decir, un posgrado. Hay ocho categorías en este esquema de clasificación.

Ahora se define el producto cartesiano de tres o más conjuntos vacíos generalizando la definición anterior del producto cartesiano de dos conjuntos. Es decir, el productocartesiano A1 X A2 X  X Am de los conjuntos no vacíos A1, A2, …, Am es el conjunto de todas las m – uplas ordenadas (a1, a2, …, am), en donde a1  Ai, i =1, 2, …, m. En consecuencia

A1 X A2 X  X Am = {(a1, a2, …, am)| a1  Ai, i = 1, 2, …, m}

Ejemplo 5. Una compañía de programas de computación proporciona las tres características siguientes para cada programa que vende:
Lenguaje:FORTRAN (f); PASCAL (p); LISP (l)
Memoria: 2 megas (2); 4 megas (4); 8 megas (8)
Sistema operativo: UNIX (u); DOS (d)

Sea L = {f,p,l}, M = {2, 4, 8} y O = {u, d}. Entonces el producto cartesianos L X M X O contiene todas las categorías que describen un programa. Hay 3  3 2 o sea 18 categorías en este esquema de clasificación.

Procediendo de manera similar a la que se siguió para demostrar el...