Md

Matemáticas Discretas Resúmenes de Teoría Juan David González Cobas 7 de junio de 2004

II

Índice general 1. Combinatoria 1.1. Principios de la suma y el producto . . . . . . . 1.2. Muestras: permutaciones y combinaciones . . . 1.3. Teorema del binomio y coeficientes binomiales 1.4. Muestras con reemplazo . . . . . . . . . . . . 1.5. Permutaciones con elementos identificados . . 1.6. Generación ordenada de muestras . . . . . . . 1.6.1. Permutaciones en orden lexicográfico . 1.6.2. Combinaciones en orden lexicográfico . 1.7. El principio de inclusión-exclusión . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

1 1 2 5 8 12 13 14 15 15

2. Grafos 2.1. Conjuntos y relaciones . . . . . . . . . . . . . . 2.1.1. Producto cartesiano . . . . . . . . . . . . 2.1.2. Relaciones . . . . . . . . . . . . . . . . 2.1.3. Propiedades de las relaciones . . . . . . . 2.1.4. Clausura transitiva . . . . . . . . . . . . 2.2. Grafos . . . . . . . . . . . . . . . . . . . . . . . 2.2.1. Grafo dirigido y no dirigido . . . . . . . 2.2.2. Incidencia y grado . . . . . . . . . . . . 2.2.3. Representación como estructuras de datos 2.2.4. Caminos y ciclos . . . . . . . . . . . . . 2.3. Relaciones y grafos . . . . . . . . . . . . . . . . 2.4. Accesibilidad y conexión . . . . . . . . . . . . . 2.4.1. Matrices de accesibilidad . . . . . . . . . 2.5. Algunos grafos especiales . . . . . . . . . . . . . 2.5.1. Grafos completos . . . . . . . . . . . . . 2.5.2. Torneos . . . . . . . . . . . . . . . . . . 2.5.3. Grafos bipartitos . . . . . . . . . . . . . 2.5.4. Caminos y ciclos . . . . . . . . . . . . . 2.5.5. Grafos cúbicos Q n . . . . . . . . . . . . 2.6. Arboles . . . . . . . . . . . . . . . . . . . . . . 2.6.1. Arboles enraizados . . . . . . . . . . . . 2.6.2. Arboles binarios . . . . . . . . . . . . . 2.7. Recorridos de grafos . . . . . . . . . . . . . . . 2.7.1. Recorridos de árboles binarios . . . . . . 2.7.2. Recorridos eulerianos . . . . . . . . . . . 2.7.3. Caminos hamiltonianos . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

19 19 19 20 20 22 23 23 24 25 26 27 28 30 32 32 33 34 34 34 36 38 40 41 41 42 47

III

2.7.4. Recorridos en anchura y profundidad . . . . . . . . . . . . . 2.7.5. Caminos mínimos, MST y demás . . . . . . . . . . . . . . . 2.8. Planaridad y coloreado . . . . . . . . . . . . . . . . . . . . . . . . . 3. Recurrencias y notación asintótica 3.1. Objetivo . . . . . . . . . . . . . . 3.2. Recurrencias lineales homogéneas 3.3. Notación asintótica . . . . . . . . 3.4. Recurrencias divide y vencerás . .

IV

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

49 52 53 57 57 58 60 62

Capítulo 1

Combinatoria El objetivo de la Combinatoria, tal y como nosotros vamos a entenderla, consiste en calcular el número de elementos de ciertos conjuntos finitos. Es decir, nos ejercitaremos en el uso de determinadas técnicas de recuento.

1.1. Principios de la suma y el producto Aunque en este capítulo emplearemos una gama muy variada de técnicas con el fin de calcular de cuántas formas pueden disponerse conjuntos de objetos, todas ellas se basan en dos principios que denominaremos principio de la suma y principio del producto. Vamos a dar diferentes enunciados de los mismos. En primer lugar, la versión conjuntista. Teorema 1. (Principio de la suma). Si A 1 , A2 , . . . , An es una familia de conjuntos disjuntos dos a dos (es decir, Ai ∩ A j = ∅ para i 6= j), entonces ¯ ¯ n n ¯[ ¯ X ¯ ¯ |Ak | = |A1 | + |A2 | + · · · + |An | Ak ¯ = ¯ ¯ ¯ k=1

k=1

es decir, el cardinal (número de elementos) de la unión de dichos conjuntos es igual a la suma de sus cardinales. Y de forma análoga enunciamos el

Teorema 2. (Principio del producto). Si A 1 , A2 , . . . , An es una familia de conjuntos cualesquiera, entonces ¯ ¯ n n ¯Y ¯ Y ¯ ¯ |Ak | = |A1 | · |A2 | · . . . · |An | Ak ¯ = ¯ ¯ ¯ k=1

k=1

es decir, el cardinal (número de elementos) del producto cartesiano de dichos conjuntos es igual al producto de sus cardinales.

Enunciados de esta forma, los dos principios tienen una apariencia sobrecogedora. Sin embargo, expresan ideas muy simples que todos poseemos asimiladas de forma inconsciente en nuestra intuición. Así pues, enunciaremos los mismos en forma intuitiva. 1

Teorema 3. (Principio de la suma, forma intuitiva) Si una elección puede realizarse por varios caminos alternativos, excluyentes entre sí, el número de resultados posibles es igual a la suma de las alternativas que cada uno de los caminos nos ofrece. Teorema 4. (Principio del producto, forma intuitiva) Si una elección queda determinada por varias elecciones parciales independientes entre sí (es decir, cada una de ellas puede realizarse sin afectar al resultado de las otras), el número de resultados posibles es el producto de los números de posibilidades que ofrece cada elección parcial. Una aplicación de ambos principios la encontramos en el siguiente Ejemplo 1. Calcular cuántas palabras de hasta cuatro letras existen, suponiendo que el alfabeto tiene 26 símbolos. Para empezar, podemos construir palabras de uno, dos, tres y cuatro símbolos. Es evidente que el número total de palabras será la suma total del número de palabras de una letra, de dos, de tres y de cuatro letras. Esta es una simple aplicación del principio de la suma: P = P1 + P2 + P3 + P4 Calculamos cada cantidad por separado. Es evidente que hay 26 palabras de una letra. Para construir una palabra de dos letras, tenemos que escoger la primera y la segunda: ambos procesos son independientes, y cada uno ofrece 26 posibilidades. Por lo tanto, el principio del producto nos dice que existen 26 × 26 = 262 palabras de dos letras. Generalizando, el número de palabras de i letras será Pi = 26 {z · · · 26} | × 26 i veces

por lo que

P = 26 + 262 + 263 + 264 = 475254

1.2. Muestras: permutaciones y combinaciones La aplicación directa de los principios de la suma y el producto sería muy laboriosa salvo en problemas muy simples. Existen, sin embargo, bloques constructivos que nos permiten descomponer los problemas combinatorios con facilidad, haciéndolos manejables. En general, resolveremos el cálculo de un problema descomponiéndolo en diferentes tipos de muestras. Antes de dar una definición rigurosa, veamos una descripción informal del tipo de problema a que reduciremos nuestros argumentos. Consideremos un conjunto de n objetos diferentes: para fijar ideas, pensemos en bolas numeradas de 1 a n. De estas bolas, vamos a seleccionar r , siendo 0 ≤ r ≤ n. Una tal selección de r objetos, a escoger de n dados, es lo que denominaremos muestra. Un ejemplo puede ser un sorteo de la lotería primitiva. En el bombo tenemos, exactamente, 49 bolas numeradas del 1 al 49. El sorteo (simplificando mucho) consiste en la extracción de seis bolas del bombo. En este ejemplo, n = 49 y r = 6. Obviamente, el orden en que salgan las bolas, si salen todas a la vez o salen al revés, es algo que no nos importa: lo único que afecta al resultado es que una bola dada (pongamos, la 17) esté o no presente en la muestra elegida. Otro ejemplo puede ser una rifa de tres premios entre los 50 alumnos de una clase. El primer premio consiste en un aprobado gratuito en Matemática Discreta; el segundo 2

es un DVD con materiales dudosos, pero sin duda estimulantes; el tercer premiado recibe como castigo el último CD de David Bisbal. En este caso, el resultado del sorteo consiste en la selección de tres alumnos entre los 50 dados. En este caso, n = 50 y r = 3. Ahora bien, en este caso que los premiados sean Juan, David y Ana no es lo mismo que tomar a David, Ana y Juan; en este último, Juan será castigado con el CD fatal. Así, el orden de la muestra es relevante. Definición 1. Sea X un conjunto finito de n elementos. Una selección de r elementos distintos de X se denomina una r -combinación de X . El número de r -combinaciones de un conjunto de n elementos se denota por C(n, r ). En aplicación del ejemplo anterior, el número de posibles resultados de la lotería primitiva es C(49, 6). Pronto aprenderemos a calcular el valor de este número. Para el ejemplo de la rifa que incluye el fatídico CD, tenemos otra Definición 2. Sea X un conjunto finito de n elementos. Una secuencia ordenada de r elementos distintos {x 1 , x 2 , . . . , xr } ⊂ X se denomina una r -permutación de X . El número de r -permutaciones de un conjunto de n elementos se denota por P(n, r ). Si, en particular, r = n, hablamos simplemente de las permutaciones de los n elementos dados. En el ejemplo de la rifa, los posibles resultados son las 3-permutaciones de los 50 alumnos, y hay P(50, 3) de ellas. ¿Cuál es el valor de estos misteriosos C(n, r ), P(n, r ) para números n y r concretos? La respuesta la dan los teoremas que siguen: Teorema 5. P(n, r ) = n(n − 1)(n − 2) · · · (n − r + 1) | {z }

(1.1)

r factores

Demostración. Para determinar una r -permutación de n objetos, es preciso escoger cuál de los objetos va a figurar como primero. Esto puede hacerse de n maneras, pues hay n candidatos. Una vez escogido el primer elemento, toca escoger el segundo. Éste puede ser cualquiera de los n, menos el recién escogido; por lo tanto, restan n − 1 posibilidades. El tercer elemento, de idéntica forma, podrá escogerse de n − 2 maneras, y así sucesivamente. El número de posibilidades será el producto de todas las calculadas, que es el producto indicado más arriba. El caso particular n = r (permutaciones de n elementos) es especialmente interesante. El número P(n, n) = n(n − 1)(n − 2) · · · 3 · 2 · 1 se denomina factorial de n y se denota por n!. Representa el número de maneras en que pueden ordenarse n objetos. El factorial es una función de n de crecimiento extremadamente rápido, como muestra la tabla 1.2 Cada factorial se obtiene del anterior multiplicándolo por el siguiente entero: así, 6! es igual a 5! multiplicado por 6, y en general se cumple la ecuación n! = n (n − 1)!

n≥1

Una ecuación como ésta, que define el valor de una función en términos de valores de la misma para argumentos más pequeños, se denomina una relación de recurrencia; estudiaremos algunas muy importantes en el tema 3. En particular, 1! = 1 · 0!, y de esta 3

n 0 1 2 3 4 5 6 7 8 9 10 11 12

n! 1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600

Cuadro 1.1: Factoriales de n = 0, 1, . . . 12 ecuación podemos deducir que el factorial de cero es la unidad, y no cero, como cabría concebir intuitivamente. Con el uso de factoriales, podemos escribir la fórmula 1.1 en la forma más compacta P(n, r )

=

n(n − 1)(n − 2) · · · (n − r + 1) n(n − 1)(n − 2) · · · (n − r + 1) · (n − r )(n − r − 1) · · · 3 · 2 · 1 = (n − r )(n − r − 1) · · · 3 · 2 · 1 n! = (n − r )!

que tiene utilidad exclusivamente en razonamientos teóricos, puesto que el cálculo de P(n, r ) casi siempre se realiza directamente a través de la fórmula 1.1. En cuanto a C(n, r ), obtenemos su valor en el siguiente Teorema 6. C(n, r ) =

P(n, r ) r!

(1.2)

Demostración. Una r -permutación de n objetos queda determinada por dos cosas: qué objetos intervienen en qué orden figuran Está claro que la elección de los objetos puede hacerse de C(n, r ) maneras; cada elección determina r ! órdenes posibles, y cada una de estas selecciones de r objetos y un orden particular de ellos determina una r -permutación y solamente una. Por lo tanto, el número de r -permutaciones es, aplicando el principio del producto P(n, r ) = r ! C(n, r ) que es la afirmación del teorema. 4

(1.3)

El número C(n, r ) es tan importante que recibe una denominación especial; es el número combinatorio o coeficiente binomial µ ¶ n(n − 1) · · · (n − r + 1) n = (1.4) r! r Estudiaremos más detenidamente las propiedades de estos números, cuya importancie es trascendental, en la sección 1.3; allí descubriremos de dónde viene el nombre de coeficiente binomial que damos a esta clase de objeto. Por lo pronto, nos conformaremos con utilizarlos en el cálculo de las respuestas a problemas de muestras. Por ejemplo, las fórmulas 1.2 y 1.4 nos permiten saber cuántos resultados son posibles en un sorteo de lotería primitiva: C(49, 6) =

49 · 48 · 47 · 46 · 45 · 44 = 13983816 6!

es decir, casi 14 millones de combinaciones. Jugando una apuesta simple, a 52 sorteos por año, el apostante medio emplea más de 260000 años en conseguir un boleto con seis aciertos. Naturalmente, la vida del apostante medio es mucho más corta. En cuanto a la rifa, el número de posibles tríos de seleccionados es de P(50, 3) = 50 · 49 · 48 = 117600

1.3. Teorema del binomio y coeficientes binomiales En álgebra elemental se demuestra el famosísimo Teorema 7. (Fórmula del binomio de Newton) µ ¶ µ ¶ µ ¶ n n n n−1 n n−2 2 (x + y)n = x + x y+ x y + ··· + 0 1 2 µ ¶ µ ¶ n n−k k n n + x y + ··· + y k n n µ ¶ X n n−k k = x y k

(1.5)

k=0

Los casos particulares de esta fórmula para n = 0, 1, 2, 3, 4 son bien conocidos del álgebra elemental (o deberían serlo): (x + y)0

=

1

1

(x + y)3 (x + y)4

= =

x 3 + 3x 2 y + 3x y 2 + y 3 x 4 + 4x 3 y + 6x 2 y 3 + 4x 1 y 3 + y 4

(x + y) (x + y)2

= =

x+y x 2 + 2x y + y 2

De manera general, la fórmula 1.5 nos dice que una potencia de un binomio se expande en una suma de términos que se inician con x n y van conteniendo potencias decrecientes del primer sumando y crecientes del segundoi (x e y en nuestro ejemplo). Dichos términos van afectados de coeficientes que resultan ser números combinatorios: de ahí 5

el nombre de coeficientes binomiales que les dimos en la sección anterior. Los desarrollos anteriores (cuadrado de un binomio, cubo y cuarta potencia) nos permiten ver cuáles son los valores de los primeros coeficientes binomiales. Por definición µ ¶ n n(n − 1) · · · (n − r + 1) = r! r ¡ ¢ y, en general, esta es la fórmula que recomendamos emplear para el cálculo de nr . Es válida para cualquier r entero y cualquier n complejo, aunque nosotros nos restringiremos al caso 0 ≤ r ≤ n, donde n será un número entero. De la definición de arriba y de la fórmula P(n, r ) = n!/(n − r )! se obtiene inmediatamente la expresión µ ¶ n n! = r !(n − r )! r y de ésta la propiedad de simetría ¶ µ ¶ µ n n = n −r r que es muy patente en los desarrollos del cuadrado, cubo y cuarta potencia de un binomio: los coeficientes son simétricos. Empiezan valiendo 1, y luego crecen hasta un máximo en el centro del desarrollo, para decrecer simétricamente hacia el último término. Para valores bajos del índice inferior tenemos µ ¶ µ ¶ n n =n =1 y 1 0 y por simetría tenemos µ ¶ n =1 n

µ

y

¶ n =n n−1

Una forma divertida de calcular manualmente los coeficientes binomiales resulta de colocarlos dispuestos como en la tabla 1.3 Este disposición se conoce como triángulo de Pascal, y también como triángulo de Tartaglia. Naturalmente, el triángulo se extiende indefinidamente hacia abajo. La simetría de los números combinatorios de un índice superior fijo se observa de inmediato en el triángulo, puesto que las filas son simétricas; se observan también fácilmente los valores extremos para r = 0, 1 y r = n, n − 1. El triángulo de Pascal tiene propiedades muy curiosas, reflejo de la virtual infinidad de propiedades de los números combinatorios. La más importante de todas es la relación de recurrencia que nos permite calcular con sencillez los números de una fila a partir de los de la inmediata superior. En efecto: si nos fijamos bien, comprobaremos que cada número del triángulo es la suma del que está justa encima, y el que está a la izquierda de éste último. Por ejemplo, 120 (en la fila n = 10) es suma de 84 y 36 (justo encima y a la izquierda). En símbolos: ¶ ¶ µ µ ¶ µ n−1 n−1 n (1.6) + = k−1 k k 6

n 0 1 2 3 4 5 6 7 8 9 10

µ ¶ n 0 1 1 1 1 1 1 1 1 1 1 1

µ ¶ n 1

µ ¶ n 2

µ ¶ n 3

µ ¶ n 4

µ ¶ n 5

µ ¶ n 6

µ ¶ n 7

µ ¶ n 8

µ ¶ n 9

µ ¶ n 10

1 2 3 4 5 6 7 8 9 10

1 3 6 10 15 21 28 36 45

1 4 10 20 35 56 84 120

1 5 15 35 70 126 210

1 6 21 56 126 252

1 7 28 84 210

1 8 36 120

1 9 45

1 10

1

Cuadro 1.2: Triángulo de Pascal Naturalmente, la mera observación de que una propiedad se cumple en la región del triángulo que hemos escrito no constituye una demostración. La recurrencia 1.6 se prueba de la forma siguiente: µ ¶ n n(n − 1) · · · (n − k + 1) = k! k (n − k + k)(n − 1) · · · (n − k + 1) = k(k − 1)! n − k (n − 1) · · · (n − k + 1) k (n − 1) · · · (n − k + 1) · + · = k (k − 1)! k (k − 1)! (n − 1) · · · (n − k + 1) · (n − k) (n − 1) · · · (n − k + 1) = +· k(k − 1)! (k − 1)! µ ¶ µ ¶ n−1 n−1 = + k k−1 En el curso de esta demostración nos hemos ¡ ¢visto obligados a introducir o extraer un factor k, n − k, n en el coeficiente binomial nk . Estas operaciones son de suficiente importancia como para consignarlas aparte: µ ¶ µ ¶ µ ¶ µ ¶ n−k+1 n n n n−1 n n−1 = · = · = · k k k−1 k k−1 n−k k La fórmula del binomio de Newton nos permite evaluar algunas sumas interesantes de coeficiente binomiales. Por ejemplo, poniendo x = y = 1 en la fórmula 1.5 obtenemos que µ ¶ µ ¶ µ ¶ µ ¶ n n n n 2n = + + + ··· + (1.7) 0 1 2 n Es decir: la suma de los números que figuran en una fila del triángulo de Pascal es una potencia de dos. Si, en su lugar, ponemos x = 1, y = −1, obtenemos otro resultado interesante: µ ¶ µ ¶ µ ¶ µ ¶ n n n n n − · · · + (−1) + − 0= n 2 1 0 7

o, si lo queremos poner de otra manera µ ¶ µ ¶ µ ¶ µ ¶ µ ¶ µ ¶ n n n n n n + ... + + + ··· = + + 5 3 1 4 2 0 es decir, en una fila del triángulo de Pascal, los coeficientes de índice inferior par suman lo mismo que los de índice inferior impar. De lo que podemos deducir, a partir de la fórmula 1.7, que X µn ¶ X µn ¶ = 2n−1 = k k k par

k impar

Los coeficientes binomiales satisfacen identidades sin fin, y las que acabamos de ver son solamente algunas de ellas. Podrían llenarse páginas y páginas de identidades interesantes en que intervienen. Sin embargo, nuestro interés fundamental no es la manipulación de estos coeficientes, sino el cálculo de combinaciones, de forma que lo dejaremos en este punto. Solamente citaremos, para cerrar este apartado, algunas propiedades interesantes que pueden demostrarse por inducción o mediante un uso ingenioso de la fórmula del binomio: µ ¶µ ¶ µ ¶µ ¶ µ ¶µ ¶ µ ¶µ ¶ n m n m n m n m + + ... + + k 0 k−1 1 1 k−1 0 k ¶ µ n+m (Convolución de Vandermonde) = k µ ¶ µ ¶ µ ¶ µ ¶ µ ¶ n+0 n+1 n+2 n +r n +r +1 + + + = 0 1 2 r r µ ¶ µ ¶ µ ¶ µ ¶ µ ¶ n+0 n+1 n+2 n +r n +r +1 + + + = n n n n r

1.4. Muestras con reemplazo Existen algunos problemas que no pueden resolverse directamente con las fórmulas de la sección 1.2. Aparecen cuando las muestras que construimos permiten que un elemento del conjunto que muestreamos sea seleccionado varias veces. A dicho tipo de muestras se la denomina genéricamente muestras con reemplazo. Dos ejemplos aclararán este tipo de construcción. Ejemplo 2. ¿Cuántas palabras de seis letras podemos formar con el alfabeto español (26 letras) En este caso, nuestra muestra es ordenada (puesto que la palabra pelota no es la misma que la palabra paleto), pero no es una permutación ordinaria, puesto que puedo construir palabras como papada en que la letra a es seleccionada tres veces. Sin embargo, es fácil calcular el número de posibilidades por el principio del producto. Cada una de las posiciones de la palabra puede ser escogida independientemente de las demás, y de 26 maneras. Por lo tanto, el número total de resultado posibles es 26 · 26 · 26 · 26 · 26 · 26 = 266 Este problema es un ejemplo de r -permutaciones con reemplazo de un conjunto de n elementos, donde n = 26 y r = 6. Una tal r -permutación es una secuencia ordenada 8

de r elementos seleccionados a partir de un conjunto de n dados, teniendo en cuenta ahora que un elemento puede utilizarse varias veces. El número de muestras de este tipo se calcula de forma muy simple Teorema 8. El número de r -permutaciones con reemplazo de un conjunto de n elementos es PR(n, r ) = n r Demostración. Es una consecuencia directa de la regla del producto y de que cada miembro de la permutación puede escogerse de n formas distintas. Ejemplo 3. En una urna tenemos una cantidad virtualmente ilimitada de bolas rojas, blancas y negras. Si extraigo cinco bolas, ¿cuántos resultados son posibles? Este problema es bastante más complicado. La “cantidad ilimitada” de bolas es un dato que nos permite suponer que hay más de cinco bolas de cada color, de forma que la extracción de cinco bolas rojas, o cinco negras, o cinco blancas, sea un resultado posible. ¿Cuántas muestras distintas pueden salir? Los métodos vistos hasta ahora no parecen aplicables de forma directa para encontrar esto. Vamos a enumerar todas las posibilidades: BBBBB BBBN N BBN N N BBRRR BN N RR NNNNN N N RRR

BBBBN BBBN R BBN N R BN N N N BN RRR NNNNR N RRRR

BBBBR BBBRR BBN RR BN N N R BRRRR N N N RR RRRRR

Está claro que el resultado N N N R R es el mismo que N R N R N ; no nos importa el orden en que las bolas salen, sino cuántas de cada color. Este tipo de muestras, en que no nos importa el orden de los objetos escogidos y éstos se extraen de un conjunto dado, pudiendo escogerse el mismo elemento repetidas veces, se denominan r combinaciones con reemplazo del conjunto de n elementos dado. En este ejemplo, n = 3 y r = 5. Una de estas combinaciones con reemplazo queda determinada por el número de bolas rojas x R , bolas blancas x B , y bolas negras, x N , que constituyen la muestra. La restricción es que las tres cantidades han de sumar cinco: xR + xB + xN = 5

(1.8)

El número de muestras es el número de soluciones de la ecuación1.8 en números enteros no negativos. Esto nos conduce aún a otra formulación del problema. Podríamos considerar que tenemos tres amigos, Rojo, Blanco y Negro, que se reparten entre sí cinco monedas. ¿Cuántos repartos posibles hay? En cualquier caso, podemos formular estos tres problemas como uno de combinaciones (muestras desordenadas), si permitimos que un objeto introducido en la muestra pueda volver a seleccionarse. En efecto: bolas Podemos imaginar que el saco contiene solamente tres bolas: una roja, una negra y una blanca. Extraemos una bola, anotamos su color y la devolvemos al saco. Volvemos a realizar la misma operación hasta completar cinco extracciones con reemplazo. El resultado, prescindiendo del orden, es una 5-combinación de tres elementos en que se permite el reemplazo de los objetos a muestrear 9

reparto de monedas Imaginemos que hay que repartir cinco monedas (idénticas) entre los tres amigos Rojo, Blanco y Negro. Cogemos una moneda y escogemos a cuál de los tres individuos se la vamos a dar, para lo cual podemos recurrir al consabido bombo con tres bolas. Cada moneda implica escoger a uno de los tres amigos, pudiendo resultar cualquiera de ellos elegido más de una vez. ecuacion Está claro que el problema es idéntico a repartir cinco unidades entre las tres variables. Aunque no sepamos cómo calcular cuántas soluciones totales existen (hemos llegado a las 21 enumeradas arriba por pura fuerza bruta), está claro que la estructura de los tres problemas es idéntica. ¿Cómo encontrar el número de posibilidades en el caso más general? La respuesta nos la da el siguiente Teorema 9. El número de r -combinaciones con reemplazo que puede obtenerse a partir de un conjunto de n objetos es µ ¶ µ ¶ n +r −1 n +r −1 CR(n, r ) = = r n−1 Demostración. Vamos a demostrar que el número de maneras de repartir r bolas idénticas entre n jugadores viene dado por la fórmula indicada. Para ello, consideremos que las bolas están inicialmente apoyadas de la forma consecutiva que vemos en la figura 1.8, caso a). Supongamos que otorgo x 1 bolas al primer jugador: separo las x 1 primeras bolas de las restantes insertando una bola negra que me permita llevar la cuenta, como puede verse en el apartado b) de la misma figura. De las siguientes bolas, decido dar x 2 al segundo jugador, y marco el final de la parte que le corresponde por la inserción de otra bola negra (apartado c), donde podemos ver que las dos bolas negras contiguas representan que x 2 = 0). El proceso continúa insertando una bola negra cada vez que quiero separar las bolas ya repartidas de las que restan, como podemos ver en los apartados d) y e). Finalmente, al repartir las x n−1 bolas del penúltimo jugador e insertar la consabida bola negra, determinamos ya la parte que le queda al jugador n-simo, como se ve en el aprtado f) de la figura 1.8. Con este proceso, obtenemos una fila de r + (n − 1) bolas: las r originales, y las n − 1 negras que hemos utilizado para separar las n partes. Es evidente que cada disposición de estas bolas determina un reparto posible, y recíprocamente. Por lo tanto, el número de soluciones al problema del reparto es idéntico al número de maneras que tenemos de escoger r posiciones para las r bolas blancas entre las n + r − 1 posiciones que finalmente ocupan las bolas. En conclusión µ ¶ µ ¶ n +r −1 n +r −1 C(n, r ) = = r n−1 como se quería demostrar. En el ejemplo de las bolas, CR(3, 5) =

