Matematicas Discretas

Capítulo 1

Grafos
1.1. Conjuntos y relaciones
Consideraremos un conjunto como una colección cualquiera de objetos. Un conjunto queda definido por los objetos que a él pertenecen; dichos objetos son los elementos o miembros del mismo. Si x es un miembro del conjunto A, escribimos x ∈ A y decimos que x pertenece a A; en caso contrario, escribimos x ∈ A y decimos, análogamente, que x nopertenece a A. Si cada elemento x de un conjunto A es también miembro de otro conjunto B, decimos que A es un subconjunto de B, o que A está incluído en B, y escribimos A ⊂ B. Dos conjuntos A y B son iguales si y solamente si A ⊂ B y B ⊂ A; es decir, si constan exactamente de los mismos elementos. En ese caso, escribimos A = B. A veces se emplea también la notación A ⊆ B para la relación de inclusión, yel símbolo ⊂ se reserva para la inclusión propia, que ocurre cuando A ⊆ B pero A = B. En general, la relación de inclusión propia aparece con menos frecuencia, y usaremos el símbolo más sencillo para la relación más frecuente, de modo que “⊂” significará siempre para nosotros “está incluido en o es igual a”. En lo sucesivo nos ocuparemos predominantemente de conjuntos finitos, que pueden denotarseconvenientemente enumerando todos sus elementos. El número de elementos de un conjunto finito A se denomina también a veces su cardinal, y se escribe |A|.

1.1.1. Producto cartesiano
El producto cartesiano de dos conjuntos A y B se define como el conjunto formado por todos los pares ordenados posibles cuyo primer elemento es un miembro de A y cuyo segundo elemento es un miembro de B. En notaciónconjuntista A × B = {(a, b) | a ∈ A, b ∈ B} Si los conjuntos involucrados son finitos, es evidente que |A × B| = |A| · |B|. Por ejemplo, si A es el conjunto de todos los hombres y B el de todas las mujeres, A× B es el conjunto de todas las parejas (heterosexuales) posibles que pueden formarse entre ellos. En particular, si no existiesen hombres, A × B sería vacío, y todo bastante aburrido.

1Siguiendo con el ejemplo, el producto cartesiano A × B contiene todas las parejas concebibles, no necesariamente las que existen en la realidad. Consideremos solamente aquellas parejas hombre-mujer que constituyan un matrimonio. El conjunto R de pares hombre-mujer (h, m) donde h es un hombre, m es una mujer y h está casado con m es un subconjunto de A × B. Además, la inclusión R ⊂ A × B es casiseguramente propia, excepto en una sociedad polígama y extremadamente promiscua. En cualquier caso, R contiene toda la información que necesitamos sobre el matrimonio en general: nos dice exactamente quién está casado con quién.

1.1.2. Relaciones
Definimos una relación entre dos conjuntos A y B como un subconjunto R del producto cartesiano A × B; en símbolos, R ⊂ A × B. El hecho de que (a, b) ∈ Rse suele expresar diciendo que a está relacionado con b, y, de forma abreviada, se suele escribir como a R b. La negación de a R b se escribe a R b Una relación binaria en un conjunto A se define como un subconjunto R del producto A × A. El conjunto en el que se establece R suele denominarse dominio de la relación. Algunos ejemplos de relaciones binarias son los siguientes: La relación de igualdad= entre números reales. La relación “ser hermano de” en el conjunto de los seres humanos. La relación de orden ≤ entre números reales. La relación “ser progenitor de” en el conjunto de los seres humanos. Esta relación contendría todas las parejas ( p, h) de personas cuyo segundo elemento fuese hijo del primero. La relación “ser hijo de” en el conjunto de los seres humanos. Esta relación contendríatodas las parejas (h, p) de personas cuyo segundo elemento fuese padre del primero. Es evidente que esta relación se obtiene de la anterior invirtiendo el orden de todos los pares: se dice que son inversas. La relación “ser divisor de” entre números naturales, que suele denotarse por el símbolo |. Por ejemplo, 6 | 24, pero 6 | 31. La relación inversa de ésta también tiene un nombre común: “ser...