Problemas de Grafos y Tratabilidad Computacional Primer Cuatrimestre de 2009 Min Chih Lin ([email protected]) Marina Groshaus ([email protected]) Francisco J. Soulignac ([email protected]) http://www.dc.uba.ar/people/materias/probgraf

Normas b´ asicas de higiene y seguridad ´ - FCEyN - UBA DEPTO. DE COMPUTACION

Por resoluci´ on 802/98 del Consejo Directivo de la Facultad cada Departamento debe elaborar un conjunto de Normas B´ asicas de Seguridad para ser incluidas en las Gu´ıas de Trabajos Pr´acticos de todas las materias. A continuaci´ on transcribimos las normas aprobadas por el Departamento de Computaci´on Las normas b´ asicas de higiene y seguridad son un conjunto de medidas destinadas a proteger la salud de todos, prevenir accidentes y promover el cuidado del material de los laboratorios. Son un conjunto de pr´ acticas de sentido com´ un: el elemento clave es la actitud responsable y la concientizaci´on de todos: personal y alumnado. ´ ´ RESPETELAS Y HAGALAS RESPETAR 1. Se deber´ a conocer la ubicaci´ on de los elementos de seguridad en el lugar de trabajo, tales como: matafuegos, salidas de emergencia, accionamiento de alarmas, etc. 2. Observar de qu´e clase –A, B o C– es cada matafuego ubicado en el Departamento de Computaci´ on, y verificar qu´e material combustible –papel, madera, pintura, material el´ectrico– se puede apagar con ´el. Por ejemplo, nunca usar un matafuegos clase A para apagar fuego provocado por un cortocircuito. 3. Salidas: Ante una emergencia: se podr´a solicitar a un docente –JTP o profesor, u otra persona autorizada– que obtenga la llave de la puerta de planta baja. La persona autorizada que abra la puerta se har´ a responsable del cierre de la puerta y de la devoluci´on de la llave. 4. Las u ´nicas ventanas sin reja son las de los cuartos 11 y 12, dan a un balc´on. 5. No se deben bloquear las rutas de escape o pasillos con equipos, mesas, m´aquinas u otros elementos que entorpezcan la correcta circulaci´ on. 6. No se permitir´ a comer, beber, ni fumar en los laboratorios. Recordar que el polvo y la tiza da˜ nan las PC. 7. No se permitir´ a enchufar ni desenchufar perif´ericos a las CPU de los laboratorios sin la supervisi´on del docente o administradores de la red. No se modificar´a la instalaci´on de ning´ un equipo. 8. No se permitir´ an instalaciones el´ectricas precarias o provisorias. Se dar´a aviso inmediato a la Secretar´ıa T´ecnica en caso de filtraciones o goteras que puedan afectar las instalaciones o equipos y puedan provocar incendios por cortocircuitos (interno 355). 9. Es imprescindible mantener el orden y la limpieza. Cada persona es responsable directa del lugar donde est´ a trabajando y de todos los lugares comunes. 10. Los laboratorios contar´ an con un botiqu´ın de primeros auxilios con los elementos indispensables para atender casos de emergencia.

1

Procedimientos ante emergencias a. Emergencias m´ edicas Si ocurre una emergencia tal como: cortes o abrasiones, quemaduras o ingesti´on accidental de alg´ un producto qu´ımico, t´ oxico o peligroso, se deber´a proceder: a) A los accidentados se les proveer´ an los primeros auxilios. b) Simult´ aneamente se tomar´ a contacto con el Servicio M´edico (Interno 482), o al Servicio M´edico de Deportes (4576-3451 / 3459) c) Avise al Jefe de Laboratorio o autoridad del Departamento, quienes solicitar´an asistencia de la Secretar´ıa T´ecnica (interno 380) para que env´ıen personal del Departamento de Mantenimiento, Seguridad y Control o Servicios Generales seg´ un correspondan. d ) El Jefe de Departamento notificar´a el accidente al Servicio de Higiene y Seguridad para su evaluaci´ on e informe, donde se determinar´an las causas y se elaborar´an las propuestas para modificar dichas causas y evitar futuras repeticiones. e) Centros para requerir ayuda m´edica: S.A.M.E. Tel´efono 107 Hospital Pirovano Av. Monroe 3555 Tel. 4542-5552 / 9279 INTOXICACIONES Hospital de Ni˜ nos. Dr. R. Guti´errez S´ anchez de Bustamante 1399. Capital Federal. Tel: 4962-6666. Hospital de Ni˜ nos. Dr. P. de Elizalde Av. Montes de Oca 40 Tel. 4307-7491. Toxicolog´ıa: 4300-2115 QUEMADURAS Hospital de Quemados P. Goyena 369 Tel. 4923-4082 / 3022 OFTALMOLOG´IA Hospital Santa Luc´ıa San Juan 2021 Tel. 4941-7077 Hospital Dr. P. Lagleyze Av. Juan B. Justo 4151 Tel. 4581-0645 / 2792 b. Incendio Mantenga la calma. Lo m´ as importante es ponerse a salvo y dar aviso a los dem´as. Si hay alarma, acci´ onela. Si no grite para alertar al resto. Se dar´ a aviso inmediatamente al Departamento de Seguridad y Control (Interno 311) informando el lugar y las caracter´ısticas del siniestro. Si el fuego es peque˜ no y sabe utilizar un extintor, u ´selo. Si el fuego es de consideraci´on, no se arriesgue y manteniendo la calma ponga en marcha el plan de evacuaci´on. Si debe evacuar el sector apague los equipos el´ectricos y cierre las llaves de gas y ventanas. Evacue la zona por la ruta asignada. No corra, camine r´ apido, cerrando a su paso la mayor cantidad de puertas. No utilice ascensores. Descienda siempre que sea posible. No lleve consigo objetos, pueden entorpecer su salida. Si pudo salir, por ninguna causa vuelva a entrar. Deje que los equipos especializados se encarguen. Tel´efonos u ´tiles: BOMBEROS: Tel´efono 100 2