µ

¶ µ ¶ 3+5−1 7 = = 21 5 2

y parece que todo encaja. 10

0

Q1 Q2 Q3 Q4 Q5 Abad Abascal Álvarez Bastardo Cobas Cazorla Dehesa González Guzmán Herrero Lebrel Zapatero Zorrilla A B C D Ea) F G H Ib) J 3 + ∗c) 5 + 6 12d) χ (K 5 ) = 5 χ (K 3,3 ) = 2 χ (C7 ) = 3 χ (esto) = 4 χ (esto otro) = 4 x1 ≥ 6 x2 ≥ 8 x1 ≥ 6, x 2 ≥ 8e) x1 < 6, x 2 < 8 A2 A1 A − A1 − A2f) A12

1

2

1

2

3

4

5

6

7

8

r

3

4

5

6

7

r −1

r

3

4

5

6

r −2

r −1

r

3

4

5

r −3

r −2

r −1

r

5

r −3

r −2

r −1

r −2

r −1

x1 1

2 x1

1

2 x1

1

x3

x2

3

2 x1

1

x2

3 x2

5

4

r

xn−2

x3

x2

2 x1

4

r −3

xn−2

x3

Figura 1.1: Cómo repartir r bolas entre n jugadores

11

r xn−1

xn

1.5. Permutaciones con elementos identificados Consideremos la palabra “ABRACADABRA”. Si reordenamos sus letras, podemos obtener diversos conjuros, algunos de ellos no muy pronunciables: AAARCRAADBB AAARBDBCRAA RDAARBABAAC RDARABAACBA ¿Cuántos de ellos son posibles? Si las letras de la palabra original fuesen todas diferentes, la respuesta sería muy sencilla: P(11) = 11!. Pero al existir letras repetidas (cinco A’s, dos B’s, dos R’s, una C y una D), la respuesta resulta ser mucho menor. En efecto, si numeramos las letras originales con subíndices A1 B2 R3 A4 C5 A6 D7 A8 B9 R10 A11 podemos observar que, de las 11! permutaciones existentes entre estos 11 símbolos distintos, algunas resultan en idéntica palabra al identificar letras iguales: A11 B2 R10 A8 C5 A4 D7 A6 B9 R3 A1 ,

A1 B9 R3 A4 C5 A8 D7 A6 B2 R10 A11

y muchas otras que siguen produciendo la palabra “ABRACADABRA”. ¿Cuántas en total? Podemos permutar entre sí, sin que la palabra cambie su identidad, todas las letras idénticas. Por lo tanto, en este ejemplo, “ABRACADABRA” puede escribirse de 5!2!2!1!1! = 480 maneras distintas. Cualquier otra permutación diferente puede escribirse también de 480 maneras que difieren solamente en la reordenación de letras indistinguibles. Generalizando estas observaciones obtenemos el siguiente Teorema 10. El número de permutaciones de n objetos, de los cuales existen k clases de objetos diferentes entre sí, cada una con n i miembros iguales, es ¶ µ n n = n1! n2! . . . nk ! n1, n2, . . . , nk Al número anterior se lo denomina coeficiente multinomial de n sobre n 1 , n 2 , . . . , n k . Además del cálculo del número de permutaciones de un multiconjunto, el coeficiente multinomial aparece en otro problema combinatorio clásico: el reparto de n objetos distinguibles en k clases distintas, con un número de n i objetos asignado a la clase i-ésima. Ejemplo 4. ¿De cuántas formas podemos repartir diez libros diferentes entre Alicia, Bernardo y Carlos, si a Alicia hay que darle tres libros, a Bernardo cinco y a Carlos dos? Empezamos por Alicia: tenemos que escoger para ella tres libros, y eso puede ha¡ ¢ cerse de 10 siete libros, de los que habrá que escoger 3 maneras. Después de esto quedan ¡¢ cinco para Bernardo. Tendremos para ello 75 posibilidades. Finalmente, quedarán dos ¡¢ libros, que son los que habrá que dar a Carlos, cosa que podemos hacer de 22 maneras, o sea, de una sola forma. En total µ ¶ µ ¶µ ¶µ ¶ 10 10 7 2 10! 10! 7! 2! = = = 3! 7! 5! 2! 2! 0! 3! 7! 2! 3, 7, 2 3 5 2 12

1.6. Generación ordenada de muestras En algunas ocasiones resulta conveniente enumerar todas las combinaciones o permutaciones que representan la solución a un problema, y no solamente calcular su número. Sería bueno disponer de un método que permitiese realizar esta tarea de forma ordenada y sistemática. Así, evitaríamos cometer errores u omisiones. Además, un procedimiento sistemático puede programarse, relegando al computador la tarea de producir listas de combinaciones, que es siempre tediosa. En esta sección estudiaremos dos algoritmos que permiten producir una lista ordenada de todas las n-permutaciones y las r -combinaciones del conjunto de enteros X n = {1, 2, 3, . . . , n}. En ambos casos, las muestras se representarán como “palabras” formadas por los números del conjunto X n . El orden en que vamos a producirlas es suficientemente importante como para merecer una denominación especial: se denomina orden lexicográfico. La mejor manera de entender el orden lexicográfico es mediante el ejemplo del diccionario, del cual toma su nombre. Cuando buscamos una palabra en orden alfabético, entendemos que .abonado"va después que .abeto", puesto que la primera discrepancia entre ambas palabra ocurre en la tercera posición: en .abonado"hay una letra .o", y en .abetoüna "e"; de forma que .abeto"debe ir antes, puesto que la "e"precede a la .o"en el orden alfabético subyacente. Si no hay ninguna discrepancia, y las palabras difieren simplemente en que una es más larga que la otra, como entre "mano "manotazo", se clasifica como posterior la palabra más larga. La ordenación del tipo string en la mayoría de los lenguajes de programación sigue la misma regla. A la luz de estos ejemplos, podemos definir el orden lexicográfico de de forma general como sigue. 2

Definición 3. Sea (X, <) un conjunto ordenado, que denominaremos alfabeto. Sea X ∗ el conjunto formado por todas las palabras construíbles con símbolos de X . Definimos entre las palabras de X ∗ una relación de orden que denominamos orden lexicográfico, diciendo que a < b si podemos escribir a = a1 a2 . . . ak , b = b1 b2 . . . bl , y se da uno de estos casos: o bien a es un prefijo de b, es decir, |a| ≤ |b| ai = bi

para i = 1 . . . |a|

o bien ai = bi ap < bp

para i = 1 . . . p − 1 < k, l

es decir, la primera discrepancia entre las dos palabras ocurre en la posición p-ésima, y a tiene en esa posición un carácter anterior al que b posee (anterior en el orden definido en el alfabeto X ). La definición puede parecer confusa, pero es más fácil de entender que de enunciar. Por ejemplo, en el orden habitual de los números enteros, 56874 <569, puesto que las dos palabras coinciden en las primeras dos posiciones, y la primera discrepancia surge en la tercera posición; como 56874 tiene allí un 8, y 569 tiene un 9, la primera palabra va antes en orden lexicográfico. En cambio, 568<56874. Y puede verse fácilmente que 1355655 < 1357 < 13571 < 1423 < 6 < 64 < 9876 < 991111 < 999 13

Consideremos ahora el conjunto X n = {1, 2, . . . , n} con el orden natural. Vamos a estudiar algoritmos que permitan generar, en el primer caso, las n-permutaciones de X n en orden lexicográfico, y en el segundo, las r -combinaciones de X n .

1.6.1.

Permutaciones en orden lexicográfico

Analicemos primero las 4! = 24 permutaciones del conjunto X 4 . Son las siguientes (leídas de arriba abajo y de derecha a izquierda): 1234 1243 1324 1342 1423 1432

2134 2143 2314 2341 2413 2431

3124 3142 3214 3241 3412 3421

4123 4132 4213 4231 4312 4321

¿Cómo podemos generar este listado? Es obvio que la primera permutación en orden lexicográfico es 123 . . . n, y la última n . . . 321; de forma que será suficiente disponer de un procedimiento que, dada cualquier permutación, 983126754

(1.9)

nos permita construir de forma sencilla la siguiente: 983127456

(1.10)

Ese procedimiento resulta ser el que se describe a continuación. 1.

Localizamos el sufijo más largo que esté ordenado decrecientemente. En nuestro ejemplo de la permutación 1.9, se trataría de 754. El número que antecede a dicho prefijo se denominará el pivot. En nuestro ejemplo es el 6.

2.

Comparamos el pivot con los números del sufijo que le siguen. De los que exceden al pivot, escogemos el menor. En nuestro ejemplo sería el 7.

3.

Colocamos dicho número reemplazando al pivot. En nuestro ejemplo, tendríamos 983127xxx

4.

Completamos la permutación con los números restantes en orden creciente. En el ejemplo, añadiríamos 456 donde antes tuvimos “xxx”. Lo que conduce al resultado de 1.10.

Puede comprobarse que este procedimiento es similar a la forma en que incrementamos números en notación posicional decimal. Por ejemplo, cuando incrementamos el número 76799, pasamos al 76800, puesto que al aumentar los dígitos finales (que ya no pueden incrementarse más), la modificación repercute en el primer dígito por la derecha que puede admitirla (en este ejemplo, el 7). En las permutaciones, el papel de la fila de 9’s final lo desempeña el sufijo seleccionado en el primer paso; el pivot es el dígito que se altera efectivamente; y el reemplazo de los nueves por ceros se convierte en el reemplazo de un sufijo descendente en uno ascendente, que están en los extremos del orden lexicográfico. 14

1.6.2.

Combinaciones en orden lexicográfico

La generación de combinaciones en orden lexicográfico es algo más sencilla. Basta analizar un ejemplo para inducir de él la técnica general. Consideremos las 3-permutaciones de un conjunto de cinco elementos X 5 , enumeradas, una vez más, por columnas: 123 124 125 134 135

145 234 235 245 345

Puede verse que el paso de una combinación a la siguiente se obtiene incrementando el último miembro. Si ello no fuera posible, por haber alcanzado éste un valor máximo, trasladamos nuestro intento al dígito precedente; y seguimos así hasta encontrar un dígito susceptible de ser incrementado. Hecho esto, completamos la combinación con los números inmediatamente siguientes. En suma, el procedimiento para generar la siguiente r -permutación de n elementos es 1.

Localizamos el sufijo más largo que termine en n que esté formado por números consecutivos (obsérvese que podría ser el sufijo vacío). El elemento que lo precede se denominará pivot.

2.

Incrementamos el pivot en una unidad

3.

Completamos la r -combinación con los números consecutivos al pivot.

Así, 12789 (una 5-combinación de los números del 1 al 9) tiene por sufijo detectado en el primer paso a 789; el pivot será 2. Incrementamos dicho número y completamos con los números que siguen al 3 para obtener 13456 como siguiente 5-combinación en orden lexicográfico. Ahora, el sufijo que seleccionaríamos es vacío (puesto que el número no acaba en n = 9); por lo tanto, el pivot es 6, y basta incrementarlo para obtener la siguiente combinación en orden lexicográfico, 13457. Y así sucesivamente: 12789 13456 13456 13457 13458

13458 13459 13467 13468 13469

hasta llegar a 56789, que sería la última.

1.7. El principio de inclusión-exclusión Existen situaciones en las que el principio de la suma no es aplicable, porque los conjuntos involucrados no son disjuntos. En casos así, resulta útil el siguiente teorema, que permite calcular el cardinal de la unión de una familia de conjuntos finitos aunque no sean disjuntos dos a dos. Teorema 11. (Principio de inclusión-exclusión) Si A 1 , A2 , . . . , An es una colección 15

