Grafos

Cap´ ıtulo 9

El lenguaje de los grafos
Los grafos, los objetos y el lenguaje cuyo estudio iniciamos aqu´ son extremadamente ı, utiles para representar primero, y luego analizar, problemas muy diversos. De una manera ´ informal, un grafo es una colecci´n de v´rtices y de aristas que unen estos v´rtices. Los o e e v´rtices los dibujaremos como puntos (o peque˜os c´ e n ırculos) sobre el plano;las aristas ser´n a l´ ıneas que unen estos puntos. Adelant´ndonos a las definiciones formales, y para que el a lector vaya comprobando la amplia capacidad de representaci´n del lenguaje de los grafos, o empezamos con algunos ejemplos. Problema de horarios. El plan de estudios de una cierta licenciatura universitaria consta de ocho asignaturas. No se pueden programar a la misma hora dos asignaturassi hay alg´n alumno matriculado en u ambas. Se desea minimizar el n´mero de horas necesario para programar todas las asignaturas u salvando esa dificultad. Representamos primero cada asignatura con un v´rtice. Si entre dos e asignaturas hay incompatibilidad, entonces dibujamos una arista entre A8 A3 los v´rtices correspondientes. La representaci´n de toda esta informae o ci´n podr´ dar lugar a ungrafo como el de la izquierda. Ahora se trata o ıa A7 A4 de asignar a cada v´rtice un s´ e ımbolo (la hora a la que se imparte la A6 A5 asignatura) de manera que v´rtices que vayan unidos por una arista e no lleven el mismo s´ ımbolo. Pero adem´s nos interesar´ hacerlo empleando el m´ a a ınimo n´meu ımbolos. Para abordar esta cuesti´n (que el lector habr´ adivinado ya que o a ro posible de s´est´ ´ a ıntimamente relacionada con la construcci´n de listas con restricciones) desarrollaremos o el lenguaje del coloreado de grafos (v´ase la secci´n 10.3). e o ¿C´mo ordena Google los resultados de sus b´squedas? o u Los buscadores de la red tienen almacenada, en gigantescas bases de datos, informaci´n o sobre los contenidos de millones de p´ginas web. Cuando se introduce un cierto t´rmino, el ae buscador encuentra las p´ginas en las que ´ste aparece. La cuesti´n que aqu´ nos interesa es a e o ı la siguiente: ¿en qu´ orden se deben mostrar las p´ginas localizadas? e a En los ultimos a˜os, Google se ha convertido en el buscador m´s eficaz, con mucha ´ n a diferencia, hasta el punto de haberse convertido en un est´ndar. ¿Cu´l es el secreto (o uno a a 577
A1 A2

578

Cap´ ıtulo 9. Ellenguaje de los grafos

de los secretos) de Google? Al lector quiz´s le sorprender´ al descubrir que la explicaci´n a a o ´ se basa, simplemente, en un poco de teor´ de grafos y otro poquito de Algebra lineal. No ıa desvelamos nada m´s por el momento y remitimos al lector interesado a la subsecci´n 9.3. a o Asignaci´n de tareas o Tenemos un conjunto de trabajadores y otro de tareas y lainformaci´n de para qu´ tareas o e est´ capacitado cada trabajador. Buscamos una asignaci´n de tareas (a cada trabajador, una a o tarea distinta para la que est´ preparado) de forma que consigamos ocupar al mayor n´mero e u de trabajadores posible. t1 Digamos que en la empresa hay cinco trabajadores, T1 , . . . , T5 , y T1 t2 e ocho tareas, t1 , . . . , t8 . El grafo va a tener 13 v´rtices en total, tantost3 T2 como trabajadores y tareas, pero dibujamos, pues as´ resulta conveı t4 niente, los correspondientes a los trabajadores a un lado, y los de las T3 t5 tareas a otro. Adem´s, trazamos una arista entre un v´rtice que reprea e t6 T4 sente a un trabajador y otro que represente a una tarea si efectivamente t7 el trabajador est´ preparado para realizar dicha tarea (v´ase el dibujo a e t8 T5 de laderecha). Querr´ ıamos, por ejemplo, asignar a cada trabajador una tarea de entre las que sabe realizar. Determinar las condiciones necesarias para que esta asignaci´n exista (y encontrar un algoritmo que la construya) es un problema cl´sico de la o a Combinatoria, que aqu´ abordaremos desde el punto de vista de la Teor´ de grafos (v´ase la ı ıa e subsecci´n 10.2). o Construcci´n de redes o Se...