´ CENTRAL DE ALARMA: 4381-2222 / 4383-2222 / 4304-2222. DIVISION CUARTEL V DE BOMBEROS DE BELGRANO: Obligado 2254 Capital Tel. 4783-2222 ´ BOMBEROS DE VICENTE LOPEZ: Av. Maip´ u 1669 Vicente L´opez. Tel. 4795-2222 BOMBEROS DE SAN ISIDRO: Santa Fe 650 Mart´ınez. Tel. 747-2222 c. Corriente el´ ectrica Es imprescindible la concientizaci´ on del riesgo que engendra la corriente el´ectrica. Ya que si bien no es la mayor fuente de accidentes, se trata generalmente de accidentes graves, en muchos casos mortales. Los incendios provocados por causas el´ectricas son muy frecuentes. Ellos ocurren por: sobrecalentamiento de cables o equipos bajo tensi´ on debido a sobrecarga de los conductores; sobrecalentamiento debido a fallas en termostatos o fallas en equipos de corte de temperatura; fugas debidas a fallas de aislaci´ on; autoignici´ on debida a sobrecalentamiento de materiales inflamables ubicados demasiado cerca o dentro de equipos bajo tensi´ on, cuando en operaci´on normal pueden llegar a estar calientes; ignici´ on de materiales inflamables por chispas o arco. Shock El´ectrico Un shock el´ectrico puede causar desde un sensaci´on de cosquilleo hasta un desagradable est´ımulo doloroso resultado de una p´erdida total del control muscular y llegar a la muerte. Control de los riesgos el´ectricos Los factores principales a considerar son: el dise˜ no seguro de las instalaciones el dise˜ no y construcci´ on de los equipos de acuerdo a normas adecuadas la autorizaci´ on de uso despu´es que se ha comprobado que es seguro el mantenimiento correcto y reparaciones las modificaciones que se efect´ uen se realicen seg´ un normas Las precauciones generales contra el shock el´ectrico son: la selecci´ on del equipo apropiado y el ambiente adecuado las buenas pr´ acticas de instalaci´ on el mantenimiento programado y regular el uso de acuerdo a las instrucciones del fabricante La protecci´ on contra el shock el´ectrico se consigue usando: equipos de maniobra con baja tensi´on la doble aislaci´ on o la construcci´ on aislada las conexiones a tierra y la protecci´on por equipos de desconexi´on autom´atica la separaci´ on el´ectrica entre las fuentes y la tierra Frecuentemente se usan adaptadores de enchufes. Tenga siempre en cuenta que cuando se usan estos aditamentos puede desconectarse la tierra del equipo que est´a usando.

3

Informaci´ on sobre la materia Programa 1 A ser completado

4

R´ egimen de aprobaci´ on 1. Habr´ a dos instancias de evaluaci´ on de la materia para aprobar los pr´acticos, una a mediados del cuatrimestre y la otra al final. 2. Cada instancia de evaluaci´ on es un examen individual, con fechas de entrega el 27/05/09 y 02/07/09, respectivamente. 3. Se podr´ a recuperar una vez cada instancia de evaluaci´on. Ambos recuperatorios son ex´amenes escritos, que se tomar´ an al final del cuatrimestre. 4. Para aprobar los pr´ acticos y poder dar final como alumno regular, se requiere haber aprobado las dos instancias de evaluaci´ on con nota 5 (cinco) o m´as en cada una. La aprobaci´on de los trabajos pr´acticos se firmar´ au ´nicamente en las fechas de toma o entrega de ex´amenes del primer cuatrimestre de 2009. No se firmar´ an los pr´ acticos despu´es de comenzado el siguiente cuatrimestre. 5. Para aprobar la materia por promoci´ on (es decir, sin rendir examen final) se requiere: a. Haber aprobado las dos instancias de evaluaci´on y tener 7 o m´as de promedio. Un promedio decimal inferior a 7 no se considera promocionado. b. Tener los finales de las correlativas aprobados antes de la u ´ltima fecha de finales del segundo cuatrimestre de 2009. Las promociones se firmar´ an u ´nicamente en cualquier fecha convenida con el profesor. No se firmaran promociones luego de la u ´ltima fecha de final del segundo cuatrimestre de 2009. 6. Tanto para firmar los pr´ acticos como para la promoci´on la nota puede ser la obtenida en el recuperatorio. 7. Toda informaci´ on referente a la materia ser´a publicada en la p´agina web y/o ser´a enviada a la lista de alumnos de la materia por e-mail.

Sobre la dificultad de los ejercicios Los ejercicios de esta gu´ıa practica pueden estar marcados con una cantidad de estrellas que indican la dificultad de cada ejercicio de acuerdo a las expectativas de los docentes. Los ejercicios con tres estrellas se corresponden a problemas de investigaci´on que fueron resueltos en la literatura y podr´ıan resolverse con las definiciones dadas en clase y/o en las pr´acticas. Los ejercicios con dos estrellas requieren un buen manejo de muchas de las definiciones y conceptos que se introducen en el curso. En las instancias de evaluaci´ on los ejercicios van a tener un nivel similar a los ejercicios de una estrella, siempre de acuerdo a la consideraci´ on de los docentes. Por lo tanto no es necesario resolver todos los ejercicios para aprobar la materia, pero se recomienda fuertemente intentar los ejercicios con dos estrellas, ya que permiten profundizar en los temas de la materia y obtener un buen manejo de las t´ecnicas y definiciones ense˜ nadas.

5

Bibliograf´ıa Los docentes de la materia no conocen ning´ un material bibliogr´afico que se ajuste exactamente a los contenidos de la materia. Los apuntes de las clases te´oricas y pr´acticas deber´ıan ser suficientes para poder realizar todos los pr´ acticos de la materia. Recomendamos los siguientes libros para profundizar en cada uno de los temas, que pueden ser solicitados a los docentes por parte de los alumnos.

Complejidad abstracta [1] M. R. Garey and D. S. Johnson, Computers and intractability; a guide to the Theory of NPCompleteness, Freeman, San Francisco, Calif., 1979.

Grafos de intersecci´ on: cubren casi todos los temas de la materia [2] BLS A. Brandst¨ adt, V. B. Le and J. P. Spinrad, Graph classes: a survey, SIAM, Philadelphia, PA, 1999. [3] M. C. Golumbic, Algorithmic graph theory and perfect graphs, Second edition, Elsevier, Amsterdam, 2004. [4] T. A. McKee and F. R. McMorris, Topics in intersection graph theory, SIAM, Philadelphia, PA, 1999. [5] J. P. Spinrad, Efficient graph representations, Amer. Math. Soc., Providence, RI, 2003.