de conjuntos finitos, se verifica que |A1 ∪ A2 ∪ · · · ∪ An | = +

X

1≤i< j
X

1≤i≤n

|Ai | −

X

1≤i< j≤n

|Ai ∩ A j |

|Ai ∩ A j ∩ Ak | − · · · + (−1)n+1 |A1 ∩ A2 ∩ · · · ∩ An |

(1.11)

Demostración. Supongamos que un cierto elemento a ∈ A 1 ∪ A2 ∪ · · · ∪ An pertenece exactamente a r de los n conjuntos Ai . Es fácil ver que dicho elemento contribuirá r unidades al primer¡ sumando de la expresión 1.11. Del mismo modo, al segundo ¢ sumando contribuirá r2 unidades, puesto que a se halla presente en todos los A i ∩ A j que podemos formar escogiendo i, j entre los r índices de los A i en que a se halla presente. Concluimos razonando análogamente para los sumandos siguientes que, si a ∈ A1 ∪ A2 ∪ · · · ∪ An pertenece a exactamente r de los conjuntos A i , su contribución a la suma total de 1.11 es µ ¶ µ ¶ µ ¶ µ ¶ r r r r − + − · · · + (−1)r r 1 2 3 Del teorema del binomio deducimos que µ ¶ µ ¶ µ ¶ µ ¶ µ ¶ r r r r r r − + − + · · · + (−1) = (1 − 1)r = 0 0 1 2 3 r por lo que la contribución indicada es igual a la unidad. Entonces, cada elemento de la unión contribuye en una unidad a la suma de arriba, y entonces su valor será |A 1 ∪ A2 ∪ · · · ∪ An |. El principio de inclusión-exclusión recibe este nombre del método que usa para contabilizar elementos: al sumar |A 1 |+|A2 |+· · ·+|An |, los miembros de los conjuntos de la forma Ai ∩ A j están siendo contabilizados por duplicado. Por lo tanto, tenemos que descontarlos de esa suma, lo que explica la aparición del sustraendo −|A 1 ∩ A2 | − · · · − |An−1 ∩ An |, que involucra todos los pares de conjuntos aludidos. Ahora bien, al hacer esto estamos (indebidamente) sustrayendo una vez más todos los miembros de intersecciones Ai ∩ A j ∩ Ak , por lo que volvemos a contabilizarlos añadiendo los sumandos |A1 ∩ A2 ∩ A3 | + · · · + |An−2 + An−1 + An |. Y se prosigue así, sumando y restando hasta llegar al último termino. Ejemplo 5. ¿Cuántas permutaciones del conjunto X = {1, 2, 3, . . . , n} mueven todos los elementos del conjunto a una posición diferente de la original? Podemos resolver este problema del modo siguiente. Consideremos el conjunto A formado por todas las permutaciones de los n elementos: claramente, |A| = n!. De éstas, consideremos la clase de las permutaciones que dejan al elemento 1 en primera posición; llamemos a esta clase A 1 , y, análogamente, definamos A k como la clase de las permutaciones en que el número k queda fijo, ocupando la k-ésima posición. Como cada permutación de A1 involucra reordenar solamente los n − 1 elementos restantes, tenemos que |A1 | = (n − 1)!, y análogamente para cada A k . Por otra parte, el conjunto Ai ∩ A j está formado por permutaciones en que escogemos la posición de i y j, de manera que tenemos (n − 2)! permutaciones posibles. En general |Ai1 ∩ Ai2 ∩ · · · ∩ Aik | = (n − k)! 16

es decir, cada conjunto de permutaciones que fija al menos k elementos contiene (n − k)! permutaciones posibles. Aplicando entonces la fórmula 1.11: |A1 ∪ A2 ∪ · · · ∪ An | = µ ¶ µ ¶ µ ¶ n n n+1 n n(n − 1)! − (n − 2)! + (n − 3)! + · · · + (−1) (n − n)! 2 3 n ¡ ¢ puesto que el número de sumandos de cada término de (1.11) es nk . Ahora, la suma anterior se simplifica considerablemente expandiendo los coeficientes binomiales por medio de su forma factorial: n! n! n! (n − 1)! − (n − 2)! + (n − 3)!− 1!(n − 1)! 2!(n − 2)! 3!(n − 3)! n! n! − (n − 4)! + · · · + (−1)n+1 0! = 4!(n − 4)! n!0! n! n! n! n! = − + − · · · + (−1)n+1 1! 2! 3! n! Esta es la expresión del número de permutaciones que fijan algún elemento. Como queremos calcular exactamente lo contrario, obtenemos |A − (A1 ∪ A2 ∪ · · · ∪ An )| = n!

µ

1 1 1 1 − + − · · · + (−1)n 2! 3! 4! n!

¶

(1.12)

Lo sorprendente de este resultado es que el factor entre paréntesis es, con una aproximación muy elevada, igual a 1/e = 0,3678, siendo e la base de los logaritmos neperianos. La aproximación es tan buena que podemos escribir Dn ≈

n! e

siendo la fórmula exacta si redondeamos el cociente al entero más próximo. Por ejemplo, para n = 8, obtenemos 8!/e = 14832,899, siendo Dn = 14833. La letra D proviene del término derangements, que es como se denomina en la literatura anglosajona a este tipo de permutaciones que no dejan fijo ningún elemento. Ejemplo 6. Encontrar el número de soluciones enteras no negativas de la ecuación x1 + x 2 + x 3 = 12

(1.13)

sometidas a la restricción x 1 < 6, x 2 < 4. Consideremos los siguientes conjuntos: A = {(x 1 , x 2 , x 3 ) | x1 + x 2 + x 3 = 12, xi ≥ 0} A1 = {(x 1 , x 2 , x 3 ) ∈ A | x 1 ≥ 6} A2 = {(x 1 , x 2 , x 3 ) ∈ A | x 2 ≥ 4}

(1.14) (1.15) (1.16)

de donde A12 = A1 ∩ A2 = {(x 1 , x 2 , x 3 ) ∈ A | x 1 ≥ 6 y x 2 ≥ 4} 17

(1.17)

F G H I J 3 + ∗ 5 + 6 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 χ (C7 ) = 3 χ (esto) = 4 χ (esto otro) = 4

A A − A1 − A2 x1 < 6, x 2 < 8 A2 x2 ≥ 8

A1 x1 ≥ 6 A12

x1 ≥ 6, x 2 ≥ 8 Figura 1.2: Representación esquemática del ejemplo 6 Podemos representar esquemáticamente la situación indicada por medio de la figura 1.2. Las soluciones que se nos exige contabilizar son las que no se encuentran ni en A1 ni en A2 ; es decir, tenemos que calcular el cardinal |A− A 1 − A2 | = |A|−|A1 ∪ A2 |. El último término se evalúa por medio del principio de inclusión-exclusión: |A1 ∪ A2 | = |A1 | + |A2 | − |A1 ∩ A2 | Como µ ¶ µ ¶ 14 14 |A| = CR(3, 12) = = = 91 12 2 µ ¶ µ ¶ 8 8 |A1 | = CR(3, 12 − 6) = = = 28 6 2 µ ¶ µ ¶ 10 10 = 45 = |A2 | = CR(3, 12 − 4) = 2 8 µ ¶ 4 |A12 | = CR(3, 12 − 6 − 4) = =6 2

(1.18) (1.19) (1.20) (1.21)

tenemos finalmente |A − A1 − A2 | = |A| − |A1 | − |A2 | + |A1 ∩ A2 | = 91 − 28 − 45 + 6 = 24.

18

Capítulo 2

Grafos 2.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 6∈ A y decimos, análogamente, que x no pertenece 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, y el símbolo ⊂ se reserva para la inclusión propia, que ocurre cuando A ⊆ B pero A 6= 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 denotarse convenientemente 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|.

2.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ón conjuntista 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. 19

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 casi seguramente 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.

2.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) ∈ R se 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 6 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ía todas 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 6 | 31. La relación inversa de ésta también tiene un nombre común: “ser múltiplo de”.

2.1.3.

Propiedades de las relaciones

Hay cuatro propiedades de una relación que nos van a interesar especialmente: que sea reflexiva, simétrica, transitiva o antisimétrica. Discutiremos primero el significado de las definiciones y daremos al final un resumen formal de las mismas. Decimos que una relación R es reflexiva si a R a para todo miembro a del dominio de R. Por ejemplo, la igualdad = y el orden ≤ son relaciones reflexivas. También lo es la relación “vivir en el mismo domicilio”. Una relación R es simétrica si para todo par de elementos a, b del dominio de R se verifica que, si a R b, entonces b R a. Por ejemplo, “ser hermano de” es una relación simétrica (es muy difícil ser hermano de alguien sin que éste sea hermano de uno), lo mismo que “estar casado con”. También la igualdad = entre números reales es una relación simétrica; sin embargo, el orden ≤ no lo es. De modo más interesante, 20

“x ama a y” (comoquiera que se defina) no es una relación simétrica: un amor no tiene por qué ser correspondido (aunque puede serlo). Basta con que haya un solo amor no correspondido para que esta relación deje de ser simétrica. Tampoco es simétrica la paternidad entre seres humanos: x es padre de y no implica que y sea padre de x (de hecho, en general, lo impide). Notemos la diferencia entre la paternidad y el amor: mientras que “x ama a y” no implica el recíproco, no lo impide (y puede amar a x). En cambio, la paternidad difícilmente puede ser recíproca en ningún caso: si x es padre de y, no es posible que y sea padre de x. Decimos que una relación R es antisimétrica si, para cualquier par de miembros a, b del dominio, a R b y b R a se dan simultáneamente sólo cuando a = b. Por último, otra propiedad muy importante es la transitividad. Decimos que R es transitiva si para cualquier terna a, b, c de miembros del dominio, las relaciones a R b y b R c obligan necesariamente a que a R c. Por ejemplo, si R es la relación de amistad entre seres humanos, es bastante evidente que no es transitiva: a puede ser amigo de b y b puede serlo de c, mientras que a puede considerar a c muy poco recomendable. Si R fuese transitiva, sería cierto el refrán “los amigos de mis amigos son mis amigos”. Sí es transitiva, en cambio, la relación “ser antepasado de”: los antepasados de mis antepasados son mis antepasados. En cambio, la paternidad no lo es: si x es el padre de y e y es el padre de z, esto no obliga en absoluto a que x sea el padre de z. Resumiendo, si R es una relación binaria en el conjunto A, decimos que R es reflexiva si a R a, para todo a ∈ A simétrica si a R b → b R a, para todos a, b ∈ A transitiva si a R b y b R c → a R c, para todos a, b, c ∈ A antisimétrica si a R b y b R a → a = b, para todos a, b ∈ A Una relación R se dice que es una relación de equivalencia si es reflexiva, simétrica y transitiva. El ejemplo por excelencia es la igualdad, pero existen otros ejemplos significativos. Por ejemplo, la relación “ser hermano de” es una relación de equivalencia, si admitimos el hecho de que uno es hermano de sí mismo. Dado un elemento a ∈ A del dominio de una relación de equivalencia R, se define su clase de equivalencia como el conjunto [a] = {x ∈ A | a R x}, es decir, el conjunto de los elementos relacionados con a en virtud de R. En el ejemplo anterior, R = “ser hermano de”, la clase de equivalencia de un individuo es el conjunto de todos sus hermanos (incluyéndolo a él mismo). Obsérvese que las clases de equivalencia de esta relación son las progenies de cada familia, y toda la humanidad está dividida en clases disjuntas de hermanos. Este hecho no es casual. La propiedad más importante de las relaciones de equivalencia la proporciona el siguiente Teorema 12. Sea R una relación de equivalencia en un conjunto A. Las clases de equivalencia de R forman una partición de A, es decir, A es la unión de dichas clases de equivalencia, y dos clases de equivalencia son o iguales o disjuntas. Demostración. Obviamente, cada elemento a ∈ A es miembro de una clase de equivalencia: la suya propia. Ello es así porque la relación es reflexiva, de modo que a R a y, por tanto, a ∈ [a]. Se deduce que A ⊂ ∪a∈A [a], es decir, A es unión de clases de equivalencia. 21

Por otro lado, sean [x] e [y] dos clases de equivalencia. Si no son disjuntas, existe un elemento común a ∈ [x] ∩ [y]. Se deduce que a R x y que a R y

(pertenencia a [x] e [y])

x R aya R y x Ry

(simetría) (transitividad)

x Rzyx R y

(definición de [x])

Por tanto, si z ∈ [x] z Rxyx R y z R y, o sea, y R z z ∈ [y]

(simetría) (transitividad y simetría) (definición de [y])

y se concluye que [x] ⊂ [y]. Se prueba del mismo modo que [y] ⊂ [x], y por tanto, que [x] = [y]. Otro tipo de relación de especial interés es la relación de orden (parcial). Se llama así a una relación que es reflexiva, antisimétrica y transitiva. Como ejemplos típicos de relaciones de orden tenemos la relación ≤ entre números reales, o la relación de divisibilidad entre números naturales (“ser divisor de”, denotada por |). Esta última es relación de orden, puesto que para todo entero a, se verifica que a|a (reflexividad) para todo par de enteros a, b, se verifica que si a|b y b|a, entonces existen números k y l con a = kb = kla y kl = 1, de forma que a = b (antisimetría) para todo trío de enteros a, b, c, si se dan las relaciones a|b y b|c, existen ciertos naturales k y l que cumplen c = kb = kla, de modo que a|c (transitividad) La divisibilidad es un buen ejemplo de una relación de orden parcial. En un orden parcial R no es preciso que una de las dos relaciones a R b o bien b R a se dé. Por ejemplo, ni 7|69 ni 69|7. Se dice que los elementos en cuestión no son comparables. Una relación de orden en la que para todo par de elementos a, b del dominio se verifica que a R b o bien b R a (o ambas) se dice que es de orden total. La relación de orden habitual entre números, ≤, es un ejemplo de orden total. Una representación muy conveniente de las relaciones de orden en conjuntos finitos es su diagrama de Hasse, que definiremos en la sección 2.3.

2.1.4.

Clausura transitiva

Vimos en la sección 2.1.3 que la relación “ser ancestro de” es transitiva, pero la paternidad no lo es: el padre de mi padre no es mi padre (suele denominarse abuelo mío). Sin embargo, existe una vinculación interesante entre la paternidad y la ancestralidad: los antepasados se obtienen, por lo general, remontándose hacia atrás una o más veces en la relación de paternidad (un ancestro mío es, o bien mi padre, o bien el padre de mi padre, o el padre de mi padre de mi padre, etc.) Del mismo modo, la relación “ser sucesor de” definida sobre el conjunto de los enteros no es transitiva: 5 es el sucesor de 4, y 6 es el sucesor de 5, pero 6 no es sucesor de 4. Como mucho, es mayor que cuatro, y esta relación de orden sí que es transitiva. 22

La relación transitiva que se obtiene por repetición a partir de otra aparece con frencuencia, lo que motiva la siguiente definición. Sea R una relación en un conjunto A. Definimos la clausura transitiva de R (a veces denotada por R ∗ ) como la menor relación transitiva que contiene a R. Más explícitamente, a) R ⊂ R ∗ ⊂ A × A (es decir, R ∗ es una relación binaria en A). b) R ∗ es transitiva. c) Si R ⊂ S ⊂ R ∗ ⊂ A × A y además S es transitiva, entonces S = R ∗ . Esta definición es muy poco intuitiva, y generalmente utilizaremos esta otra: diremos que a R ∗ b si existe una sucesión {ai } de elementos de A que verifica a R a1 R a2 R a3 R · · · R a n R b es decir, si a está relacionado con un elemento, que está relacionado con otro, que. . . y así sucesivamente hasta llegar a b. Por ejemplo, la clausura transitiva de la relación de paternidad es “ser antepasado de”.

2.2. Grafos 2.2.1.

Grafo dirigido y no dirigido

Definición 4. Un grafo (específicamente, grafo simple no dirigido) es un par G = (V, E) = (V (G), V (E)), donde V es un conjunto finito no vacío de elementos llamados vértices y E es un conjunto de pares desordenados de elementos distintos de V llamados aristas. Es decir, una arista e ∈ E tiene la forma {u, v}, donde u, v ∈ V y u 6= v. La terminología en teoría de grafos varía muchísimo: prácticamente no hay dos textos que adopten la misma. En paticular, los vértices de un grafo también reciben a veces el nombre de nodos, y las aristas arcos, ejes o líneas. Obsérvese que, en un grafo no dirigido conforme con esta definición, los bucles están excluídos. Por convenio, en grafos no dirigidos designaremos las aristas con la notación (u, v) que usamos para los pares ordenados de vértices; se sobreentiende que en las aristas de grafos no dirigidos no importa el orden, es decir, (u, v) = (v, u). Un grafo se representa por medio de puntos o círculos, que designan los vértices, y líneas que los unen, que representan las aristas. Por ejemplo, en la figura 2.1(b) tenemos un ejemplo de grafo no dirigido con conjunto de vértices V = {1, 2, 3, 4, 5, 6} y aristas E = {(1, 2), (2, 5), (1, 5), (3, 6)}. Definición 5. Un grafo dirigido o digrafo G es un par (V, E), donde V es un conjunto finito no vacío y E es una relación binaria en V , es decir, un conjunto de pares ordenados de elementos de V . Los elementos de V reciben el nombre de vértices. El conjunto E es el conjunto de aristas de G. Por ejemplo, en la figura 2.1(a) tenemos un grafo dirigido que, de acuerdo con la definición, tiene seis vértices (V = {1, 2, 3, 4, 5, 6}) y ocho aristas (E = {(1, 2), (2, 2), (2, 4), (2, 5), (4, 1), (4, 5), (5, 4), (3, 6)}). Las flechas apuntan del primer elemento de cada par al segundo. 23

∗ 5 + 6 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 χ (C7 ) = 3 χ (esto) = 4 χ (esto otro) = 4 x1 ≥ 6 x2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 1 x1 < 6, x 2 < 8 A2 A1 A − A1 − A2 A12 4

∗ 5 + 6 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 χ (C7 ) = 3 χ (esto) = 4 χ (esto otro) = 4 x1 ≥ 6 x2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 3 2 1 x1 < 6, x 2 < 8 A2 A1 A − A1 − A2 5 6 A12 4 (a)

2

3

5

6

(b)

Figura 2.1: Ejemplos de (a) grafo dirigido, y (b) no dirigido Tipo de grafo Grafo Multigrafo Pseudografo Grafo dirigido (digrafo) Multigrafo dirigido

Dirigido No No No Sí Sí

Simple Sí No No Sí No

Lazos No No Sí Sí Sí

Cuadro 2.1: Cadro resumen de los diferentes tipos de grafos

Obsérvese que es posible que una arista puede partir de un vértice y llegar a él de nuevo. Una arista de esta clase, es decir, de la forma e = (v, v), recibe el nombre de bucle o lazo. Cuando el sentido de las flechas no nos interesa (o, dicho de forma más técnica, la relación que el grafo representa es simétrica), es más conveniente el concepto de grafo no dirigido. Existen numerosas variantes de las definiciones que acabamos de dar. Por ejemplo, un multigrafo es un grafo no dirigido en el que permitimos la existencia de varias aristas conectando los mismos vértices y la aparición de bucles. Específicamente, un multigrafo queda definido por medio de una tríada G = (V, E, f ), donde V y E son conjuntos y f : E → V × V asigna a cada arista e ∈ E un par desordenado f (e) = {u, v} de vértices diferentes de V (los vértices extremos de la arista e). Un multigrafo dirigido se define de forma exactamente igual, excepto que el recorrido de f está formado por pares ordenados de vértices. Por último, si permitimos la existencia de bucles o lazos en un grafo no dirigido, tenemos un pseudografo: se trata de una terna G = (V, E, f ), donde f : E → V × V asigna a cada arista un par no ordenado de vértices (posiblemente iguales). Dado que esta terminología no es estándar, siempre es conveniente en cada caso especificar claramente si el grafo objeto de nuestra consideración es dirigido o no; si se admiten múltiples aristas entre un par cualquiera de vértices (es decir, si el grafo es o no simple); y si se admiten bucles o lazos. En el cuadro resumen 2.1 se esquematizan los valores de estos parámetros para las definiciones recién dadas.

2.2.2.

Incidencia y grado

Si (u, v) es una arista de un grafo dirigido, decimos que incide desde o sale de el vértice u, que será su vértice inicial, y que incide hacia o entra en el vértice v, que será 24

su vértice final. Si estamos en un grafo no dirigido, decimos que (u, v) simplemente incide en los vértices u y v, que serán sus vértices extremos. Por ejemplo, en la figura 2.1(a), hay tres aristas que salen del vértice 2: son (2, 2), (2, 4) y (2, 5). En el grafo no dirigido de la figura 2.1(b), la arista (3, 6) incide en los vértices 3 y 6. Si (u, v) es una arista de un grafo, decimos que el vértice v es adyacente al vértice u. En un grafo no dirigido, la relación de adyacencia es simétrica; no es así necesariamente en un digrafo. Por ejemplo, en la figura 2.1(a), el vértice 5 es adyacente al 2 (pero el 2 no es adyacente al 5). En cambio, en el grafo de la figura 2.1(b), los vértices 1 y 2 son adyacentes entre sí. El grado de un vértice en un grafo no dirigido es número de aristas incidentes con él. Por ejemplo, el vértice 5 de la figura 2.1(b) tiene grado 2. En un digrafo, el grado de salida de un vértice es el número de aristas que salen de él, y el grado de entrada es el número de aristas que entran en él. El grado es la suma de los grados de salida y entrada. En el grafo dirigido de la figura 2.1(a), el vértice 2 tiene grado de salida 3, grado de entrada 2 y grado 5.

2.2.3.

Representación como estructuras de datos

Nuestro interés en los grafos radica en su aplicación a la informática, y exige que podamos representarlos en nuestros programas como estructuras de datos que podamos manejar, crear, modificar y consultar. Existen tres representaciones usuales de los grafos que permiten su manipulación como objetos en nuestros programas: las representaciones por medio de matrices de adyacencia, de listas de adyacencia y de matrices de incidencia. En la representación por matrices de adyacencia, un grafo G = (V, E) cuyo conjunto de vértices sea V = {a1 , a2 , . . . , an } se representa por una matriz booleana M, cuadrada, de dimensión igual al número de vértices n, y cuyos elementos se definen por ( 1 si (ai , a j ) es una arista de G Mi j = 0 en caso contrario Es decir, la matriz M representa la relación de adyacencia. Habrá un uno en la fila i, columna j, si hay una arista que va del vértice ai al vértice a j . Obsérvese que la matriz no será simétrica, en general, si el grafo es dirigido. En cambio, la matriz de adyacencia de un grafo no dirigido siempre será simétrica. Las aristas múltiples no quedan bien representadas en la matriz de adyacencia, pero sí los bucles o lazos, que provocan la presencia de unos en la diagonal principal. Para el grafo de la figura 2.1(a), la matriz de adyacencia se representa en la figura 2.2(a). La representación por matrices de adyacencia tiene un inconveniente serio para grafos grandes: el tamaño de la matriz es proporcional al cuadrado del número de vértices. Si el número de aristas |E| es comparativamente pequeño en relación a |V | 2 , se desperdicia una cantidad enorme de espacio. La mayoría de los grafos se encuentra en este caso: son grafos dispersos, donde |E| ¿ |V |2 . La representación por listas de adyacencia es mucho más conveniente en esta mayoría de casos. Un grafo G = (V, E) se representará por un vector de listas. El vector tiene |V | posiciones, una por cada vértice; en la posición i-ésima se almacena la lista de los vértices adyacentes a ai . En la figura 2.2(b) representamos el grafo de la figura 2.1(a) por medio de listas de adyacencia. 25



0 1 0 1  0 0 M= 1 0  0 0 0 0

0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 0

 0 0  0  0  0 0

Vértice 1 2 3 4 5 6

Adj(V ) {2} {2, 4, 5} {} {1, 5} {4} {3} (b)

(a)

Figura 2.2: Representación del grafo de la figura 2.1(a) por medio de a) matriz de adyacencia b) listas de adyacencia

Podemos ver que el tamaño de esta representación es proporcional al número |E| de aristas del grafo. Esto lo hace mucho más conveniente en casi todos los casos. Solamente en el caso de grafos densos (en los que |E| y |V |2 son comparables) es razonable considerar la matriz de adyacencia como representación alternativa. La matriz de incidencia de un grafo G = (V, E), donde |V | = n y |E| = m se define como una matriz booleana n × m en la que (Minc )i j =