Teor´ıa de grafos b´ asica [6] J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. Una versi´ on para uso personal se encuentra disponible en la pagina de Adrian Bondy: http://www.ecp6.jussieu.fr/pageperso/bondy/bondy.html [7] J. L. Gross and J. Yellen, Graph theory and its applications, Second edition, Chapman & Hall/CRC, Boca Raton, FL, 2006. [8] F. Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass., 1969.

Algoritmos y Estructuras de Datos. Nociones b´ asicas de complejidad [9] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to algorithms, Second edition, MIT Press, Cambridge, MA, 2001.

6

Pr´ actica 1

Referencias para este pr´ actico:

T´ ecnicas Algor´ıtmicas 1.1 Hay que organizar un torneo que involucre a n competidores. Cada competidor debe jugar exactamente una vez contra cada uno de sus oponentes. Adem´as cada competidor debe jugar un partido por d´ıa con la sola posible excepci´ on de un d´ıa en el cual no juegue. a. Si n es potencia de 2 dar un algoritmo que use la t´ecnica de dividir y conquistar para armar el fixture para que el torneo termine en n − 1 d´ıas. b. Si n > 1 no es potencia de 2 dar un algoritmo para armar el fixture para que el torneo termine en n − 1 d´ıas, si n es par o en n, si n es impar. 1.2 a. Se quiere dar el vuelto a un cliente usando el m´ınimo n´ umero de monedas posibles. Suponga que hay una cantidad suficientemente grande de monedas de 1, 5, 10 y 25 centavos. Analizar el siguiente algoritmo goloso para resolver el problema: Elegir en cada paso la moneda de mayor valor entre las disponibles. Probar que siempre existe una u ´nica soluci´on que es encontrada por el algoritmo goloso, para estos valores de las monedas. b. Mostrar ejemplos que muestren que si tambi´en hay monedas de 12 centavos, o si no hay al menos una moneda de cada tipo, puede ocurrir que el algoritmo no encuentre una soluci´on aunque la haya. c. Dise˜ nar un algoritmo de programaci´on din´amica que determine si hay o no soluci´on cuando las monedas tienen cualquier valor, siempre suponiendo que hay infinitas monedas de cada valor. Dise˜ nar tambi´en un algoritmo que muestre la soluci´on, en caso de existir. d. Suponga que el vuelto a dar en el ´ıtem (c) es x ∈ N. Considere el grafo G = (V, E) donde V es el conjunto de los n´ umeros naturales entre 0 y x, y v → w ∈ E cuando w − v es el valor de una moneda. Demuestre que el problema tiene soluci´on si y s´olo si 0 y x pertenecen a la misma componente conexa. ¿C´ omo se encuentra la soluci´on en este caso?. Justificar. 1.3

??

Sean u y v dos string de caracteres. Queremos transformar u en v con el menor n´ umero de operaciones posibles de alguno de los siguientes tipos: borrar un caracter agregar un caracter cambiar un caracter

a. Por ejemplo, uno puede transformar u = abbac en v = abcbc en tres pasos, (borrar b del segundo lugar de u, agregar b en el pen´ ultimo lugar, cambiar la a que est´a en el tercer lugar a c) ¿Es esta forma de transformar u en v ´optima? b. Escribir un algoritmo de programaci´on din´amica que encuentre el m´ınimo n´ umero de operaciones necesarias para transformar u en v e informe cu´ales son las operaciones necesarias. ¿Cu´al es la complejidad del algoritmo en funci´ on de las longitudes de u y v?

7

Complejidad y NP-completitud Para cada uno de los ejercicios de grafos, vamos a suponer que la representaci´on del grafo es su lista de adyacencias. O sea, G viene representado por un conjunto de n v´ertices v1 , . . . , vn y n listas N (v1 ), . . . , N (vn ) donde N (vi ) tiene los v´ertices adyacentes de vi en cualquier orden. El tama˜ no de esta representaci´ on es O(n + m). Las otras representaciones usuales para grafos (matriz de adyacencias, matriz de incidencia, lista de aristas) pueden ser calculadas a partir de las listas de adyacencias de manera “eficiente”. 1.4 Indique si cada una de las siguientes afirmaciones es verdadera o falsa. Justifique. a. El algoritmo b´ asico para sumar dos n´ umeros naturales, que consiste en sumar cada uno de sus d´ıgitos, es lineal. b. El algoritmo b´ asico para sumar dos vectores de n´ umeros naturales, que consiste en sumar cada una de sus coordenadas, es lineal. c. El algoritmo b´ asico para sumar dos matrices de Nn×m , que consiste en sumar cada uno de sus elementos, es lineal. d. El algoritmo b´ asico para determinar si un n´ umero n es primo, que consiste en verificar que ning´ un √ elemento del conjunto {1, . . . , n} lo divida, es polinomial. e. Los algoritmos BFS y DFS se pueden implementar en tiempo lineal. f. La matriz de adyacencia tiene un tama˜ no lineal con respecto al grafo que representa. 1.5 Indique si cada una de las siguientes afirmaciones es verdadera o falsa. Justifique. a. Cualquier problema polinomial es reducible en tiempo polinomial a cualquier otro problema no trivial (i.e., que tiene al menos una instancia positiva y otra negativa) b. Si Π ≤p Π0 y Π0 es NP-completo, entonces Π es NP. c. Si Π ≤p Π0 y Π es NP-completo, entonces Π0 es NP-completo. d. Si Π ≤p Π0 y Π0 es P, entonces Π es P. e. El problema de determinar si una f´ ormula es una tautolog´ıa es co-NP. f. Si el problema de determinar si una f´ormula es una tautolog´ıa es P entonces P = NP. 1.6 Indique cu´ al ser´ıa un certificado positivo para cada uno de los siguientes problemas que se pueda autenticar en tiempo polinomial. ¿C´ omo es el algoritmo de autenticaci´on?. a. SAT: ¿es una f´ ormula satisfactible?. b. Camino m´ınimo: ¿existe en un grafo un camino de longitud menor o igual a un k dado?. c. Coloreo: ¿existe un coloreo v´ alido con menos de k colores? d. Clique m´ axima: ¿existe un subgrafo completo de tama˜ no mayor a k? e. Bipartito: ¿es un grafo bipartito? 1.7 Indique cu´ al ser´ıa un certificado negativo para cada uno de los siguientes problemas que se pueda autenticar en tiempo polinomial. ¿C´ omo es el algoritmo de autenticaci´on?. a. Tautolog´ıa: ¿es una f´ ormula una tautolog´ıa?. b. Primo: ¿es primo un n´ umero?. c. Bipartito: ¿es un grafo bipartito? d. Even pair (dupla par): ¿hay dos v´ertices de un grafo cuyos caminos inducidos sean todos de longitud par? 1.8 Demostrar que el problema de determinar si un grafo contiene una clique de tama˜ no mayor o igual a k es polinomialmente equivalente al problema de determinar si un grafo contiene un conjunto independiente de tama˜ no mayor o igual a k. 1.9