(

1 0

si la arista j incide en el vértice i en caso contrario

Esta representación es solamente válida para grafos no dirigidos, puesto que el sentido de las aristas no puede ser representado de esta forma. Puede resultar útil para representar multigrafos, pero su interés fundamental es más bien teórico.

2.2.4.

Caminos y ciclos

Un camino de longitud k entre el vértice u y el vértice u 0 del grafo G = (V, E) es una sucesión de aristas {e1 , e2 , . . . , ek } tales que ei = (vi−1 , vi ) para i = 2, 3, . . . , k, con lo que cada arista tiene por vértice inicial el vértice final de la anterior. Para hacer explícito este hecho, a veces un camino se denota también con los vértices intercalados: C = {v0 , e1 , v1 , . . . , en , vn }. Si no hay ambigüedad, un camino puede denotarse exclusivamente por la sucesión de vértices que visita: C = {v0 , v1 , . . . , vk }. Esto puede hacerse, por ejemplo, cuando los grafos con los que trabajamos son simples. La longitud del camino, según la definición dada arriba, es el número de aristas que lo constituyen. El vértice inicial de C = {v0 , e1 , . . . , ek , vk } es v0 , y el vértice final es vk . Un camino es simple si todas sus aristas son distintas. En ocasiones se llama simple a un camino que no visita dos veces el mismo vértice. La segunda definición es más restrictiva que la primera, puesto que un camino puede pasar dos veces por un mismo vértice sin visitar ninguna arista más de una vez. Un camino (v0 , e1 , v1 , . . . , ek , vk ) forma un ciclo si v0 = vk y el camino contiene al menos una arista. El ciclo es simple si, además, las aristas que lo forman son todas distintas. Por ejemplo, un lazo es un ciclo de longitud unidad. 26

G H I J 3 + ∗ 5 + 6 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 χ (C7 ) = 3 χ (esto) = 4 χ (esto otro) = 4 x1 ≥ 6 x2 ≥ 8 4 x1 ≥ 6, x 2 ≥ 8 x1 < 6, x 2 < 8 A2 A1 A − A1 − A2 A12

G H I J 3 + ∗ 5 + 6 12 χ (K 5 ) = 5 36 χ (K 3,3 ) = 2 χ (C7 ) = 3 12 18χ (esto) = 4 χ (esto otro) = 4 x1 ≥ 6 9 x2 ≥ 8 6 x1 ≥ 6, x 2 ≥ 8 x1 < 6, x 2 < 8 A2 3 2 A1 A − A1 − A2 3 1 A12

6

4

(a)

9

(b)

Figura 2.3: (a) Retículo de divisores de 36 y (b) Relación de orden entre 3, 4, 6, 9

2.3. Relaciones y grafos Existe una conexión muy íntima entre las relaciones binarias en un conjunto y los grafos. De hecho, hemos definido un grafo dirigido como una relación, y el uso que hacemos de los grafos en informática es para representar relaciones. Sea A un conjunto finito y R una relación binaria de dominio A. Al ser A finito, podremos enumerar sus elementos: A = {a1 , a2 , a3 , . . . , an } Definimos el grafo asociado a R (o grafo que representa R) como un grafo cuyos vértices son los elementos de A, siendo (ai , a j ) una arista del grafo si y solamente si ai R a j . De hecho, según la definición de digrafo que dimos en la sección 2.1(b), la propia relación es un grafo. Como ejemplo, consideremos la relación binaria R definida entre números enteros como sigue a R b si y solamente si b = pa con p primo y estudiemos su restricción al conjunto A = {1, 2, 3, 4, 6, 9, 12, 18, 36} formado por los divisores de 36. El grafo asociado a la relación será el que se muestra en la figura 2.3(a). En cambio, el grafo de la relación ≤ entre los números {3, 4, 6, 9} puede verse en la figura 2.3(b). Algunas propiedades de estas relaciones son directamente observables a partir del grafo. Por ejemplo, en ninguna de las figuras encontramos flechas dirigidas en sentidos contrarios entre ningún par de nodos. Esto se debe a que las relaciones representadas son antisimétricas. La relación de orden de la figura 2.3(b) es, además, obviamente reflexiva: la presencia de un bucle o lazo en todos y cada uno de los nodos lo prueba. Observemos que 2 R 6 y que 6 R 12, pero que, sin embargo, 2 6 R 12. Esto se debe a que la relación R no es transitiva. En cambio, ≤ sí es una relación transitiva; veremos enseguida en qué se traduce esto en términos de grafos. 27

Un ejemplo de grafo que se vincula a una relación de manera algo diferente es el diagrama de Hasse de una relación de orden. El diagrama de Hasse se obtiene representando la relación por un grafo, y suprimiendo todos los lazos todas las aristas que se puedan deducir por transitividad de otras dos En la figura 2.3(a) tenemos un ejemplo de un tal diagrama para la relación de divisibilidad en el conjunto de los divisores de 36. La matriz de adyacencia del grafo asociado a una relación R se denomina simplemente matriz de la relación; es una matriz cuadrada binaria M R , de dimensión igual al cardinal del dominio de R. El elemento (M R )i j de la matriz vale uno o cero según que los elementos ai y a j estén relacionados o no. En símbolos, ( 1 si ai R a j (M R )i j = 0 en caso contrario Veamos cómo se plasman en términos de grafos y de matrices de relaciones las cuatro propiedades estudiadas en 2.1.3. reflexividad R es reflexiva sii a R a para todo a ∈ A. Por lo tanto, si cada vértice del grafo posee un lazo, R es reflexiva; si algún vértice carece de lazo, la relación no es reflexiva. En términos de matrices, cada elemento de la diagonal principal de M R debe ser un uno. simetría R es simétrica sii a R b ⇒ b R a, para todo par de a, b ∈ A. Por lo tanto, si hay una flecha de un vértice v a otro w, la flecha contraria también debe estar presente; y si no la hay en un sentido, la contraria tampoco puede existir. En términos matriciales, (M R )i j = (M R ) ji para todo par de índices i, j; o, más brevemente, M R es simétrica: M Rt = M R transitividad R es transitiva si y solamente si a R b junto con b R c implica necesariamente que a R c. En términos de grafos, la existencia de una arista entre los vértices a, b y otra entre b, c implica la existencia de la arista (a, c). El par de aristas (a, b), (b, c) forma un camino de longitud dos entre los vértices a y c, de modo que la condición de transitividad puede formularse así: la accesibilidad de orden dos implica adyacencia. En términos matriciales, (M R )i2j = 1 implicará siempre que (M R )i j = 1 o, abreviando, M R2 ⊂ M R : elevar al cuadrado la matriz de la relación no introduce unos que no existieran ya en M R .

2.4. Accesibilidad y conexión Decimos que un vértice u 0 de un grafo es accesible (o alcanzable) desde otro vértice u si existe un camino de u a u 0 . Es fácil ver que la relación de accesibilidad es transitiva: si w es accesible desde v y v es accesible desde u, es evidente que w es accesible desde u. Además, todo nodo es accesible desde sí mismo (por medio de un camino de longitud cero). En un grafo no dirigido, la relación también es simétrica; en un digrafo ya no tiene por qué ser así (en la figura 2.1(a), el vértice 3 es accesible desde 6, pero no al contrario). 28

Propiedad

Definición

Reflexiva

∀a

29

Simétrica Antisimétrica Transitiva

∀a, b ∀a, b

∀a, b, c

a R a R a R a R

Cazorla Bastardo Lebrel Guzmán Dehesa Cobas Zapatero Herrero González Cazorla Zorrilla Lebrel Guzmán Dehesa Zapatero Herrero A González B Lebrel C Zorrilla Guzmán Zapatero A D Herrero B E Lebrel Zorrilla C Zapatero A F D B G Zorrilla E C A F HI D B G E C H F J3 D GI + E H FJ3 ∗ I 5 G + J∗ + H I3 6 + J5 12 + χ (K 5 )3∗ 56= 5 + χ (K 3,3 )12 =2 + ∗ χ (Kχ5(C )= 6= 3 7 )55 +2= 4 χ (Kχ3,3 ) =12 (esto) χχ(K )) = (C57otro) =12653= 4 χχ(esto = 42 3,3 ) = χχ(K (esto) x153≥ 6 χ(K (C57)) = = χ (esto otro) = x224≥ 8 χχ(K ) = 3,3 = ≥ xχ1(esto) ≥ 7x6, x 2 346≥ 8 1= (C ) χ (esto otro) = < x6, x≥2 448< 8 χx≥1(esto) x221 = ≥ 68 A2 x 6, 1 χ (esto ≥ 48 AGrafo x1 < otro) 6, xx22 = < 1 x1 ≥A6,−x1A ≥A 2≥ −6882 A2 1 x ≥ x < 6, < 8 2 1 2 A a x1A≥−6,Ax1 2−≥A8212A12 x < 6, x 81 1 2 AA12 b ⇒ b R Aa − A −< AA22 1 1 b y b R a ⇒ a = bAA12 A − A1 − A2 b y b R c ⇒ a R cA12

Matriz (M R )ii = 1 M Rt

∀i

= MR (M R )i j 6= (M R ) ji M R2

⊂ MR

Cuadro 2.2: Cuadro resumen de las propiedades de las relaciones

∀i 6= j

Un grafo no dirigido es conexo si cada par de vértices está conectado por un camino (es decir, todos los vértices son mutuamente accesibles). Las componentes conexas de un grafo son las clases de equivalencia de los vértices bajo la relación de accesibilidad. El grafo de la figura 2.1(b) no es conexo, ya que, por ejemplo, 6 es inaccesible desde 1. Hay tres componentes conexas en el grafo: {1, 2, 5}, {3, 6} y {4}. En una componente conexa, todos los vértices son mutuamente accesibles; es evidente, por tanto, que un grafo es conexo si y solamente si tiene una única componente conexa. Intuitivamente, las componentes son los diferentes “trozos” conexos en que el grafo se descompone. Un grafo dirigido es fuertemente conexo si cualquier vértice es accesible desde cualquier otro. Las componentes fuertemente conexas de un digrafo son las clases de equivalencia de los vértices bajo la relación “ser mutuamente accesibles”. Es algo menos intuitivo visualmente el extraer las componentes fuertemente conexas de un digrafo. Por ejemplo, en el grafo de la figura 2.1(a), tenemos tres componentes: {1, 2, 4, 5}, {3} y {6}. Los cuatro vértices que residen en la primera componente son mutuamente accesibles entre sí (basta usar el ciclo (1, 2, 5, 4) para desplazarse de un vértice a otro); pero 3 y 6 no son mutuamente accesibles (solamente 3 es accesible desde 6, pero no a la inversa), y por consiguiente residen en componentes distintas.

2.4.1.

Matrices de accesibilidad

De manera análoga a como hicimos en el epígrafe anterior, podemos decir que un vértice v es accesible de orden k desde otro vértice u, si existe un camino de longitud k exactamente que tiene a u por vértice inicial y a v por vértice final. De forma trivial, un vértice v0 es accesible de orden cero desde sí mismo, puesto que el camino de longitud cero {v0 } satisface la definición. También es evidente la equivalencia v accesible desde u ⇔ ∃k ≥ 0 | v accesible desde u

(2.1)

Las definiciones anteriores establecen una serie de relaciones binarias en el conjunto V (G) de los vértices de un grafo G: la accesibilidad pura, y las accesibilidades de órdenes k = 0, 1, 2, . . . . Cada una de estas relaciones binarias da lugar a una matriz de accesibilidad que la representa. Definimos detalladamente estas matrices a continuación. Definición 6. Sea G un grafo con n nodos. La matriz de accesibilidad de G se define como la matriz binaria Macc de dimensión n × n cuyos elementos vienen dados por ( 1 si v j es accesible desde vi (Macc )i j = 0 en caso contrario Definición 7. Sea G un grafo con n nodos. La matriz de accesibilidad de orden k de G se define como la matriz binaria Mk de dimensión n × n cuyos elementos vienen dados por ( 1 si v j es accesible de orden k desde vi (Mk )i j = 0 en caso contrario En algunos casos, las matrices de accesibilidad se definen, no como matrices binarias, sino como matrices de enteros, poniendo en lugar de un uno el número total de caminos existentes del tipo indicado. Si utilizamos ese convenio, nuestras matrices de 30

accesibilidad booleanas se obtienen a partir de las matrices enteras reemplazando por unos los enteros positivos, y dejando los ceros donde están. El paso inverso (de matriz booleana a entera) no es posible en general, puesto que al convertir a matriz booleana se pierde información. Es evidente que la matriz M1 coincide con la matriz de adyacencia que vimos en la sección 2.2.3. Como la accesibilidad de orden cero solamente se da entre vértices iguales, es también evidente que M0 = In , la matriz identidad n × n. En cuanto a otras matrices de accesibilidad de orden superior, no parece haber una forma inmediata de calcularlas. Para el grafo de la figura 2.1(a), puede comprobarse manualmente que     1 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 0  1 1 0 1 1 0      0 0 0 0 0 0  0 0 0 0 0 0     M = M2 =  3 1 1 0 1 1 0  0 1 0 1 0 0      0 1 0 1 0 0  1 0 0 0 1 0  0 0 0 0 0 0 0 0 0 0 0 0

pero las comprobaciones se vuelven muy engorrosas para órdenes mayores. Por fortuna, hay una fórmula algebraica muy simple que nos permite calcular de forma directa las matrices de accesibilidad de cualquier orden. Teorema 13. Para k ≥ 0,

Mk = M k

(2.2)

Demostración. Por inducción sobre el exponente k. Para k = 0, hemos visto que M0 = In = M 0 , y no hay nada que demostrar. De la misma forma, M1 = M = M 1 y se tiene el teorema trivialmente. Supongamos, pues, que la identidad (2.2) es cierta para k < l; vamos a probarla para k = l. Como tanto Ml como M l son matrices booleanas del mismo tamaño, lo único que es preciso probar es que coinciden elemento a elemento, es decir, que (Ml )i j = (M l )i j para cada 1 ≤ i, j ≤ n. Ahora bien, tenemos que (M l )i j = (M l−1 M)i j =

n X

(M l−1 )ik Mk j

(2.3)

k=1

Por hipótesis de inducción, M l−1 = Ml−1 , por lo cual l

(M )i j =

n X

(Ml−1 )ik Mk j

(2.4)

k=1

Ahora bien, la suma de 2.4 será la unidad solamente si existe algún valor del índice k para el que (Ml−1 )ik = 1 y Mk j = 1 La primera igualdad ocurre si y solamente si existe un camino de orden l − 1 entre vi y vk ; la segunda, si hay una arista que une a vk con v j . Por lo tanto (M l )i j = 1 ⇔ ⇔ ∃vk ∈ V (G)(vk accesible de orden l − 1 desde vi ∧ ∧ v j accesible de orden 1 desde vk ) ⇔ v j es accesible de orden l desde vi ⇔ (Ml )i j = 1 31

+ ∗ 5 + 6 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 χ (C7 ) = 3 χ (esto) = 4 χ (esto otro) = 4 x1 ≥ 6 x2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 x1 < 6, x 2 < 8 A2 A1 A − A1 − A2 A12

K5

K4

K6

Figura 2.4: Grafos completos de cuatro, cinco y seis vértices Con ayuyda del teorema recién probado, el cálculo de las diferentes matrices M k se reduce a simple potenciación de la matriz de conexión o adyacencia. El teorema siguiente nos da una forma sencilla de calcular Macc Teorema 14. Si G es un grafo de n vértices, Macc = I + M + M 2 + · · · + M n−1 Demostración. De la equivalencia 2.1 podemos deducir inmediatamente que Macc ⊇ I + M + M 2 + · · · + M n−1 es decir, que la matriz de la izquierda poseerá todos los unos que posee el lado derecho, y posiblemente alguno más. Nos bastará, pues, probar la inclusión contraria: (Macc )i j = 1

⇒

(I )i j + (M)i j + (M 2 )i j + · · · + (M n−1 )i j = 1

(2.5)

Ahora bien, el lado izquierdo de la ecuación 2.5 implica que existe un camino de cierta longitud m entre el vértice vi y el vértice v j . Sea dicho camino C = {v0 , e1 , v1 , e2 , v2 , . . . , em , vm } Tendremos vi = v0 como vértice inicial y v j = vm como final. Si m = |C| ≥ n, el número de vértices visitados por C es m + 1 > n, de manera que C tiene forzosamente que pasar dos veces por un mismo vértice. Es decir, existirán dos índices k, l con 0 ≤ k < l ≤ n y vk = vl . Si suprimimos la sección de C entre esos dos vértices, {vk , ek+1 , . . . , el }, obtenemos un camino nuevo C 0 cuya longitud es inferior a m y que sigue teniendo los mismos extremos. Por aplicación reiterada de este procedimiento, podemos llegar a un camino final que no visita más de n vértices, y que, por tanto, tiene longitud a lo sumo n − 1. El argumento anterior prueba que, si v j es accesible desde vi , lo es para algún orden k < n, de modo que (M k )i j = 1 para algún exponente k entre 0 y n − 1. Esto prueba que el lado derecho de la ecuación 2.5 tiene que ser igual a uno si lo es el izquierdo, que es lo que se precisaba demostrar.

2.5. Algunos grafos especiales 2.5.1.

Grafos completos

Un grafo completo es un grafo no dirigido en que todos los vértices son adyacentes entre sí. Para cada número de vértices n, existe esencialmente un solo grafo completo 32

H I J 3 + ∗ 5 + 6 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 χ (C7 ) = 3 χ (esto) = 4 χ (esto otro) = 4 x1 ≥ 6 x2 ≥ 8 3 x1 ≥ 6, x 2 ≥ 8 x1 < 6, x 2 < 8 A2 A1 A − A1 − A2 A12

1

2

4

6

5

Figura 2.5: Torneo de seis vértices (todos son isomorfos entre sí), que se designa por K n . Por ejemplo, en la figura 2.4 tenemos algunos grafos completos. ¡ ¢ Teorema 15. El grafo completo de n vértices K n tiene n2 = n(n − 1)/2 aristas. Hay varias formas de demostrar esto:

1.

El número de aristas de K n es el número de pares desordenados en un conjunto de n objetos, es decir, el de combinaciones de n elementos tomados de dos en dos.

2.

Cada vértice del grafo está unido a los n − 1 restantes. Si contamos las aristas incidentes en cada uno de los n vértices, obtenemos n(n − 1), pero, al obrar así, estamos contando cada arista dos veces (puesto que tiene dos extremos). Por tanto, el número total de aristas es exactamente la mitad, n(n − 1)/2.

3.

Numeremos los vértices de 1 a n. En el vértice 1 inciden n − 1 aristas: (1, 2), (1, 3), (1, 4), . . . (1, n) En el vértice 2 inciden también n − 1 aristas, pero una ya ha sido contada anteriormente, de modo que sólo aparecen aquí n − 2 nuevas: (2, 3), (2, 4), . . . (2, n) Si proseguimos así el recuento, llegamos a que el número total de aristas es la suma de una progresión aritmética: |E| = (n − 1) + (n − 2) + · · · + 2 + 1 = (n − 1)

(n − 1) + 1 2

De este ¡ ¢teorema deducimos que un grafo simple no dirigido de n vértices tendrá, a lo sumo, n2 aristas.

2.5.2.

Torneos

Un torneo (tournament) es un grafo dirigido cuya versión no dirigida es un grafo completo. Podemos decir que un torneo puede obtenerse a partir de un grafo completo 33

asignando orientaciones a cada una de las aristas. En la figura 2.5 podemos ver un ejemplo de torneo con seis vértices. En el torneo de la figura podemos ver que el camino simple (1, 2, 4, 6, 3, 5) pasa por todos los vértices. Un camino así se denomina camino hamiltoniano. En el teorema 21 veremos que siempre es posible encontrar uno en cualquier torneo.

2.5.3.

Grafos bipartitos

Un grafo bipartito es un grafo no dirigido G = (V, E) cuyo conjunto de vértices V es unión de dos conjuntos disjuntos V1 y V2 de forma que (u, v) ∈ E implica que, o bien u ∈ V1 y v ∈ V2 , o bien u ∈ V2 y v ∈ V1 . Es decir, todas las aristas tienen un extremo en cada uno de los conjuntos V1 y V2 . Recordemos que V1 y V2 forman una partición de V si son disjuntos y su unión es V . Teorema 16. Un grafo es bipartito si y solamente si carece de ciclos de longitud impar Demostración. Sea G bipartito y C = (v0 , v1 , . . . , vn ) un ciclo de G. Como cada arista (vi−1 , vi ) une un elemento de V1 con uno de V2 , se deduce que vértices consecutivos de C pertenecen a lados distintos de la partición, de forma que los vértices de subíndice par están todos en un lado y los de subíndice impar en el contrario. Como v0 = vn , se deduce que n tiene la misma paridad que 0, es decir, es par. Recíprocamente, supongamos que el grafo G carece de ciclos de longitud impar. En primer lugar, es obvio que bastará probar que cada componente de G es bipartita, así que podemos suponer G conexo. Sea v0 ∈ V (G) un vértice cualquiera, y definamos V1 = {v ∈ V (G) | existe un camino de longitud impar entre v0 y v}, y V2 = V − V1 . Por definición, los caminos entre v0 y cualquier vértice de V2 serán todos de longitud par. Además, V1 y V2 forman una partición de V . Ahora, si dos vértices v, w de V1 son adyacentes, los caminos de longitud impar que los unen con v0 , más las arista (v, w), constituyen un ciclo impar, contra la hipótesis. Por lo tanto, no hay ningún par de vértices adyacentes en V1 . Para V2 , el mismo razonamiento es válido, de forma que cualquier arista une algún vértice de V1 con alguno de V2 .

2.5.4.

Caminos y ciclos

El camino de longitud n es el grafo Pn = (V, E), donde V = {v0 , v1 , . . . , vn } y E = {(v0 , v1 ), (v1 , v2 ), . . . , (vn−1 , vn )}. El ciclo de longitud n es el grafo C n = (V, E), donde V = {v1 , . . . , vn } y E = {(vn , v1 ), (v1 , v2 ), . . . , (vn−1 , vn )}. En la figura 2.5.4 podemos ver ejemplos de estos complicadísimos conceptos.

2.5.5.

Grafos cúbicos Q n

Los grafos Q n son la representación de la red de vértices y aristas de un cubo ndimensional. El cubo de dimensión cero Q 0 consta, por definición, de un solo vértice. A partir de ahí, se obtiene Q n uniendo por medio de aristas los vértices correlativos de dos copias de Q n−1 . En la figura 2.7 podemos ver los primeros grafos cúbicos, hasta el de dimensión 4. 34

Abad C32 C2Abad C2 Zorrilla Zorrilla Zorrilla Abascal Abascal + C3 C3 A C3 A A Álvarez Álvarez C∗4 C4 B C4 B B Bastardo Bastardo C55 C5 C C5 C C Cobas +7 C CCobas C7 7D D D Cazorla Cazorla P66 P6 E P6 E E Dehesa C CDehesa Cm 12m mF F F González González χ (K 5 ) =Q50 Q0 G Q0 G G Guzmán Guzmán χ (K 3,3 ) =Q21 Q Q1 1H H H Herrero Herrero χ (C7 ) =Q32 Q Q2 2 I I I Lebrel Lebrel χ (esto) =Q43 Q Q3 3 J J J Zapatero Zapatero χ (esto otro) =Q44 Q Q4 4 3 3 3 Zorrilla Zorrilla x1 ≥Q65 Q Q5 + + 5+ A A x2 Abad ≥8 Abad ∗ ∗ ∗ Abad x1 ≥ 6,Abascal x2 ≥ 8 Abascal 5 B 5B 5Abascal x1 < 6, Álvarez x2 < 8 +C +Álvarez Álvarez + C A2 Bastardo Bastardo 6 D Bastardo 6D 6 E A 1 Cobas Cobas12 E 12 12 Cobas A − A1Cazorla − A2P6χ (K 5 ) = 5 F χCazorla (K 5 ) C =5F χ (K 5 ) = 5Cazorla 7 G G A χ (K ) = 2 χ (K ) = 2 χ (K 3,3 ) = 2Dehesa 12 3,3 Dehesa 3,3 Dehesa H H χ (C ) = 3 χ (C ) = 3 χ (C7 ) =González 3 7 7 González González I I Figura 2.6: Camino P y ciclos C χ (esto) = 4 χ (esto) = 4 χ (esto) = 4 6 7 y C5 Guzmán Guzmán Guzmán J J χ (esto otro) = 4 χ (esto otro) = 4 χ (esto otro) = 4 Herrero Herrero Herrero x1 ≥ 6 3 x1 ≥ 6 3 x1 ≥ 6 Lebrel Lebrel Lebrel Zapatero Zapatero x2 ≥ 8 + x2 ≥ 8 + x2 ≥ Zapatero 8 ∗ ∗ x ≥ 6, x ≥ 8 x ≥ 6, x ≥ 8 x ≥ 6, x ≥ 8Zorrilla Zorrilla Zorrilla 1 2 1 2 1 2 5 x1A< 6, x 2 < 8 5 x1 < 6, x 2 < 8 x < 6, x < 8 A A 1 2 Q0 A2 + A2 B BA2 + B Q1 A1 6 A1 C CA1 6 C 12 12 A − A − A A − A − A A − A − A2 D D 1 2 1 D 2 1 χ (K 5A) = 5 χ (K 5A) = 5 A12 E E 12 E 12 χ (K 3,3 ) = 2 χ (K 3,3 ) = 2 F F F χ (C7 ) = 3 χ (C7 ) = 3 (a) (b) G G G (c) χ (esto) = 4 χ (esto) = 4 H H H χ (esto otro) = 4 χ (esto otro) = 4 I I I x1 ≥ 6 x1 ≥ 6 J J J x2 ≥ 8 x2 ≥ 8 3 3 3 x ≥ 6, x ≥ 8 x ≥ 6, x 2 1 +1 +2 ≥ 8 + x < 6, x 2 < Q 83 x1 < 6, x 2 < 8 ∗1 ∗ ∗ A2 A 5 5 2 5 A1 + + A1 + A − A1 − A2 A − A1 − A2 6 6 6 Q4 A12 A 12 12 12 12 χ (K 5 ) = 5 χ (K 5 ) = 5 χ (K 5 ) = 5 (d) ) = 2 (e) χ (K 3,3 ) = 2 χ (K χ (K 3,3 3,3 ) = 2 χ (C7 ) = 3 χ (C7 ) = 3 χ (C7 ) = 3 χ (esto) = 4 χ (esto) 4 Grafos Q n , para nχ= (esto) Figura=2.7: 0, . . = .,4 χ (esto otro) = 4 χ (esto otro) = 4 χ (esto otro) = 4 x1 ≥ 6 x1 ≥ 6 x1 ≥ 6 x2 ≥ 8 x2 ≥ 8 x2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 x1 < 6, x 2 < 8 x1 < 6, x 2 < 8 x1 < 6, x 2 < 8 A2 A2 A2 A1 A1 A1 A − A1 − A2 A − A1 − A2 A − A1 − A2 A12 A12 A12 (a)

























































(b)

C5

Q2

(c)

Figura 2.8: (a) Un árbol. (b) Un bosque. (c) Un grafo que no es ni un árbol ni un bosque

35

2.6. Arboles Definición 8. Un árbol es un grafo no dirigido, conexo y acíclico. Un grafo no dirigido que es acíclico, pero posiblemente no conexo, se denomina bosque. La figura 2.8(a) muestra un árbol, y en 2.8(b) vemos un bosque que no es un árbol, al no ser conexo. El grafo de 2.8(c) no es un árbol ni un bosque, pues contiene un ciclo. Antes de demostrar un importante teorema sobre árboles precisamos los dos lemas siguientes, cuyas demostraciones son prácticamente idénticas. Lema 1. Sea G un grafo no dirigido con n vértices y e aristas. Si G es conexo, se verifica que e ≥ n − 1. Demostración. Por inducción sobre el número de vértices. El teorema es trivialmente cierto para n = 1. Supongamos entonces que la desigualdad se verifica en todos los grafos conexos con menos de n vértices. Consideremos un vértice cualquiera v ∈ V (G) de grado d como el que mostramos en la figura 2.9, siendo sus vértices adyacentes v1 , v2 , . . . , vd . El grafo G − v obtenido al suprimir v y sus aristas adyacentes posee n − 1 vértices, e − d aristas y es posiblemente inconexo; al suprimir v, G puede divirse a lo sumo en d componentes conexas (¿por qué?). Sean entonces esas componentes los subgrafos C i de G, con i = 1, 2, . . . , m ≤ d. Cada componente C i es un grafo conexo con menos de n vértices. Por tanto, por hipótesis de inducción, sus números de vértices n i y aristas ei satisfacen la desigualdad ei ≥ n i − 1

i = 1, 2, . . . m

Sumando estas desigualdades sobre todas las componentes à m ! m m X X X ni − m ei ≥ (n i − 1) = i=1

i=1

i=1

Ahora, el primer sumatorio es el número de aristas de G − v, es decir, e − d, y el último es el de vértices, n − 1. Como el número de componentes m no supera el grado d e−d ≥n−1−m

es decir

e ≥n−1+d −m ≥n−1

como se quería demostrar. El lema dual del recién probado cambia la conexión por la aciclicidad, con lo que el sentido de la desigualdad se invierte. Lema 2. Sea G un grafo no dirigido con n vértices y e aristas. Si G es acíclico, e ≤ n − 1. Demostración. Por inducción sobre el número de vértices. El teorema es trivialmente cierto para n = 1. Supongamos entonces que la desigualdad se verifica en todos los grafos acíclicos con menos de n vértices. Consideremos un vértice cualquiera v ∈ V (G) de grado d como el que mostramos en la figura 2.9, siendo sus vértices adyacentes v1 , v2 , . . . , vd . Al suprimir el vértice v y obtener G − v, resulta ahora un grafo acíclico que, a diferencia del lema anterior, posee al menos d componentes conexas (¿por qué?). Es decir, m ≥ d. 36

F G H I J 3 + ∗ 5 + 6 vd 12 Cm χ (K 5 ) = 5 χ (K 3,3 ) = 2 .. χ (C7 ) = 3 . χ (esto) = 4C 4 χ (esto otro) = 4 v x1 ≥ 6 6 x2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 x1 < 6, x 2 < 8 A2 v5 A1 A − A1 − A2 A12 C3

v1 C1 v2 v

v3 C2 v4

Figura 2.9: Demostración de los lemas 1 y 2 Ahora cada componente es un subgrafo acíclico y, por hipótesis de inducción ei ≤ n i − 1 Sumando

m X i=1

ei ≤

m X i=1

i = 1, 2, . . . m

(n i − 1) =

à m X i=1

ni

!

−m

En el presente caso, rige la desigualdad m ≥ d y se tiene entonces e−d ≤n−1−m

es decir

e ≥n−1+d −m ≤n−1

como se quería demostrar. Existen numerosas formulaciones equivalentes de la definición de árbol; el teorema siguiente resume las fundamentales. Teorema 17. Sea G = (V, E) un grafo no dirigido. Las siguientes afirmaciones son equivalentes. 1.

G es un árbol

2.

Dos vértices cualesquiera de G están conectados por un único camino simple

3.

G es conexo, pero si se le suprime una arista cualquiera, deja de serlo.

4.

G es conexo y |E| = |V | − 1

5.

G es acíclico y |E| = |V | − 1

6.

G es acíclico, pero si se le añade una arista, deja de serlo

Demostración. 1 ⇒ 2) Sean u, v ∈ V . Como G es conexo, existe un camino simple entre ellos. Si existen dos caminos simples distintos entre ambos vértices, se dará la situación de la figura 17: los caminos p y p 0 divergen por primera vez en el vértice w y vuelven a converger en el vértice z, pasando por vértices diferentes x e y. Como 37

∗ 5 + 6 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 χ (C7 ) = 3 χ (esto) = 4 χ (esto otro) = 4 x1 ≥ 6 x2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 x1 < 6, x 2 < 8 u A2 A1 A − A1 − A2 A12

p x

v

w z y p0

Figura 2.10: Demostración de la implicación 1 ⇒ 2 en el teorema 17 resultado, es posible construir un ciclo, contra la hipótesis. Por tanto, no pueden existir dos caminos simples distintos entre u y v. 2 ⇒ 3) Evidentemente, G es conexo. Si se suprime la arista (u, v) de G, los vértices u y v quedan desconectados, pues, por hipótesis, dicha arista era el único camino simple que los conectaba. 3 ⇒ 4) Una vez más, la conexión de G es parte de la hipótesis. Por otro lado, G es acíclico, puesto que si tuviese un ciclo, podría suprimírsele una arista sin perder la conexión. Por tanto, de los lemas precedentes de deduce que |E| = |V | − 1. 4 ⇒ 5) Si suprimimos una arista de G, deja de verificarse la desigualdad |E| ≥ |V | − 1; por tanto, de la implicación anterior se sigue que G es acíclico. La igualdad |E| = |V | − 1 es parte de la hipótesis. 5 ⇒ 6) Al añadir una arista a G, se viola la desigualdad |E| ≤ |V | − 1 y el contrarrecíproco del lema 2 implica que G deja de ser acíclico. 6 ⇒ 1) Sean u y v dos vértices distintos de G (si no los hay la implicación es trivial). Si existe una arista (u, v), los dos vértices son mutuamente accesibles; si no, la adición de (u, v) a E(G) provoca la aparición de un ciclo C del que dicha arista es obviamente miembro. Suprimiendo (u, v) de C obtenemos un camino que conecta u y v.