???

Sea Φ = C1 ∧ C2 ∧ . . . Ck instancia de 3-SAT, o sea, Ci = Xi1 ∨ Xi2 ∨ Xi3 , donde Xij es una variable o la negaci´ on de una variable. Sea G el grafo definido de la siguiente forma. Ver Figura 1 para un ejemplo 8

T

F

c1

c2

k2

k1

Figura 1.1: Ejemplo del grafo de formula Φ = (p ∨ q ∨ ¬r) ∧ (¬p ∨ q ∨ r) Por cada cl´ ausula Ci , G tiene dos v´ertices ci , ki , un v´ertice xij por cada literal Xij y cuatro v´ertices yi1 , yi2 , yi3 , yi4 . Adem´ as G tiene dos v´ertices T y F . ki es adyacente u ´nicamente a yi1 , yi2 y xi3 . ci es adyacente a xij y a T, F para 1 ≤ j ≤ 3. xi1 , yi1 , yi2 , xi2 , yi3 , yi4 , xi3 forman un camino en ese orden. xij es adyacente a xkl si los literales Xij y Xkl son uno la negaci´on del otro. Por cada conjunto maximal de literales iguales L se tiene dos v´ertices AL , BL que son adyacentes entre s´ı y adyacentes a todos los v´ertices xij correspondientes a literales de L. a. El problema 3-NAESAT consiste en determinar si una f´ormula Φ de 3-SAT es satisfacible con una asignaci´ on de valores de verdad donde cada cl´ausula tiene un literal verdadero y otro falso. Demostrar que G es 3-coloreable si y s´olo si Φ b. Sabiendo que 3-NAESAT es NP-completo, concluir que el problema de 3-colorear un grafo es NP-completo. Comentario: se puede demostrar que el problema de determinar si un grafo sin tri´ angulos y con grado m´ aximo a lo sumo 4 se puede 3-colorear es NP-completo.

Algoritmos y problemas b´ asicos en grafos 1.10 Considere el siguiente para determinar la componente conexa de G que contiene al v´ertice v. PASO 1: Poner T = ({v}, ∅) con v sin marcar. PASO 2: Mientras existan v´ ertices de T sin marcar, hacer: PASO 3: PASO 4: PASO 5:

Elegir un v´ ertice w de T no marcado de alguna forma. Agregar a T el conjunto N de vecinos de w que no est´ an en T , agregando una arista de w a cada v´ ertice de N . Marcar w.

PASO 6: Devolver T . a. Demostrar que T es un ´ arbol generador de la componente conexa de G que contiene a v. b. Describir una implementaci´ on de este algoritmo que genere el ´arbol BFS y otra que genere el arbol DFS. ¿Cu´ ´ al es la complejidad de este algoritmo en estos casos?. c. Dar un algoritmo lineal para determinar las componentes conexas de G. 1.11 El siguiente algoritmo se conoce con el nombre de algoritmo secuencial de coloreo y sirve para colorear un grafo G. El input del algoritmo es un grafo G y un ordenamiento v1 , . . . , vn de sus v´ertices. PASO 1: Para i desde 1 hasta n, pintar a vi con el m´ ınimo color no utilizado por los v´ ertices de v1 , . . . , vi−1 que son adyacentes a vi . 9

PASO 2: Devolver el coloreo c obtenido.

a. Demostrar que c es un coloreo v´ alido de G, independientemente de cu´al sea el ordenamiento de sus v´ertices. b. ? Exhibir un grafo bipartito G y un ordenamiento de sus v´ertices, para el cual el algoritmo secuencial consuma O(n) colores. c. Demostrar que para todo grafo existe un ordenamiento v1 , . . . , vn de sus v´ertices, de forma tal que el algoritmo secuencial con ese ordenamiento consuma χ(G) colores. d. Demostrar usando (c) que los grafos bipartitos se pueden colorear en tiempo O(n + m). 1.12 En un grafo G, dos v´ertices v y w se dicen mellizos cuando N [v] = N [w]. a. Demuestre que la relaci´ on de ser mellizos es una relaci´on de equivalencia. O sea, probar que es reflexiva, sim´etrica y transitiva. Concluir que V (G) se puede particionar en clases de equivalencia. b.

??

Dar un algoritmo de complejidad lineal que calcule la partici´on de V (G) en clases de equivalencia con respecto a la relaci´ on de ser mellizos.

1.13 Sean v y w dos v´ertices mellizos en G. Demostrar que toda clique que contiene a v tambi´en contiene a w. Demostrar que si Q es una clique de G entonces Q \ {v} es una clique de G \ {v}. 1.14 Dos v´ertices v y w se dicen similares si N (v) = N (w). Demostrar que Q es una clique de G que contiene a v si y s´ olo si (Q \ {v}) ∪ {w} es una clique de G. 1.15 Sean v y w dos v´ertices similares en G. Demostrar que χ(G) = χ(G) \ {v}. 1.16 El grafo que se obtiene de K4 eliminando una arista se llama diamante. Demostrar que G no contiene ning´ un diamante como subgrafo inducido si y s´olo si toda arista de G pertenece a una u ´nica clique. Dar un algoritmo eficiente para determinar la clique m´axima de un grafo que no contiene diamantes como subgrafos inducidos.

10

Pr´ actica 2

Referencias para este pr´ actico: Una clase de grafos es simplemente una familia de grafos que satisface alguna propiedad dada. Por ejemplo, la clase de los grafos que no contienen ciclos, se llaman ´ arboles. De la misma forma, podemos definir los grafos bipartitos, eulerianos, hamiltonianos, etc. En esta pr´actica nos dedicamos al estudio de algunos problemas para algunas clases de grafos particulares. En el resto de las pr´acticas nos vamos a dedicar con mayor profundidad a algunas de estas clases.

Grafos de intersecci´ on (l´ınea y clique) Sea F = {C1 , . . . , Cn } una familia de conjuntos, es decir, un multiconjunto que contiene conjuntos. El grafo de intersecci´ on G de F contiene un v´ertice vi por cada conjunto Ci y dos vertices vi y vj son adyacentes cuando Ci ∩ Cj 6= ∅ e i 6= j (a partir de ahora, la condici´on i 6= j queda sobreentendida). La familia F se llama representaci´ on de G. En general estaremos mas interesados por la pregunta inversa. Si G es un grafo, ¿existe una familia F cuyo grafo de intersecci´on sea G?. Es decir, se puede hacer corresponder cada v´ertice vi de G con un conjunto Ci de forma tal que vi y vj sean adyacentes si y s´olo si Ci ∩ Cj 6= ∅ (i 6= j). Si se adiciona una condici´on particular, se puede obtener la clase de grafos de intersecci´ on de familias que cumplen dicha condici´on. A continuaci´on damos una breve lista de algunas de estas clases de grafos de intersecci´ on. Grafo de intersecci´ on: son los grafos intersecci´on de alguna familia. Esta es la clase general, donde no se piden condiciones. Grafos de l´ınea: son los grafos de intersecci´on de las aristas de un grafo. Es decir, G es un grafo de l´ınea si cada v´ertice ei se puede hacer corresponder con una arista (vi , wi ) de un grafo H, de forma tal que ei es adyacente a ej en G si y s´olo si {vi , wi } ∩ {vj , wj } = 6 ∅. Grafos clique (resp. biclique): son los grafos de intersecci´on de las cliques (resp. bicliques) de un grafo. Es decir, G es un grafo clique (resp. biclique) si cada v´ertice ci de G se puede hacer corresponder con una clique (resp. biclique) Ci de un grafo H, de forma tal que ci es adyacente a cj si y s´ olo si V (Ci ) ∩ V (Cj ) 6= ∅. Grafos de intervalos: son los grafos de intersecci´on de intervalos en la recta real. Es decir, G es un grafo de intervalos si cada v´ertice v se puede hacer corresponder con un intervalo Iv de la recta real, de forma tal que v es adyacente a w si y s´olo si Iv e Iw comparten un punto de la recta. Grafos arco-circulares: son los grafos de intersecci´on de arcos de un c´ırculo. Es decir, G es un grafo arco-circular si cada v´ertice v se puede hacer corresponder con un arco Av de un c´ırculo C, de forma tal que v es adyacente a w si y s´olo si Av y Aw comparten un punto de C. En esta pr´ actica, vamos a llamar L(G) al grafo de l´ınea de G y K(G) al grafo clique de G. Es decir, L(G) es un grafo cuyos v´ertices son las aristas de G y donde dos v´ertices de L(G) son adyacentes cuando sus aristas inciden en un v´ertice en com´ un. Por otra parte K(G) es un grafo cuyos v´ertices son las cliques de G y dos v´ertices de K(G) son adyacentes si sus correspondientes cliques se intersecan.

2.1 Demostrar que todo grafo es un grafo de intersecci´on. HINT: considerar un conjunto Vi por cada v´ertice que contenga todas las aristas que inciden en v. 11

2.2 Demostrar que las clases de grafos de intervalos y de grafos arco-circulares son hereditarias. Es decir, que si G es de intervalos (arco-circular) entonces G \ {v} es de intervalos (arco-circular). 2.3 Demostrar que el grafo K1,3 no es un grafo de l´ınea. 2.4 Demostrar que el grafo C4 no es un grafo de intervalos. 2.5 Demostrar que todo grafo de intervalos es arco-circular, y que C4 ∪ K1 no es arco-circular. 2.6 Sea G = L(H). Demostrar que G0 es un subgrafo inducido de G si y s´olo si G0 es el grafo de l´ınea de un grafo H 0 que es subgrafo de H. 2.7 Sea G = L(H). Demostrar que G es completo si y s´olo si H es una estrella o un tri´angulo. 2.8

??

Sea G = L(H) y C1 , C2 dos cliques de G. Demostrar que |C1 ∩ C2 | < 3.

2.9 ? Demostrar que un grafo conexo G es isomorfo a su grafo de l´ınea si y s´olo si G es un ciclo. 2.10 Demostrar que si G no contiene tri´ angulos ni v´ertices aislados, entonces L(G) = K(G). 2.11 Demostrar que si G tiene mellizos v y w, entonces K(G) = K(G \ {v}). ¿Es cierta la rec´ıproca? 2.12 Demostrar que si G tiene v´ertices similares v y w, entonces K(G) tiene v´ertices mellizos. ¿Es cierta la rec´ıproca? 2.13

??

Sea G un grafo de l´ınea. Sabiendo que existe un algoritmo lineal que encuentra un grafo de H ∈ L−1 (G), dise˜ ne un algoritmo que encuentre la clique m´axima de G en tiempo lineal. HINT: Relacionar con el Ejercicio 7.

Grafos de superposici´ on y contenci´ on (overlap) Decimos que dos conjuntos C1 y C2 se superponen cuando C1 ∩ C2 6= ∅ y C1 6⊆ C2 y C2 6⊆ C1 . Dada una familia F = {C1 , . . . , Cn } de conjuntos, definimos el grafo de superposici´on G de F poniendo un v´ertice vi por cada conjunto Ci y haciendo que vi y vj sean adyacentes cuando Ci y Cj se superponen. Para los grafos de superposici´ on, valen las mismas consideraciones que para los grafos de intersecci´on. Dada una familia F podemos definir tambi´en el grafo de contenci´on poniendo un v´ertice vi por cada conjunto Ci , y haciendo que vi sea adyacente a vj cuando Ci ⊂ Cj o Cj ⊂ Ci . 2.14 Demostrar que todo grafo es un grafo de superposici´on. 2.15 Demostrar que los ciclos son grafos de contenci´on si y s´olo si tienen longitud par ´o tres. 2.16 Demostrar que si ning´ un conjunto F est´a contenido en otro conjunto entonces el grafo de intersecci´on de F es isomorfo al grafo de superposici´on de F. ¿Vale la rec´ıproca?. Concluir que los grafos de l´ınea y los grafos clique son los grafos de superposici´on de aristas y cliques de un grafo, respectivamente. 2.17