2.6.1.

Arboles enraizados

Un árbol enraizado es un árbol en el que marcamos uno de los vértices como vértices disinguido. Dicho vértice se denomina raíz del árbol. Por ejemplo, el árbol de la figura 2.11 tiene por raíz el nodo 7. Como puede verse, en los árboles enraizados es más común llamar nodos a los vértices Consideremos un nodo cualquiera v de un árbol enraizado de raíz r . Existe un único camino entre r y v; cualquier nodo presente en ese camino es un ancestro o antecesor de v. Si w es un ancestro de v, decimos que v es un descendiente de w. Todo nodo es, por definición, ancestro de sí mismo; un ancestro de v diferente a él es un ancestro propio. Un descendiente propio se define de forma análoga. El subárbol con raíz en v es el subárbol inducido por los descendientes de dicho vértice. Supongamos que la última arista del (único) camino entre la raíz y un nodo v es (w, v). En ese caso, decimos que w es el padre de v, y que v es hijo de w. Dos nodos que tienen el mismo padre son hermanos. Un nodo sin hijos es una hoja o nodo externo; en caso contrario, es un nodo interno. El número de hijos de un nodo es su grado; obsérvese que, en este contexto, el grado de un nodo es una unidad inferior a lo definido en la sección 2.2.2. Si todos los nodos de un árbol tienen grado a lo sumo m, 38

H I J 3 + ∗ 5 + 6 12 Lebrel χ (K 5 ) = 5 χ (K 3,3 ) = 2 7 χ (C7 ) = 3 A χ (esto) = 4 B χ (esto otro) = 4 9 6 8 C x1 ≥ 6 D x2 ≥ 8 E x1 ≥ 6, x 2 ≥ 8 F 3 5 10 4 11 12 x < 6, x 2 < 8 G1 A2 H A1 I A − A1 − A2 J 2 A12 1 3 + Figura 2.11: Arbol de doce nodos enraizado en el nodo 7 ∗ 5 + Abad 6 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 Álvarez Zapatero Abascal Zorrilla χ (C7 ) = 3 χ (esto) = 4 χ (esto otro) = 4 x1 ≥ 6 Guzmán Bastardo González x2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 x1 < 6, x 2 < 8 A2 A1 Herrero Dehesa Cobas A − A1 − A2 Cazorla A12 Figura 2.12: Buscando al abonado Dehesa el árbol es m-ario. Así, en un árbol ternario cada nodo tiene, a lo sumo, tres hijos; posiblemente, menos. Definimos la profundidad de un nodo v como la longitud del camino de la raíz a v. La altura de un árbol es el máximo de las profundidades de sus nodos. El árbol de la figura 2.11 tiene altura 3, puesto que los nodos 1 y 2 tienen ambos dicha profundidad. El subárbol con raíz en el nodo 9 tiene altura uno. Un árbol enraizado en el que los hijos de cada nodo tienen asignado un orden es un árbol ordenado. Esto significa que si un nodo tiene k hijos, hay un primer, segundo, . . . , k-ésimo hijo. El interés de los árboles reside en su uso como estructuras de datos para clasificar información. Por ejemplo, el árbol de la figura 2.6.1 codifica un índice de una base de datos de abonados telefónicos. El árbol es ordenado y cuaternario; tiene, además, la propiedad de que los datos residentes en una rama son siempre anteriores a los datos que residen en ramas situadas a su derecha. Esto lo convierte en un árbol de búsqueda. Para localizar al abonado Dehesa, es suficiente encontrar qué hijo del nodo raíz lo 39

contiene, lo que se determina de inmediato. Prosiguiendo recursivamente de esta forma, llegamos a encontrar al abonado en un número de pasos igual, a lo sumo, a la altura del árbol de búsqueda. ¿Cuál podría ser esa altura en el caso de tener un millón de abonados? Teorema 18. Sea T un árbol m-ario de altura h. Entonces, el número de nodos n del árbol satisface la desigualdad m h+1 − 1 n≤ m−1 Dicho de otro modo, un árbol m-ario de n nodos tiene que tener altura mínima dada por h ≥ −1 + logm ((m − 1)n + 1) En particular, un árbol binario satisface las desigualdades siguientes n h

≤ 2h+1 − 1 ≥ −1 + log2 (n + 1)

Demostración. Si cada nodo tiene a lo sumo m hijos, habrá a lo sumo un nodo de nivel 0 (el nodo raíz); m nodos de nivel 1 (sus hijos); m 2 nodos de nivel 2 (sus nietos); m 3 nodos de nivel 3 (sus bisnietos); y, en general, el nivel k tendrá una población máxima de m k nodos. Por lo tanto, el número total de nodos será inferior a 1 + m + m2 + m3 + · · · + mh =

m h+1 − 1 m−1

que es lo que se quería demostrar. Las demás desigualdades se obtienen despejando la altura y particularizando para m = 2. Como ejemplo, en el caso de un millón de abonados, tendríamos un árbol de altura mínima h ≥ −1 + log4 (3·106 + 1) = 9,758 luego un árbol de altura h = 10 podría albergar nuestro millón de abonados, si está correctamente equilibrado. En esta hipótesis, nuestra búsqueda concluiría tras la lectura de once registros de nuestra base de datos a lo sumo, lo que no está nada mal.

2.6.2.

Arboles binarios

Aunque podríamos definir estos árboles a partir de lo estudiado en las secciones anteriores, seguiremos otra vía mucho más conveniente. Un árbol binario T es una estructura definida en un conjunto finito de nodos, que, o bien no contiene nodos, o bien contiene tres conjuntos distintos de nodos: un nodo raíz, un árbol binario llamado el subárbol izquierdo y otro llamado el subárbol derecho. Observemos que está permitido que un árbol binario sea vacío: se trata del árbol vacío o árbol nulo. Dado un árbol binario de raíz r , si el subárbol izquierdo no es vacío, su raíz es el hijo izquierdo de r ; el hijo derecho de define análogamente. Es posible, pues, que un hijo izquierdo o derecho estén ausentes (cuando sea vacío el correspondiente subárbol). 40

P REORDEN(T ) 1 if T = NIL 2 then no hacer nada 3 else V ISITA(T ) 4 P REORDEN(T.i z) 5 P REORDEN(T.de)

P OSTORDEN(T ) 1 if T = NIL 2 then no hacer nada 3 else P OSTORDEN(T.i z) 4 P OSTORDEN(T.de) 5 V ISITA(T )

I NORDEN(T ) 1 if T = NIL 2 then no hacer nada 3 else I NORDEN(T.i z) 4 V ISITA(T ) 5 I NORDEN(T.de)

Figura 2.13: Pseudocódigo de los recorridos de un árbol binario Es preciso hacer notar que un árbol binario no es simplemente un árbol ordenado en que cada nodo tiene a lo sumo dos hijos. En tal caso, no podríamos decidir, para un nodo con un solo hijo, si éste es el izquierdo o el derecho. El árbol binario, pues, proporciona “más estructura” que un simple árbol ordenado. Un nodo puede tener solamente un hijo izquierdo o solamente un hijo derecho.

2.7. Recorridos de grafos Un recorrido de un grafo es un procedimiento que origina una enumeración ordenada de sus vértices. Comenzaremos nuestro estudio de los recorridos por el caso particular de los árboles binarios

2.7.1.

Recorridos de árboles binarios

Recordemos que un árbol binario se define como un grafo vacío, o bien un nodo raíz más dos árboles binarios que constituyen el subárbol izquierdo y el derecho Esta definición recursiva es de especial interés cuando recorremos el árbol. Podemos definir tres maneras de visitar todos y cada uno de los vértices según se ve en la figura 2.13. Aplicando estos procedimientos al árbol de la figura 2.14(a), se obtienen las secuencias que se muestran en la tabla adjunta 2.14(b). Estos tres tipos de recorrido se relacionan con tres notaciones usuales para las expresiones algebraicas infija La notación del álgebra corriente exige que los operadores vayan en medio de sus dos operandos. Por ejemplo, la expresión 3 + 5 ∗ (6 + 12) está en notación infija. postfija Se obtiene colocando cada operador binario a continuación de sus operandos. Al contrario que la infija, no requiere paréntesis ni reglas de precedencia para resolución de la ambigüedad. La expresión anterior, en notación posfija se convierte en 3 5 6 12 + ∗+ 41

H I J 3 + ∗ 5 + 6 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 χ (C7 ) = 3 χ (esto) = 4 χ (esto otro) = 4 x1 ≥ 6 x2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 x1 < 6, x 2 < 8 A2 A1 A − A1 − A2 A12

e

a

g

c

j

b

f

h

d

(a) Árbol binario

Tipo Inorden Preorden Postorden

c e c

a a b

Resultado e j g h b g j f j h d f

b c a

f h g

d d e

(b) Recorridos

Figura 2.14: Recorridos de un árbol binario La notación postfija (también llamada polaca inversa es muy adecuada para su interpretación por máquinas, lo que no es de extrañar a la luz del ejemplo anterior. Es muy sencillo escribir un programa que interprete de forma directa expresiones postfijas empleando una pila como estructura de datos auxiliar prefija Se obtiene colocando los operadores binarios como prefijos de los operandos. Así: + 3 ∗ 5 + 6 12

No es de mucho uso, pero aún pervive en el lenguaje Lisp, donde el cálculo anterior se escribiría como (+ 3 (* 5 (+ 6 12))) a pesar de que tampoco son precisos paréntesis ni reglas de precedencia para resolución de ambigüedades (el uso de paréntesis en Lisp tiene un significado distinto).

Las tres notaciones resultan de recorrer en in-, pre- y postorden un árbol sintáctico de la expresión, como puede comprobarse en la figura 2.7.1.

2.7.2.

Recorridos eulerianos

El problema que estudiamos a continuación se encuentra en el origen mismo de la teoría de grafos y de otra importante rama de la Matemática: la topología. Se trata del célebre problema de los puentes de Königsberg. 42

C4 C5 C7 P6 Cm Q0 Q1 Q2 Q3 Q4 + Q5 Abad Abascal Álvarez Bastardo χ (K 5 ) = 5 Cobas χ (K 3,3 ) = 2 Cazorla χ (C7 ) = 3 Dehesa χ (esto) = 4González χ (esto otro) = 4 Guzmán 3 x1 ≥ 6 Herrero x2 ≥ 8 Lebrel Zapatero x1 ≥ 6, x 2 ≥ 8 x < 6, x < 8 Zorrilla C D E F G H I J

1

2

A2 A1 A − A1 − A2 A12

+ Recorrido Inorden Postorden Preorden

∗

5

Expresión 3 + 5 ∗ 6 + 12 3 5 6 12 + ∗+ +3 ∗ 5 + 6 12

+

12 6 E F (a) (b) G H Figura 2.15: a) Árbol sintáctico y b) notaciones infija, prefija y postfija para la expresión I 3 + 5 ∗J(6 + 12) 3 + ∗ 5 + 6 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 χ (C7 ) = 3 χ (esto) = 4 B χ (esto otro) = 4 x1 ≥ 6 x2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 x1 < 6, x 2 < 8 A D A2 A1 A − A1 − A2 C A12 Figura 2.16: Los puentes de Königsberg

43

J 3 + ∗ 5 + 6 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 χ (C7 ) = 3 χ (esto) = 4 A χ (esto otro) = 4 x1 ≥ 6 x2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 x1 < 6, x 2 < 8B A2 A1 A − A1 − A2 A12 C

D

Figura 2.17: Los puentes de Königsberg La ciudad de Königsberg, capital de Prusia y patria del célebre filósofo Immanuel Kant, es atravesada por el río Pregel. En medio del río encontramos dos islas que se encuentran comunicadas con las orillas y entre sí por siete puentes, como se muestra en la figura 2.16. Los habitantes de Königsberg se plantearon si era posible dar un paseo que recorriese los siete puentes sin repetir ninguno (y, naturalmente, sin mojarse). Tras numerosos intentos infructuosos, la solución de este divertido problema combinatorio fue aportada por el matemático suizo Leonhard Euler en 1736. Euler no solamente demostró la imposibilidad del pretendido paseo, sino que, además, dio un sencillo criterio general para resolver cualquier problema del mismo tipo. Si prescindimos de detalles anecdóticos, es fácil ver que la búsqueda de un paseo por los puentes equivale a encontrar un camino que recorra todas las aristas del grafo de la figura 2.17 sin repetir ninguna (naturalmente, los vértices pueden repetirse). O, como suele formularse en las revistas de matemática recreativa, dibujar la figura de un solo trazo sin levantar el lápiz del papel. Definición 9. Sea G un grafo no dirigido. Denominamos recorrido euleriano de G a un camino que pasa por todas las aristas de G exactamente una vez. Es decir, si C = (v1 , v2 , . . . , vn ), la sucesión de aristas (v1 , v2 ), (v2 , v3 ), (v3 , v4 ), . . . , (vn−1 , vn ) contiene cada arista de G exactamente una vez. Si además C es cerrado, denominamos al recorrido un circuito euleriano El grafo del problema de los puentes no es un grafo dirigido en el sentido de la definición dada en 2.2.1, sino un multigrafo, en el que permitimos que haya más de una arista distinta entre dos vértices. Aunque no hemos definido rigurosamente estos objetos, todo lo que probaremos en la presente sección se extiende a ellos sin dificultad. Decimos que un grafo es euleriano si posee un recorrido euleriano. Obviamente, un grafo euleriano tiene que ser conexo. Pero, además, se necesitarán condiciones adicionales para garantizar la existencia de recorridos eulerianos. Tras bastantes ensayos con el grafo de los puentes, parece claro que no podemos encontrar una solución. La razón está en la paridad de los vértices del grafo. Decimos que un vértice v de un grafo no dirigido G es par (respectivamente, impar) si su grado es un entero par (resp. impar). Por ejemplo, en el grafo de la figura 2.17, todos los vértices son impares. Ahora bien, si intentamos dibujarlo de un solo trazo, cada vez que pasemos por un vértice, entraremos en él por una arista y saldremos por otra; ambas quedarán inutilizadas para su recorrido posterior. Excepto los vértices inicial o final de la trayectoria, todos los demás (vértices de paso) tendrán tantas aristas de entrada como de salida; por tanto, un número par de ellas, y su grado será par. Esto nos lleva al teorema de Euler. 44

Teorema 19. Sea G un grafo conexo no dirigido. Entonces, G posee un circuito euleriano si y solamente si G carece de vértices impares. Demostración. Supongamos primero que G posee un circuito euleriano dado por la sucesión de vértices C = (v0 , v1 , v2 , . . . , vn ). Por definición, cada arista del grafo aparece en la sucesión (v0 , v1 ), . . . , (vn−1 , vn ) exactamente una vez, y al ser el recorrido cerrado, v0 = vn . Sea v un vértice cualquiera de G. Si v es el único vértice de G, no hay nada que demostrar. Si no es así, v tendrá alguna arista incidente puesto que G se supone conexo, y esto obliga a que v aparezca cierto número de veces en el camino C. En cada aparición de v, éste figura dos veces; si, por ejemplo, está en la posición k-ésima de C, v = vk y tenemos dos aristas (vk−1 , vk ) y (vk , vk+1 ) incidentes en vk . Como estas aristas solamente figuran una vez en el recorrido, obtenemos que el número de aristas incidentes en v es igual al doble del número de apariciones de v en C, y, como todas las aristas son visitadas por C, el grado de v es forzosamente un número par. La única excepción de este argumento se encuentra en los extremos: cuando k = 0, n, las dos aristas (vn , v0 ) y (v0 , v1 ) se añaden al recuento de aristas incidentes en v0 según el argumento anterior, de modo que también v0 = vn debe ser par. La implicación contraria se demuestra por inducción sobre el número de vértices. De hecho, vamos a demostrar esta implicación para multigrafos dirigidos. Supongamos que G es un multigrafo conexo todos cuyos vértices son de grado par. En el caso de un grafo de un solo vértice, el circuito euleriano se obtiene de forma trivial. Así pues, sea |V | = n y supongamos que todo multigrafo conexo de menos de n vértices, todos pares, posee un circuito euleriano. Sea v un vértice cualquiera de G; por hipótesis de conexión, el grado d de v debe ser un número par estrictamente mayor que cero. Consideremos los vérticesi v 1 , v2 , . . . , vd adyacentes a v, como se muestran en la figura 2.18(a). Si suprimimos v y las aristas incidentes en él, obtenemos el grafo G − v; la supresión de las aristas indicadas se muestra en gris en la figura 2.18(b). Ahora, los vértices vi resultan ser todos impares tras la supresión. Adjuntando las aristas (v1 , v2 ), (v3 , v4 ), . . . , (vd−1 , vd ) obtenemos un nuevo grafo en el que todos los vértices vuelven a ser de grado par; no obstante, el número de vértices es ahora n − 1. Además, el nuevo grafo es obviamente conexo (obsérvese que, por la adjunción de las nuevas aristas, podemos obtener un multigrafo). Por lo tanto, se aplica la hipótesis de inducción, y deducimos que existe un recorrido euleriano. El paso por las aristas auxiliares de dicho circuito se produce en sentidos imprevisibles que indicamos con flechas en 2.18(b). Queda convertir este circuito euleriano en uno para G. Para ello, basta observar que la nueva arista (vi−1 , vi ) siempre puede ser reemplazada por el recorrido de (vi−1 , v), (v, vi ) (y en sentido contrario si es necesario), como se muestra en la figura 2.18(c). Con esto obtenemos un circuito euleriano de G y el teorema queda demostrado. De este teorema se deduce un interesante corolario. Corolario 1. Sea G un grafo conexo no dirigido. Si G tiene exactamente dos vértices impares, G posee un recorrido euleriano. Recíprocamente, si G posee un recorrido euleriano, sus vértices extremos son los únicos vértices impares de G (si son diferentes). Demostración. Sean v y w los vértices impares en cuestión, y añadamos a G la arista (v, w) (observemos que, una vez más, de esta adjunción puede resultar un multigrafo). Con esto, obtenemos un grafo en las hipótesis del teorema anterior, que posee 45

Zorrilla A B C D E F G H I J 3 + ∗ 5 + 6 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 χ (C7 ) = 3 χ (esto) = 4 χ (esto otro) = 4 x1 ≥ 6 x2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 x1 < 6, x 2 < 8 A2 A1 A − A1 − A2 A12

Q2 Zorrilla Q3 A Q4 B Q5 C Abad D Abascal E Álvarez F Bastardo G Cobas H Cazorla I Dehesa J González 3 Guzmán + Herrero ∗ Lebrel 5 Zapatero + Zorrilla 6 A 12 B χ (K 5 ) = 5 C χ (K 3,3 ) = 2 v1 vd D χ (C7 ) = 3 E χ (esto) = 4 F χ (esto v2 otro) = 4 G x1 ≥ 6 H .. v x2 ≥ 8 . I x1 ≥ 6, x 2 ≥ 8 J x1 < 6, x 2 < 8 v3 3 A2 + A1 ∗ v5 A − A1 − A2 v4 5 A12 + 6 (a) 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 v1 χ (C7 ) = 3 vd χ (esto) = 4 χ (esto otro) = 4 x1 ≥ 6 v x2 ≥ 8 .. x1 ≥ 6, x 2 ≥ 8 . x1 < 6, x 2 < 8 A2 A1 A − A 1 − A 2 v5 v4 A12