??

2.18

??

Los grafos circulares son los grafos de intersecci´on de cuerdas en un c´ırculo (ver Figura 2). Demostrar que un grafo es circular si y s´ olo si es el grafo de superposici´on de intervalos en la recta. Sea G un grafo de contenci´ on. Demostrar que existe una relaci´on transitiva R entre los v´ertices, donde v es adyacente a w en G si y s´ olo si vRw o wRv.

Potencias Dado un grafo G, se define el grafo Gk como un nuevo grafo que tiene los mismos v´ertices que G, pero donde dos v´ertices son adyacentes si la distancia en G es menor o igual a k. Una matriz de adyacencias aumentada de G es una matriz booleana de Nn×n , que tiene un 1 en la posici´on (i, j) si y s´olo si i = j o vi es adyacente a vj . La multiplicaci´ on 0, 1 de matrices se obtiene haciendo la multiplicaci´on usual y luego reemplazando cada valor positivo por un 1. A no ser que se aclare lo contrario, suponemos que la multiplicaci´ on y la potenciaci´ on son 0, 1. Un grafo G se llama k-potencia si existe H tal que G = H k . En tal caso, H es la ra´ız k-´esima de G. Los grafos 2-potencia son llamados grafos cuadrados.

12

Figura 2.1: Ejemplo de un modelo circular del grafo C5 m´as una cuerda corta. 2.19 Sea M una matriz de adyacencias aumentada de G. Demostrar que M k es una matriz de adyacencias aumentadas de Gk . 2.20 Demostrar que si un grafo G conexo con n > 2 tiene una hoja (v´ertice de grado 1) entonces G no es cuadrado. ¿Vale la rec´ıproca? 2.21

???

En este ejercicio demostramos que el problema de determinar si un grafo es cuadrado es NP-hard con una reducci´ on desde coloreo. Sea J = (V (J), E(J)) un grafo sin v´ertices universales y definamos G con los siguientes v´ertices y aristas. V´ertices de G: V (J) ∪ {1, 2, 3, 4, t} ∪ {Xvw : (v, w) 6∈ E(J)}. t es adyacente u ´nicamente a 1, 2, 3 y 4. v ∈ V (J) es adyacente a w ∈ V (J) en G si y s´olo si v y w no son adyacentes en J. Todos los v´ertices restantes son adyacentes entre s´ı. Supongamos que J es 3-coloreable y sea c un 3-coloreo. Definamos tambi´en H con los siguientes v´ertices y aristas. V´ertices de H: V (H) = V (G) t es adyacente u ´nicamente a 4 1, 2, 3, 4 es un completo de H Para todo v ∈ V (J), v es adyacente a c(v) y a todos los v´ertices de la forma Xvw Los v´ertices del tipo X forman un completo Xvw es adyacente a ambos c(v) y c(w) (puede ser que c(v) = c(w)) no hay mas aristas en H. a. Demostrar que si J es 3-coloreable entonces G es cuadrado. HINT: probar que H 2 = G. b. Demostrar que tambi´en vale la rec´ıproca, i.e., si G es cuadrado entonces J es 3-coloreable. HINT: probar que si existe H 2 = G, entonces cada v es adyacente a uno s´olo de 1, 2, 3 en H (que ser´a su color) y que si v y w son adyacentes, entonces no son adyacentes al mismo color. c. Demostrar que el problema de determinar si G es cuadrado es NP-completo, sabiendo que el problema de 3-colorear un grafo J sin v´ertices universales es NP-completo (ver ejercicio 9).

Clases por subgrafos inducidos prohibidos 2.22 Sea G un grafo y M su matriz de adyacencia. Demostrar que G contiene a K3 como subgrafo inducido si y s´ olo si existe una posici´on (i, j) tal que M (i, j) = M 2 (i, j) = 1. Usando esta idea, dise˜ nar un algoritmo de complejidad O(nα ) para encontrar un tri´angulo si es que existe. HINT: usar directamente que M k (i, j) es la cantidad de caminos de longitud k entre vi y vj . 2.23 Dise˜ nar un algoritmo eficiente, usando el ejercicio anterior, para determinar si un grafo contiene a K1,3 como subgrafo inducido. 2.24 Dise˜ nar un algoritmo polinomial para determinar si un grafo contiene alg´ un diamante como subgrafo inducido. ¿Cu´ al es la complejidad del algoritmo? 13

2.25

??

Dise˜ ne un algoritmo de complejidad O(nm) para determinar si un grafo contiene diamantes. Comentario: el mejor√algoritmos que conocemos para encontrar un diamante tiene complejidad O(mα). Ac´ a α = O( m) es la cantidad m´ınima de bosques en la que se pueden particionar las aristas del grafo.

2.26 Estudio de los grafos threshold (umbral), con una definici´on alternativa. La definici´on usual es: un grafo G es threshold si se puede definir una funci´on de pesos wP : V (G) → R≥0 y un umbral t ∈ R≥0 de forma tal que X sea un conjunto independiente si y s´olo si v∈X w(v) ≤ t. Se puede demostrar que G es un grafo threshold si y s´ olo si G se puede obtener iterativamente agregando v´ertices aislados o universales, empezando desde el grafo trivial. a. Demuestre que P4 , C4 y 2K2 no son grafos threshold, usando alguna de las dos definiciones. b. ? Demuestre las siguientes equivalencias usando la segunda definici´on G es un grafo threshold. Para todo par de v´ertices v, w con d(v) ≥ d(w) ocurre que N (w) \ {v} ⊂ N (v) \ {w}. G no contiene a P4 , C4 y 2K2 como subgrafos inducidos. c. ? Sea D(G) el multiconjunto {d(v)}v∈V (G) . Demuestre por inducci´on en la cantidad de v´ertices que dos grafos threshold G y H son isomorfos si y s´olo si D(G) = D(H). Como corolario se obtiene que el problema de determinar si dos grafos threshold son isomorfos es lineal. d. ? Dise˜ nar un algoritmo de complejidad O(n + m) para decodificar G a partir de D(G) cuando G es threshold. e. ? Dise˜ nar un algoritmo lineal O(n + m) para determinar si un grafo es threshold. Si el grafo no es threshold, el algoritmo debe mostrar un certificado negativo. f.

??