v1

vd

v2 .. .

v v3

v5 v4 (b)

v2

v3

(c)

Figura 2.18: Demostración del teorema de Euler: (a) antes de suprimir v. (b) Suprimido v y añadidas las aristas auxiliares, el grafo resultante posee un circuito euleriano. (c) Construcción del circuito euleriano para G

46

un circuito euleriano. Forzosamente, el circuito para por la arista (v, w) exactamente una vez. Suprimiéndola del circuito obtenemos un recorrido del grafo G. Recíprocamente, un recorrido euleriano de vértices extremos v y w se completa, añadiendo la arista (v, w), obteniendo un circuito euleriano del multigrafo resultante. Por lo tanto, éste tiene todos sus vértices pares, de lo que se deduce que los vértices v y w eran impares al principio. Por lo tanto, un grafo tiene un recorrido euleriano si y solamente si el número de vértices impares es cero o dos. Que dicho número no pueda ser la unidad es consecuencia del siguiente Teorema 20. Sea G un grafo no dirigido. El número de vértices impares de G es siempre par. Demostración. Sean {v1 , v2 , . . . , vn } los vértices de G y d1 , d2 , . . . , dn sus respectivos grados. El número de extremos que poseen las aristas de G es, evidentemente, 2|A|, puesto que cada arista tiene dos extremos. Ahora bien, podemos contar dicho número de extremos sumando los grados de todos los vértices, puesto que dichos grados son el número de extremos de aristas que confluyen en un vértice dado. De modo que se tiene n X i=1

di = 2|A|

Ahora bien, esto significa que la suma de los grados de los vértices es par. Como la suma de dos números impares es siempre par, el número de di0 s no puede ser impar, puesto que el resultado de la suma sería impar en ese caso. Por tanto, hay un número par de vértices impares. Es decir, un grafo nunca podrá tener un solo vértice impar (ni tres, ni cinco. . . ). Este teorema se conoce a veces como “lema del apretón de manos”, porque puede ponerse en la siguiente forma: en una fiesta, el número de personas que estrechan la mano a una cantidad impar de gente tiene que ser necesariamente par. Es una consecuencia directa de que en un apretón siempre intervienen dos manos.

2.7.3.

Caminos hamiltonianos

Un problema de enunciado análogo, pero cuya simplicidad es tremendamente engañosa, es la determinación de si un grafo posee un camino hamiltoniano. Definición 10. Sea G un grafo (dirigido o no). Un camino C en G se dice que es hamiltoniano si C pasa por cada vértices del grafo exactamente una vez. Un ciclo que pasa exactamente una vez por cada vértice (excepto el vértice inicial, que aparece también como final), se denomina ciclo hamiltoniano Al contrario que en el caso euleriano, aquí no precisamos recorrer todas las aristas; simplemente nos interesa visitar cada vértice exactamente una vez. Aunque no se menciona explícitamente, los caminos hamiltonianos son siempre simples, lo que se deduce directamente de la definición. El nombre de este tipo de recorrido deriva de un puzzle ideado por Sir William Rowan Hamilton (1805–1865). Básicamente, Hamilton pedía encontrar un ciclo hamiltoniano en un grafo isomorfo al retículo de vértices de un dodecaedro. La solución 47

J Lebrel 3 Zapatero + Zorrilla ∗ A 5 B + C 6 D 12 E )=5 χ (K 5 F χ (K 3,3 ) = 2 G )=3 χ (C 7 H χ (esto) = 4 I =4 χ (esto otro) Jx ≥ 6 1 3x ≥ 8 2 + x1 ≥ 6, x 2 ≥ 8 x1 < 6,∗x 2 < 8 5 A 2 + A1 A − A61 − A2 12 A 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 Figura 2.19: El puzzle de Hamilton χ (C7 ) = 3 χ (esto) = 4 vm χ (esto otro) = 4 v3 vm+1 x 1 ≥ 6 v2 x2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 x1 < 6, x 2 < 8 A2 vn A1 A − A1 − A2 v1 A12 Figura 2.20: Construcción de un camino hamiltoniano en un torneo. es bastante sencilla. Sin embargo, dado un grafo arbitrario, no resulta fácil determinar si posee un ciclo hamiltoniano o no. De hecho, no se conoce ninguna caracterización fácil de los grafos hamiltonianos, y es probable que nunca se conozca ninguna. La razón de ello es que el problema del ciclo hamiltoniano es NP-completo. No es sencillo definir esta propiedad; baste mencionar que una solución eficiente del problema del ciclo hamiltoniano permitiría resolver de golpe una vasta familia de problemas computacionales enormemente difíciles, y existen sospechas muy fundadas de que tal solución eficaz no puede existir. Esto no implica que, para determinados grafos de tipos muy particulares, no sea posible determinar la existencia de caminos hamiltonianos (no necesariamente cerrados). Un ejemplo de ello lo constituyen los torneos definidos en la sección 2.5.2. Teorema 21. Todo torneo posee un camino hamiltoniano Demostración. Por inducción sobre el número de vértices n = |V |. El teorema es trivial para n = 1. Consideremos entonces un torneo G de n vértices y supongamos que todo torneo de n − 1 vértices posee un camino hamiltoniano. Sea v = v1 un vértice de G y consideremos el grafo G − v que se obtiene suprimiendo v y todas las aristas que entran o salen de dicho vértice. El grafo resultante tiene n − 1 vértices y, por hipótesis de inducción, posee un camino hamiltoniano. Sea éste C = (v2 , v3 , . . . , vn ); numeramos los vértices en el orden que dicho camino nos proporciona, por conveniencia. Nuestra notación implica, naturalmente, que el camino supuesto por hipótesis va de v 2 a vn , no en sentido contrario. Ahora pueden darse tres posibilidades: 48

1.

El torneo posee una arista (v1 , v2 ). En ese caso, puede completarse el camino C añadiéndole al principio esta arista y obteniéndose un camino hamiltoniano C 0 = (v1 , v2 , . . . , vn ) para G, con lo que el teorema quedaría demostrado.

2.

El torneo posee una arista (vn , v1 ). En ese caso, puede completarse el camino C añadiéndole al final esta arista y obteniéndose un camino hamiltoniano C 0 = (v2 , . . . , vn , v1 ) para G, con lo que el teorema quedaría demostrado.

3.

Si ninguna de las circunstancias anteriores se da, la definición de torneo obliga a que G posea las aristas (v2 , v1 ) y (v1 , vn ). Para cada vértice vk , con 2 ≤ k ≤ n, debe existir una arista ak con ak = (v1 , vk ) o ak = (vk , v1 ), puesto que así lo exige el hecho de que G sea un torneo. Esta situación se describe en la figura 2.7.3. Consideremos entonces la sucesión de aristas a2 , a3 , a4 , . . . , an . En nuestro caso, la primera arista entra en v1 y la última sale de v1 . Por lo tanto, tiene que haber una última arista que entre en v1 en esa sucesión, antes de llegar a an . Sea dicha arista am . Entonces, si reemplazamos la arista vm , vm+1 de C por el par de aristas am y am+1 obtenemos C 0 = (v2 , v3 , . . . , vm , v1 , vm+1 , vm+2 , . . . , vn ) que constituye el deseado camino hamiltoniano, y el teorema también es cierto para G en este caso.

2.7.4.

Recorridos en anchura y profundidad

Los algoritmos clásicos de teoría de grafos se basan en dos procedimientos básicos de recorrido denominados recorrido en anchura (breadth-first) y recorrido en profundidad (depth-first). Aunque admiten muchas formulaciones (por ejemplo, como algoritmos de búsqueda en árboles), aquí estableceremos su funcionamiento en el caso de grafos no dirigidos; para otros contextos funcionan exactamente igual con las modificaciones obvias. Consideremos el grafo de la figura 2.21(a), en la cual mostramos además su representación por listas de adyacencia (2.21(b)). Vamos a enunciar y ejecutar dos algoritmos que producen una enumeración ordenada de cada vértice del árbol. En cada algoritmo, procedemos visitando cada vértice y añadiendo sus vecinos a una lista de vértices pendientes. La visita de un vértice consiste en marcarlo como visitado y, si procede, tratar la información que contiene y emitir su nombre o algún otro dato como resultado de la visita. Hecho esto, seguimos tratando los vértices que queden pendientes. A grandes rasgos, los algoritmos de recorrido se describen en pseudocódigo en la figura 2.22. El recorrido en profundidad admite una formulación recursiva muy simple, mientras que el recorrido en anchura debe formularse en términos de una cola de vértices pendientes de visitar. En la cola, que inicialmente contiene sólo el vértice de partida, los vértices se mantienen en orden; se extraen del principio con la operación S ACA P RIMERO y se añaden al final con la operación E NCOLA. Los vértices ya visitados no se introducen en la cola en dicha operación. En la tabla de la figura 2.23(a) podemos observar la operación del algoritmo de recorrido en anchura. En cada paso, se toma el primer elemento de la cola, que se anota 49

C D E F G H I J + ∗ + 1 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 χ (C7 ) = 3 4 χ (esto) = 4 χ (esto otro) = 4 x1 ≥ 6 x2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 7 x1 < 6, x 2 < 8 A2 A1 A − A1 − A2 A12

2

3

5

6

8

9

Vértice 1 2 3 4 5 6 7 8 9 10

Adyacentes {2, 4} {1, 3, 5} {2, 5} {1, 5, 7, 8} {2, 3, 4, 6, 8, 9} {5} {4, 8, 10} {4, 5, 7, 9, 10} {5, 8} {7, 8}

10

(a) Grafo ejemplo

(b) Lista de adyacencia

Figura 2.21: Datos de partida para recorridos en anchura y profundidad

como visitado, y se examina su lista de adyacencia. Los vecinos que no hayan sido ya visitados se añaden al final de la cola antes de proceder a la siguiente iteración. Como resultado de este proceso, obtenemos que el recorrido construye un árbol como el mostrado en 2.23(b). Cada nodo figura en este árbol como hijo del nodo “culpable” de su ingreso en la cola Q. Un árbol de esta forma es un árbol abarcador (spanning tree): cubre todos los vértices del grafo. El recorrido de los vértices en profundidad es más difícil de visualizar al ser recursiva la formulación natural del algoritmo 2.22(a). La idea consiste en visitar en cada paso cualquiera de los nodos vecinos aún no visitados, hasta que llegamos a un callejón sin salida (es decir, no hay más vecinos inmediatos sin visitar). En ese caso es preciso volver atrás y reiniciar nuestro paseo en el último punto en el que dejamos sin explorar alguna posibilidad. Una forma menos vaga de expresar este procedimiento es la forma no recursiva del recorrido en profundidad que se esboza en el algoritmo de la figura 2.22(c). En esta versión se emplea una pila S, en la que se almacenan los vértices pendientes de ser recorridos. La operación de una pila es inversa a la de una cola: los elementos se introducen en ella por delante (con la operación P USH) y se sacan de ella también del principio (P OP). Inicialmente introducimos en la pila sólo el vértice de partida. Mientras la pila no se vacíe, tomamos el primer elemento de la pila (que es el último introducido, al revés que en una cola); si no está marcado como visitado ya, lo visitamos; y finalmente apilamos su lista de adyacentes (salvo los que estén marcados como visitados, que no se añaden). Un ejemplo de ejecución de este proceso aparece en la tabla de la figura 2.24(a), donde vamos viendo la historia de los contenidos de la pila y los elementos que van visitándose en sucesión. Como resultado del proceso obtenemos también el diagrama 2.24(b), que es otro árbol abarcador del grafo inicial. Una vez más, las aristas del 50

C4 C5 C7 P6 Cm Q0 Q1 Q2 Q3 Q4 Q5 Abad Abascal B READTH -F IRST(G, v) D EPTH -F IRST(G, v) 1 QÁlvarez ← [v] 1 V ISITA(v) 2 Bastardo while Q 6= ∅ 2 for each w in Ad j (v) 3 doCobas w ← S ACA P RIMERO(Q) 3 do D EPTH -F IRST(G, w) 4 Cazorla V ISITA(w) Dehesa 5 E NCOLA(Ad j (w)) González (a) En profundidad Guzmán (b) En anchura Herrero Lebrel Zapatero D EPTH -F IRST-NR(G, v) Zorrilla 1 S ← vacio A 2 P USH(v) B 3 while S 6= ∅ C 4 do w ← P OP(S) D 5 if w no visitado E 6 then F 7 V ISITA(w) 8 next ← Ad j (w) G H 9 next ← next − V ISITADOS (next) I 10 P USH(next) J 11 3 + (c) En profundidad, no recursivo∗ 5 + Figura 2.22: Recorridos en anchura (a) y en profundidad (b, c); pseudocódigos 6 12 χ (K 5 ) = 5 χ (K 3,3 ) = 2 Visitados Cola Q χ (C7 ) = 3 – 1 3 2 χ (esto) = 4 1 1 2 4 χ (esto otro) = 4 12 453 x1 ≥ 6 124 5378 4 5 x2 ≥ 8 6 1245 3 7 8 6 9x ≥ 6, x ≥ 8 1 2 12453 7 8 6 9 x < 6, x < 8 1 2 124537 8 6 9 10 9 8 A2 7 1245378 6 9 10 A1 12453786 9 10 A − A1 − A2 124537869 10 10 A12 1 2 4 5 3 7 8 6 9 10 – (b) Arbol abarcador (a) Traza

Figura 2.23: Funcionamiento del algoritmo B READTH -F IRST: (a) Traza del algoritmo, con la historia de vértices visitados y el estadode la cola en cada iteración, (b) árbol abarcador resultante del recorrido

51

Pila 1 24 2875 2872368 2 8 7 2 3 6 9 7 10 287236977 28723697 2872369 287236 28723 2872 287 28 2

E F G H I J 3 + ∗ 5 + 6 12 Visitado χ (K 5 ) = 5 1 χ (K 3,3 ) = 2 4 χ (C7 ) = 3 1 5 χ (esto) = 4 χ8(esto otro) = 4 10 x1 ≥ 6 4 7 x2 ≥ 8 – x1 ≥ 6, x 2 ≥ 8 9x1 < 6, x 2 < 8 7 6 A2 3 A1 2 A − A1 − A2 – A12 – –

2

3

5

6

8

9

10 (b) Arbol abarcador

(a) Evolución del stack

Figura 2.24: Funcionamiento del algoritmo D EPTH -F IRST: (a) Traza del algoritmo, con la historia de vértices visitados y el estado de la pila en cada iteración, (b) árbol abarcador resultante del recorrido. Las flechas grises indican los procesos de backtracking. grafo relacionan cada vértice con el “culpable” de su inclusión en la pila de pendientes. Las flechas grises indican los momentos en que se produjo vuelta atrás (backtracking) al haberse encontrado un callejón sin salida.

2.7.5.

Caminos mínimos, MST y demás

Los algoritmos de recorrido de la sección 2.7.4 son la base de los algoritmos clásicos de teoría de grafos que se estudian en la teoría de Estructuras de Datos y Algorítmica. De hecho, la estructura de datos básica subyacente a las búsquedas en anchura y profundidad (cola o pila) puede reemplazarse por una estructura más general denominada cola de prioridad, en la que los elementos son recuperados de acuerdo con un valor de prioridad que se asocia a cada uno. Con valores adecuados de la prioridad, se obtienen búsquedas en anchura, en profundidad o recorridos que conducen a algoritmos para encontrar caminos mínimos o árboles abarcadores. Estos conceptos se relacionan con el concepto de red. Una red se define como un grafo a cada una de cuyas aristas se ha asociado un número real, denominado su peso o coste. En la figura 2.25 tenemos un ejemplo de red. El coste asociado a un camino se obtiene de la forma obvia: sumando los pesos de las aristas que lo componen, y lo mismo puede definirse para un subárbol de la red correspondiente. Se denomina camino mínimo (o camino más corto) entre dos vértices v y w al camino de peso menor que une los dos vértices. En la red de la figura 2.25, el camino más corto entre los vértices 1 y 8 es el marcado en línea de trazos. El algoritmo para encontrar este tipo de caminos es el algoritmo de Dijkstra y se estudiará con profusión en la asignatura de Estructuras de Datos. 52

H I J + ∗ + χ (K 5 ) = 5 χ (K 3,3 ) = 2 χ (C7 ) = 3 χ (esto) = 4 χ (esto otro) = 4 x1 ≥ 6 x2 ≥ 8 x1 ≥ 6, x 2 ≥ 8 3 x1 < 6, x 2 < 8 A2 A1 4 A − A1 − A2 A12

2

32

12

21

8

6 1

18

5 17

13 14

8

3

15

6

7 24 25

5

69

Figura 2.25: Una red con el camino más corto entre 1 y 8 y su MST Las aristas marcadas con trazo grueso en la misma figura (de pesos 3, 6, 5, 13, 14, 17 y 25) constituyen un árbol abarcador mínimo (en inglés, minimum spanning tree o MST. Se trata de un árbol que cubre todos los vértices del grafo teniendo el peso menor posible. Existen dos algoritmos clásicos para encontrar tal MST, los algoritmos de Kruskal y Prim; serán también objeto de estudio en el futuro.

2.8. Planaridad y coloreado Se dice que un grafo G = (V, E) (simple, no dirigido y sin bucles) es coloreable con n colores, o simplemente n-coloreable, si existe una función f : V → {1, 2, . . . , n} tal que si u y v son vértices adyacentes, f (u) 6= f (v). Intuitivamente, esta definición implica que, disponiendo de n colores distintos, podemos colorear los vértices del grafo de modo que los vértices vecinos se distingan por el color. El menor número n de colores que resulta suficiente para colorear un grafo G se denomina su número cromático, y se denota por χ (G). En la figura 2.26 mostramos algunos ejemplos de grafos con diferentes números cromáticos. Vamos a dar algunos teoremas que nos permiten estimar un número de colores suficiente para el coloreado de ciertos grafos Teorema 22. Dado un grafo G, las siguientes afirmaciones son equivalentes: a) G es 2-coloreable, b) G es bipartito, y c) G carece de ciclos de longitud impar. Demostración. La equivalencia de b) y c) fue el contenido del teorema 16; nos queda, pues, probar la (casi trivial) equivalencia de a) y b). Si un grafo G admite un coloreado con dos colores, llamémoslo f : G → {1, 2}, denotemos V1 V2

=

=

{v ∈ V (G) | f (v) = 1}

{v ∈ V (G) | f (v) = 2}

es decir, los conjuntos V1 y V2 contienen los vértices de color 1 y color 2, respectivamente. Obviamente, estos conjuntos forman una partición de los vértices de V . Al 53

A B C D E F G H I J 2

+ ∗

2 1

2

1

2

3

+ 6 12

1

2

3

1

2

4

3

2

1

1

χ (C7 ) = 3

χ (K 3,3 ) = 2 1

x1 x2 x1 ≥ 6, x 2 x1 < 6, x 2

2

2

1

4 5 χ (K 5 ) = 5

≥6 ≥ 81 ≥8 <8 A2 A1 A − A1 − A2 A12

1

3

1

3

2 4

2 1

4 2

2

2

1

3

3 χ (esto) = 4

1

3

1

χ (esto otro) = 4

Figura 2.26: Algunos grafos y sus números cromáticos ser f un 2-coloreado, vértices adyacentes tienen colores distintos: dicho de otro modo, cada arista va de V1 a V2 , y el grafo es, por tanto, bipartito. Si G es bipartito, con aristas entre dos conjuntos V1 y V2 exclusivamente, basta asignar el primer color a los vértices de V1 y el segundo a los de V2 . El caso de los grafos bipartitos es bastante especial. Un teorema algo más general, aunque no demasiado potente, nos da una cota superior para el número de colores preciso en un grafo cualquiera G. Teorema 23. Si 1(G) = max {deg(v) | v ∈ V (G)} es el mayor de los grados de los vértices de G, entonces χ (G) ≤ 1(G) Dicho de otra manera, si el vértice de mayor grado de G tiene grado d, bastan d + 1 colores para colorear G. Demostración. Por inducción sobre el número de vértices. Si el grafo tiene un solo vértice, su grado será cero y el grafo es trivialmente 1-coloreable, o sea que χ (G) = 1 ≤ 1 = 1(G) + 1 Supongamos ahora que G tiene un número cualquiera |V | de vértices, y que el teorema que queremos probar es cierto para todos los grafos con menos vértices que |V |. Sea v un vértice de máximo grado de G, i.e., deg(v) = 1(G). Suprimamos v y todas las aristas en él incidentes, obteniendo el grafo G 0 = G − v. Evidentemente, G 0 tiene un vértice menos, y está claro que 1(G 0 ) ≤ 1(G), así que G 0 es (1(G) + 1)-coloreable, 54

por hipótesis de inducción. Ahora bien, si consideramos un (1(G) + 1)-coloreado de G 0 , podemos extenderlo a un coloreado de G asignando algún color a v. Como el grado de v es 1(G), alguno de los 1(G) + 1 colores no se ha utilizado en teñir a los vecinos de v, y ese color podrá utilizarse para teñir a v, con lo que también G será (1(G) + 1)coloreable. Obsérvese que este teorema proporciona un número de colores suficiente, pero puede ser bastante mayor que el mínimo necesario. Por ejemplo, para K 3,3 (véase la figura 2.26) el teorema dice que cuatro colores bastan, y es así, porque de hecho bastan dos. El caso del último grafo de la misma figura es especialmente significativo: hay un vértice de grado 8, luego el teorema garantiza que nueve colores bastan. Sin embargo, en la práctica vemos que con cuatro es posible colorear el grafo. El último teorema sobre coloreado que veremos no se demostrará: sería realmente difícil, por las razones que después veremos. Definimos un grafo plano como uno que es factible representar en el plano de forma que sus aristas no tengan intersecciones (salvo en los extremos, claro). Por ejemplo, la figura 2.26 representa tres grafos planos. Los dos primeros no lo son: aunque no es obvio, K 5 y K 3,3 son imposibles de dibujar en un plano sin que alguna arista se cruce con otra. Una propiedad curiosa de los grafos planos es la siguiente, que enunciamos sin demostrar: Teorema 24. Si G es un grafo plano, el número C de regiones conexas en que su representación divide al plano satisface la relación C− A+V =2 siendo A y V los números de aristas y vértices, respectivamente. El teorema al que hacíamos referencia antes es el Teorema 25. (de los cuatro colores) Todo grafo plano es 4-coloreable La interpretación geométrica de este enunciado es que cualquier mapa puede colorearse con cuatro colores de forma que países fronterizos se distingan por el color. Por complejo que sea el mapa, cuatro colores serán siempre suficientes. El teorema de los cuatro colores se demostró en 1976, tras más de un siglo de intentos fallidos y la comprobación exhaustiva por computador de miles de configuraciones a las que la demostración se reduce.

55

56

Capítulo 3

Recurrencias y notación asintótica 3.1. Objetivo En el presente apartado nos plantearemos dos clases de problemas: la resolución en forma cerrada de recurrencias lineales homogéneas, y la estimación del crecimiento de recurrencias divide y vencerás. Un ejemplo del primer tipo de problema es la sucesión de Fibonacci, definida por las fórmulas F1 = F2 Fn

=

1

(3.1)

Fn−1 + Fn−2

(3.2)

=

Los dos primeros términos están dados explícitamente por (3.1) (los valores iniciales), y el tercero y siguientes pueden calcularse aplicando reiteradamente la ecuación de recurrencia (3.2). Así, la sucesión queda perfectamente determinada y sus primeros términos son n Fn

1 1

2 1

3 2

4 3

5 5

6 8

7 13

8 21

9 34

10 55

11 89

12 144

... ...

Si cambiamos los valores iniciales, obtenemos la sucesión de Lucas: L1 L2 Ln

=

= =

2 1 L n−1 + L n−2

cuyos términos iniciales son n Ln

1 2

2 1

3 3

4 4

5 7

6 11

7 18

8 29

9 47

10 76

11 123

12 199

... ...

Aplicando las ecuaciones de recurrencia podemos calcular cualquier término de estas sucesiones. Ahora bien, ¿sería posible encontrar una fórmula explícita para Fn o L n en función de n que nos permitiera obtener estos números sin tener que pasar por 57

todos los términos intermedios? Resulta que sí, y para la sucesión de Fibonacci una tal fómula es à à √ !n √ !n 1 1 1+ 5 1− 5 −√ (3.3) Fn = √ 2 2 5 5 Por qué la fórmula tiene este aspecto, y cómo se obtiene, será el primer problema que resolveremos. Además, es interesante observar que, cuando n es muy grande y consideramos términos muy avanzados de Fn , el segundo término de (3.3) tiende a cero (puesto que ¯ ¯ à √ !n ¯ 1 − √5 ¯ 1− 5 ¯ ¯ → 0 cuando n → ∞) ⇒ ¯ ¯<1 ¯ 2 ¯ 2 Entonces, el crecimiento de Fn √ se debe exclusivamente al primer sumando y se escribe Fn = O(φ n ), donde φ = (1 + 5)/2, para expresar que los números de Fibonacci se comportan, asintóticamente, como una exponencial de base φ. Otro tipo de relación de recurrencia algo diferente es la siguiente Q n = Q n/2 + cn

(3.4)

que aparece en el análisis del tiempo de ejecución de Quicksort, el algoritmo más rápido conocido para la ordenación de un vector de números. En este caso, no es factible encontrar una fórmula explícita para Q n , pero nos interesa saber cómo aumenta cuando n se hace muy grande, puesto que eso mide el coste del algoritmo para ordenar vectores de dimensión cualquiera. Una estimación aproximada es lo máximo que podemos obtener en estos casos, y demostraremos un teorema que nos permite obtener esa estimación. En este caso particular, se obtiene que Q n = O(n log n) lo que significa que el tiempo de ejecución del Quicksort crece algo más deprisa que el tamaño del vector a ordenar (pero infinitamente más despacio que el cuadrado de su tamaño, por ejemplo).

3.2. Recurrencias lineales homogéneas Una sucesión de números complejos {z k }∞ k=0 se dice que satisface una recurrencia lineal homogénea de orden n si se verifica la relación z k = c1 z k−1 + c2 z k−2 + . . . cn z k−n

(3.5)

para todo k ≥ n, siendo los coeficientes ci constantes (independientes del índice k). En el caso particular de la sucesión de Fibonacci, la recurrencia Fn = Fn−1 + Fn−2 es de segundo orden, al igual que sucede con la sucesión de Lucas. Nos gustaría encontrar una fórmula explícita para los valores de una sucesión que satisface (3.5). Supongamos que existe una fórmula del tipo siguiente z k = λk Si esta fórmula es cierta, la recurrencia (3.5) se satisface si λk = c1 λk−1 + c2 λk−2 + . . . cn λk−n 58

es decir P(λ) = λn − c1 λn−1 − c2 λn−2 − · · · − cn = 0

(3.6)

El polinomio P(λ) es el polinomio característico de la recurrencia (3.5), y la ecuación (3.6) es su ecuación característica. Los ceros de P(λ) son los valores propios o raíces características de la relación de recurrencia, y juegan un papel importantísimo en su resolución. De hecho, la construcción recién escrita nos garantiza que cualquier raíz característica λ origina una sucesión que satisface la recurrencia planteada: z k = λk . De hecho, las raíces características proporcionan aún más soluciones si tienen multiplicidad superior a la unidad. Aunque no lo demostraremos, si λ es un cero de multiplicidad m de P(λ), cada una de las sucesiones λk , kλk , k 2 λk , . . . k m−1 λk satisface la recurrencia (3.5). Y las combinaciones lineales de soluciones son también soluciones. Todo lo cual podemos sintetizar en el siguiente Teorema 1. Si P(λ) es el polinomio característico de la recurrencia lineal homogénea (3.5), y λ1 , λ2 , . . . , λ p son los distintos ceros de P(λ), con multiplicidades respectivas m 1 , m 2 , . . . , m p respectivamente, cualquier sucesión que satisface la recurrencia tiene la forma zk =

+ +

c10 λk1 + c11 kλk1 + c12 k 2 λk1 + . . . c1,m 1 −1 k m 1 −1 λk1

c20 λk2 + c21 kλk2 + c22 k 2 λk2 + . . . c2,m 2 −1 k m 2 −1 λk2 ...

c p0 λkp + c p1 kλkp + c p2 k 2 λkp + . . . c p,m p −1 k m p −1 λkp

Más simplemente, la terrible fórmula anterior puede escribirse z k = P1 (k)λk1 + P2 (k)λk2 + Pp (k)λkp donde cada Pi es un polinomio en la variable k, de grado menor que m i . En términos coloquiales, cada cero λ del polinomio característico nos da tantas soluciones independientes de la recurrencia original como multiplicidad m tenga: dichas soluciones son λk , kλk , k 2 λk , . . . k m−1 λk . Las combinaciones lineales que podamos formar con todas estas funciones del índice k cubren todas las posibilidades. Aunque completamente general, el contenido del teorema se entiende mejor con un ejemplo concreto. Ejemplo 7. Obtener una fórmula para la sucesión de Lucas. El polinomio característico de la recurrencia L n = L n−1 + L n−2 es λ2 − λ − 1. Los ceros son √ √ 1− 5 1+ 5 φ¯ = φ= 2 2 Del teorema 1 se deduce que L n = Aφ n + B φ¯ n donde A y B son coeficientes a determinar. Ahora bien, los valores iniciales de la sucesión proporcionan L1 = 2

L2 = 1

Aφ + B φ¯

=

Aφ 2 + B φ¯ 2

= 59

Tenemos dos ecuaciones y dos incógnitas. Resolviendo el sistema lineal obtenemos √ 1+ 5 2 B=− A= √ 2 1+ 5 y por tanto 2 Ln = √ 1+ 5

Ã

√ !n √ Ã √ !n 1+ 5 1+ 5 1− 5 − 2 2 2

Ejemplo 8. Resolver la recurrencia an = 6an−1 − 12an−2 + 10an−3 − 3an−4 dados a1 = 1, a2 = 2, a3 = 3, a4 = 6. En este caso, el polinomio característico es λ4 − 6λ3 + 12λ2 − 10λ + 3 Si tiene ceros racionales, éstos deben ser divisores del término independiente, así que probamos con ±1 y ±3. Se obtiene la descomposición factorial λ4 − 6λ3 + 12λ2 − 10λ + 3 = (λ − 1)3 (λ − 3) i.e., 1 es una raíz triple y 3 una raíz simple de la ecuación característica. Por tanto, la solución de la recurrencia tendrá la forma an = 3n A + B + Cn + Dn 2 Para determinar cuánto valen A, B, C y D planteamos las ecuaciones proporcionadas por los valores iniciales: a1 a2 a3 a4

= =

= =

1 = 3A + B + C + D 2 = 9A + B + 2C + 4D

3 = 27A + B + 3C + 9D 6 = 81A + B + 4C + 16D

y obtenemos que A = 1/12, B = −3/4, C = 2 y D = −1/2. Por lo tanto an = 3n /12 − 3/4 + 2n − n 2 /2

3.3. Notación asintótica La aplicación más corriente de nuestros cálculos sobre recurrencias es la estimación del tiempo que un algoritmo tarda en ejecutarse. En tal estimación, no es preciso obtener un resultado numéricamente exacto: lo único de interés es una idea vaga de cómo aumenta el tiempo de ejecución cuando la dimensión del problema aumenta. Por ejemplo, los algoritmos usuales para la suma de matrices cuadradas de dimensión n ×n requieren realizar n 2 sumas. Si se trata de un producto de matrices, es preciso multiplicar escalarmente cada fila del primer factor por cada columna del segundo. Un producto escalar de un vector de n elementos exige n multiplicaciones y n − 1 sumas, de forma que el tiempo de ejecución de una multiplicación de dos matrices n × n es el 60

requerido para n 2 sumas y n 3 − n 2 multiplicaciones. La multiplicación suele dominar en coste a la suma, y está claro que, para matrices de un tamaño moderado, el sumando n 2 es despreciable respecto a n 3 . De esta forma, adquiere sentido la afirmación “el producto de matrices consume un tiempo proporcional a n 3 ”. Este tipo de valoración en que despreciamos todos los términos involucrados en un cálculo salvo aquéllos cuyo crecimiento domina al de todos los restantes, es lo que se denomina asintótica. La notación más habitual para expresar estas manipulaciones es la notación O (léase “O mayúscula” u “O grande”). Definición 11. Sean f (n), g(n) funciones reales de argumento entero. Decimos que f es O grande de g, y escribimos f (n) = O(g(n)), si existen c > 0 y N entero tales que | f (n)| ≤ c|g(n)|

para todo n > N

Es decir, salvo una constante multiplicativa, la función f está dominada por g desde cierto valor en adelante. Ejemplo 9. Son válidas las siguientes notaciones asintóticas: Si f (n) = O(1), la función f está acotada. n 2 = O(n e ) para e ≥ 2, pero no si e < 2. n 3 − n + 3 = O(n 3 ) 2n + 3n = O(3n ) 1/n = O(1) n + 1/n = O(n) log n = O(n) √ log n = O( n) Las propiedades más usuales de la notación O son las siguientes: Teorema 2. Se verifican las siguientes propiedades Si | f (n)| ≤ |g(n)|, entonces f (n) = O(g(n)). En particular, f (n) = O( f (n)). Si lim f (n)/g(n) < ∞, f (n) = O(g(n)). n a = O(n b ) si y solamente si a ≤ b. a n = O(bn ) si y solamente si a ≤ b. log n = O(n e ) para todo e > 0. O( f (n)) + O(g(n)) = O(max{| f (n)|, |g(n)|}) O( f (n))O(g(n)) = O( f (n)g(n)) De lo anterior podemos deducir que, si P(n) = c0 n k + c1 n k−1 · · · + ck es un polinomio en n, el término dominante (de mayor grado) es el que define su crecimiento asintótico: P(n) = O(n k ). Ejemplo 10. Estimar el crecimiento de los términos de la sucesión de Lucas. Según lo calculado en la sección 3.2, tenemos la fórmula à √ !n √ !n √ à 2 1+ 5 1+ 5 1− 5 Ln = − √ 2 2 2 1+ 5 Ahora bien, el segundo paréntesis tiene un valor absoluto menor que la unidad, de forma que à √ !n 1− 5 = O(1) 2 61

y como (1 +

√

5)/2 O(1) = O(1), obtenemos √ ¶n √ ¶n √ ¶n µ µ µ 1+ 5 1+ 5 1+ 5 2 − O(1) = O + O(1) = O + O(1) Ln = √ 2 2 2 1+ 5

pues que el término izquierdo domina asintóticamente al derecho. En otras palabras, el crecimiento de los números de Lucas es exponencial. La notación asintótica permite realizar con mucha comodidad cálculos difíciles, eliminando la obligación de arrastrar cantidades irrelevantes que podemos despreciar. Esto nos resultará útil en la sección siguiente, donde estudiaremos el crecimiento de funciones definidas por recurrencias que no podemos resolver de forma explícita.

3.4. Recurrencias divide y vencerás Una recurrencia ubicua en el análisis de algoritmos es la que se ajusta a la siguiente forma: f (n) = a f (n/b) + cn d a ≥ 1, b > 1, c > 0, d > 0 (3.7)

Una función creciente f que satisfaga esta recurrencia no puede, generalmente, calcularse en forma explícita salvo en casos muy particulares. Así pues, una solución completa como la que obtuvimos para las recurrencias lineales será imposible en la mayoría de casos. Sin embargo, sí es factible encontrar una relación que nos dé idea, al menos, de cómo crece la función f cuando su argumento tiede a infinito. Esto debería ser suficiente para nuestro propósito de analizar el comportamiento de un algoritmo recursivo, puesto que nos interesa el crecimiento del tiempo de ejecución, no su valor absolutamente exacto para cada instancia individual de n. Esa estimación aproximada de crecimiento será la que obtengamos en la presente sección. Para ello, vamos a aplicar la fórmula (3.7) reiteradas veces: f (n) = = = = =

´ ³ a f (n/b) + cn d = a a f (n/b2 ) + c(n/b)d + cn d ³ ´ a a a 2 f (n/b2 ) + cn d d + cn d = a 2 a f (n/b3 ) + c(n/b2 )d + cn d d + cn d b b ³ a ´2 ³a´ a 3 f (n/b3 ) + cn d d + cn d d + cn d b b ... ¸ ·³ ´ ³ a ´2 ³ a ´ a k−1 + · · · + + + 1 (3.8) a k f (n/bk ) + cn d bd bd bd

El proceso puede repetirse cuantas veces sea necesario, y nosotros vamos a escoger k de forma que el argumento de f (n/b k ) esté comprendido entre 0 y 1. Esto se consigue tomando k = dlogb ne

que denota el primer entero mayor que la cantidad logb n. Si lo hacemos así, 0 < n/bk < 1 y cuando n → ∞, tenemos siempre que f (0) < f (n/b k ) < f (1) y por tanto f (n) = O(1). Por otra parte, el corchete de la última expresión en 3.8 puede expresarse de forma más compacta como ³ a ´2 ³ a ´ ³ a ´k−1 (a/bd )k − 1 + · · · + + + 1 = bd bd bd (a/bd ) − 1 62

siempre que a/bd 6= 1. Tenemos entonces f (n) =

(a/bd )logb n − 1 (a/bd ) − 1 n logb a /n d − 1 n logb a O(1) + cn d (a/bd ) − 1 log a n b − nd O(n logb a ) + c (a/bd ) − 1

= a logb n O(1) + cn d = = =

O(n logb a ) + O(n d )

despreciando constantes multiplicativas. Entonces, pueden darse los casos siguientes: d > logb a. En tal caso, f (n) = O(n d ). d < logb a. En tal caso, f (n) = O(n logb a ). d = logb a. Si se da esta igualdad, a = b d y nuestra sumación geométrica del corchete en (3.8) no es lícita, puesto que la razón entre términos es igual a la unidad. Pero en este caso, el cálculo resulta aún más simple, puesto que la suma deviene entonces logb n y f (n) = O(n logb a + cn d logb n = O(n d logb n) puesto que el segundo término domina al primero Llegamos así al llamado teorema maestro: Teorema 3. Si una función monótona f (n) satisface la recurrencia (3.7), entonces Si d > logb a. f (n) = O(n d ). Si d < logb a, f (n) = O(n logb a ). Si d = logb a, f (n) = O(n d logb n).

63