Demostrar que con cualquier orden de los v´ertices el algoritmo secuencial de coloreo colorea un grafo threshold de forma ´ optima. Comentario: este resultado se puede generalizar para los grafos que no contienen a P4 como subgrafo inducido.

14

Pr´ actica 3

Referencias para este pr´ actico:

Grafos cordales Un grafo es cordal si en todo ciclo de longitud mayor o igual a 4 hay una cuerda. Un agujero es un ciclo sin cuerdas de longitud al menos 4 (trivialmente no es cordal). Un v´ertice es simplicial cuando su vecindario es un subgrafo completo. Un orden de eliminaci´ on perfecta de G es una secuencia v1 , . . . , vn de sus v´ertices donde vi es simplicial en el subgrafo inducido por vi , . . . , vn para todo 1 ≤ i ≤ n. Un (a, b)-separador S es un subconjuto de V (G) tal que a y b pertenecen a dos componentes disjuntas de G \ S.

3.1 Convercerse que G es un grafo cordal si y s´olo si no contiene ning´ un agujero como subgrafo inducido. 3.2 Demostrar que v es un v´ertice simplicial de G si y s´olo si N [v] es una clique de G. 3.3

??

Demostrar que si G es cordal entonces G tiene un v´ertice simplicial. M´as a´ un, si G no es completo, entonces tiene dos v´ertices simpliciales no adyacentes. Para ello puede usar los siguientes lemas, que deber´ıa probar, en una demostraci´ on por inducci´on. a. Si un grafo conexo cualquiera contiene dos v´ertices no adyacentes a y b entonces existe un (a, b)separador minimal.

b. Todo (a, b)-separador minimal S de G es un conjunto completo. c. Sea G0 una componente conexa de G \ S. Si x, y son v´ertices simpliciales no adyacentes de G0 entonces alguno de los dos es simplicial en G. 3.4 Demostrar que G es cordal si y s´ olo si G tiene un orden de eliminaci´on perfecta. HINT: usar el hecho de que los grafos cordales son hereditarios, junto con el ejercicio anterior para la ida. Usar inducci´on para la vuelta. 3.5 Demostrar que G tiene a lo sumo n cliques. HINT: usar el orden de eliminaci´on perfecta. 3.6 Demostrar las siguientes propiedades de un ´arbol T . a. ? Sea T = {T1 , . . . , Tk } una familia de sub´arboles de T que se intersecan en v´ertices dos a dos (o T sea, V (Ti ) ∩ V (Tj ) 6= ∅ para todo 1 ≤ i, j ≤ k). Demostrar que V (Ti ) 6= ∅. Esta familia se dice que satisface la propiedad de Helly, que veremos con mayor profundidad m´as adelante. b. ? Demostrar que si F = T1 , . . . , Tn es una familia de sub´arboles de T entonces el grafo intersecci´on de F es cordal. La vuelta se demuestra en el ejercicio siguiente. 3.7

??

Sean v1 , . . . , vn los v´ertices de un grafo G cordal. Demostrar que existe una familia de sub´arboles T1 , . . . Tn de un ´ arbol T donde V (Ti )∩V (Tj ) 6= ∅ si y s´olo si vi , vj ∈ E(G). Como corolario obtenemos que G es cordal si y s´ olo si es el grafo de intersecci´on de sub´arboles de un ´arbol. HINT: Probarlo por inducci´ on en usando el orden de eliminaci´on perfecta y la propiedad de Helly del ejercicio anterior.

3.8 ? Demostrar que χ(G) = ω(G) cuando G es cordal. HINT: sea v1 , . . . , vn un orden de eliminaci´on perfecta de G. Demostrar que si el algoritmo de coloreo secuencial usando el orden vn , . . . , v1 tiene que colorear al v´ertice vi con el color k, entonces vi pertenece a un completo de tama˜ no k.

15

3.9 Dise˜ nar un algoritmo lineal O(n + m) para encontrar la clique m´axima y el coloreo m´ınimo de un grafo cordal al mismo tiempo. HINT: intentar este ejercicio despues de resolver el anterior. 3.10 ? Considere el algoritmo goloso para encontrar un conjunto independiente S a partir de un orden v1 , . . . , vn de los v´ertices, donde en cada paso el v´ertice vi se agrega al conjunto S si y s´olo si N (vi ) ∩ S = ∅. Demostrar que el conjunto S as´ı calculado es ´optimo para el orden de eliminaci´on perfecta v1 , . . . , vn . 3.11

??

Dise˜ nar un algoritmo de complejidad O(n + m) para listar todas las cliques de un grafo cordal.

Grafos split Un grafo es split cuando tanto ´el como su complemento son cordales. Las propiedades principales se prueban en los siguientes ejercicios.

3.12 Demostrar que G es split si y s´ olo si no contiene a C4 , 2K2 ni C5 como subgrafos inducidos. 3.13 Demostrar que G es split si y s´ olo si sus v´ertices se pueden particionar en dos conjuntos V1 , V2 (quiz´ a V2 = ∅) de forma tal que V1 es un completo y V2 es un conjunto independiente. A partir de ahora notamos G = (K ∪ I, E) a un grafo split donde K es un completo, S es un conjunto independiente y E son las aristas entre K y S. 3.14 Sea s1 , . . . , si un orden de S y k1 , . . . , kj un orden de K en un grafo split G = (K ∪ S, E). Demostrar que s1 , . . . , si , k1 , . . . , kj es un orden de eliminaci´on perfecta de G y que k1 , . . . , kj , s1 , . . . , si es un orden de eliminaci´ on perfecta de G. 3.15

??

3.16

???

Demostrar que un grafo es split si y s´olo si es el grafo de intersecci´on de sub´arboles distintos de una estrella. ¿Qu´e ocurre si los sub´ arboles no son todos distintos? En este ejercicio demostramos que el problema de determinar si G es el cuadrado de un grafo split es NP-completo. Formalmente, queremos saber si G = H 2 para alg´ un grafo H que sea split. El problema que vamos a reducir se llama INTERSECTION GRAPH BASIS, queSconsiste en determinar si un grafo G es el grafo de intersecci´on de una familia F donde su base F tiene a lo sumo k elementos. Sea J un grafo cualquiera que ser´a el grafo para el que queremos determinar si tiene una base de tama˜ no menor o igual a k. Sea G el grafo que se obtiene de J al agregar k v´ertices universales. Si J es el grafo de interseccion de F cuya base tiene elementos w1 , . . . , wj de tama˜ no j ≤ k, se define H como el grafo split con v´ertices V (G) ∪ W donde W = {w1 , . . . , wk } es completo y V (G) es independiente, y adem´ as tenemos que vi es adyacente a wj si wj pertenece al conjunto que representa a vi en F. a. Demostrar que si J tiene una base de tama˜ no menor a k entonces H 2 = G. b. Demostrar que si G = (K ∪ S, E)2 entonces J tiene una base de tama˜ no a lo sumo k. HINT: probar que K se va a corresponder con la base.

16

Pr´ actica 4

Referencias para este pr´ actico:

Grafos de intervalos Un modelo de intervalos es una familia de intervalos abiertos en una recta R≥0 . Un grafo es de intervalos (IG) si es el grafo de intersecci´ on de un modelo de intervalos, que se llama su representaci´ on o modelo. Cada intervalo (a, b) tiene una longitud, definida como b − a. Un modelo de intervalos es propio si ning´ un intervalo esta contenido en otro, y es unitario si todo par de intervalos tiene la misma longitud. Un grafo es de intervalos propios (PIG) si admite una representaci´on propia, mientras que es unitario (UIG) si admite una representaci´ on unitaria. Si los v´ertices de G son v1 , . . . , vn , vamos a denotar (si , ti ) al intervalo Ii correspondiente a vi . De la misma forma, si {I1 , . . . , In } es un modelo de intervalos, vamos a llamar vi al v´ertice correspondiente a Ii . A los puntos si y ti se los llama extremo izquierdo y derecho, respectivamente. Sin perdida de generalidad vamos a suponer, siempre que no se diga lo contrario, que s1 , . . . , sn es el orden en que aparecen los extremos izquierdos cuando se recorre la recta desde 0 hasta ∞. ~ que se obtiene orientando cada arista (v, w) de G Una orientaci´ on de un grafo G es un digrafo G ~ en alguna de sus dos direcciones. Si G es una orientaci´on, entonces NG (v) se puede particionar en dos conjuntos: N − (v) son los v´ertices que tienen una arista hacia v y N + (v) son los v´ertices que tienen una ~ es un ordenamiento v1 , . . . , vn de sus arista desde v. Una enumeraci´ on consecutiva de una orientaci´on G v´ertices, de forma tal que para todo v´ertice vi , existen 1 ≤ l ≤ i ≤ r ≤ n tal que N − (vi ) = {vl , . . . , vi−1 } y N + (vj ) = {vi+1 , . . . , vr }. Por u ´ltimo, un grafo se dice consecutivo si tiene una orientaci´on que admita una enumeraci´ on consecutiva. Una tripla asteroidal en un grafo G es un conjunto de tres v´ertices v1 , v2 , v3 tales que existe un camino desde vi a vj que no pase por vk para todo {i, j, k} = {1, 2, 3}. 4.1 ? Sea {I1 , . . . , In } un modelo de intervalos de un grafo G. Demostrar que existe otro modelo de un extremo comparte un punto de la recta. intervalos {I10 , . . . , In0 } de G, donde |Ii | = |Ii0 | y ning´ HINT: desplazar todos los extremos izquierdos hacia la derecha, en un valor “adecuado”. 4.2 Encontrar una tripla asteroidal en cada uno de los grafos de la figura 4. 4.3 Demostrar que los grafos de intervalos son cordales y no contienen triplas asteroidales. 4.4

???

Demostrar la vuelta del ejercicio anterior, i.e., si un grafo cordal no contiene triplas asteroidales entonces el grafo es de intervalos.

Figura 4.1: Grafos del ejercicio 4.2 17

4.5 Demostrar que los grafos consecutivos son cordales. 4.6 Demostrar que un grafo es de intervalos propios si y s´olo si es de intervalos y no contienen al grafo K1,3 como subgrafo inducido. 4.7 Demostrar que vn , . . . , v1 es un orden de eliminaci´on perfecta de un grafo de intervalos. 4.8 ? Demostrar que un grafo es de intervalos propio si y s´olo si es consecutivo. HINT: ver que v1 , . . . , vn es una enumeraci´ on consecutiva. 4.9

??

Demostrar que G es un grafo de intervalos si y s´olo si es el grafo de intersecci´on de subcaminos de un camino.

4.10 Sea {I1 , . . . , In } una representaci´ on de intervalos de un grafo G. Si si y tj son extremos consecutivos en ese orden, entonces decimos que (si , tj ) es un segmento de intersecci´on. a. Demostrar que C es una clique de G si y s´olo si existe un segmento de intersecci´on que esta contenido en cada uno de los intervalos correspondientes a C. b. Demostrar que el segmento de intersecci´on correspondiente a la clique C es u ´nico. c.

Sean s01 , . . . , s0k los extremos izquierdos de cada segmento de intersecci´on (en orden) y t0i el extremo m´ as a la derecha de los intervalos que cruzan s0i . Considere el modelo I 0 que tiene un 0 intervalo Ii = (s0i , t0i ) por cada 1 ≤ i ≤ k. Demostrar que I 0 es un modelo de intervalos propios de K(G).

d.

??

??

Demostrar que si G es un grafo de intervalos propios, entonces existe un grafo de intervalos propios H tal que K(H) = G.

4.11 ? Usando el ejercicio anterior, demostrar que G es un grafo de intervalos si y s´olo si existe un orden C1 , . . . , Ck de las cliques de G de forma tal que todo v´ertice v pertenece a cliques consecutivas del orden. 4.12 Dise˜ nar un algoritmo que, dado un modelo de intervalos {I1 , . . . , In } donde cada intervalo tiene un peso asociado, encuentre la clique de mayor peso en tiempo O(n). 4.13 Demostrar que si G es de intervalos entonces Gk tambi´en es de intervalos. ¿Vale la reciproca?. 4.14 Demostrar que el grafo Pnk es un grafo de intervalos unitarios. 4.15

??

Demostrar que todo grafo de intervalos propios es un subgrafo inducido de Pnk para alg´ un par de valores n y k.

4.16 ? Demostrar que G es un grafo de intervalos propio si y s´olo si es de intervalos unitarios. HINT para la ida: sea H = Pnk de forma tal que G sea subgrafo inducido suyo. Encontrar un modelo unitario de H y luego tomar el modelo inducido por los intervalos correspondientes a v´ertices de G.

18