A mis hijos Pepe, Luca y Pupi, mi esposo Bernardo y mis padres Quique y Lida.


Save this PDF as:
 WORD  PNG  TXT  JPG

Tamaño: px
Comenzar la demostración a partir de la página:

Download "A mis hijos Pepe, Luca y Pupi, mi esposo Bernardo y mis padres Quique y Lida."

Transcripción

1 Universidad Nacional de La Plata Facultad de Ciencias Exactas Departamento de Matematica EL OPERADOR CLIQUE Y LOS GRAFOS PLANARES Autor: Liliana G. Alcon Director: Dra. Marisa Gutierrez Tesis para obtener el ttulo de DOCTOR EN CIENCIAS EXACTAS Marzo de 2003

2 A mis hijos Pepe, Luca y Pupi, mi esposo Bernardo y mis padres Quique y Lida.

3 Quiero expresar mi agradecimiento a las personas que directamente o indirectamente me han ayudado en la obtencion de este logro. A Nelly, Crisitina y Marite porque desde mi llegada a esta facultad en 1988, me brindaron su amistad y me dieron una posibilidad de trabajo. Al Dr. Toranzos por su direccion alla por A Marisa por haber aceptado ser mi directora, por la forma natural y sabia con que supo guiarme, por brindarme su tiempo, por socorrerme desinteresadamente en tantos tramites y situaciones (se~nora), y por haberme permitido compartir su amistad con personas maravillosas como Celina, Marcia, Jayme y Jo~ao, a quienes tambien agradezco su apoyo.

4 Contenido 1 Introduccion 1 2 Deniciones y Resultados Generales Familias de conjuntos Grafos El Operador Interseccion El Operador Clique K(Planares) y K ;1 (Planares) K(Planares) K(Planares) \ K 4 ; libre K(Planares) \ K 3 ; libre Ejemplos K ;1 (Planares) Grafos Planares Helly y 3-Helly Introduccion Las caracterizaciones K(Grafos) \ Planares Introduccion Triangulo extendido segun una familia de completos Condicion necesaria para grafo clique planar Triangulos extendidos de un Grafo Planar que son Grafos Cliques Asignacion Triangulo-Vertice Deniciones Una nueva caracterizacion de los Grafos Clique Ejemplos de Aplicacion

5 Bibliografa 83

6 Captulo 1 Introduccion Se llama completo de un grafo a un conjunto de vertices adyacentes entre s si un completo es maximal con respecto a la inclusion, se dice que es un clique del grafo. Los cliques son estructuras especiales que naturalmente han despertado interes desde el mismo inicio de la Teora de Grafos. Varios problemas famosos, como por ejemplo el problema de coloracion de un grafo, o el problema de satisfabilidad de una formula logica, se han vinculado y formulado en terminos de los clique de un grafo. Por otro lado, exite una gama de problemas motivados en el propio estudio de los cliques de un grafo. Particularmente haremos foco en el estudio del grafo que muestra la relacion de interseccion entre estos clique: el grafo clique. Dado un grafo G obtenemos el grafo clique de G considerando un vertice por cada clique de G y haciendo dos vertices adyacentes si los correspondientes clique tienen interseccion no vaca. De esta simple denicion surgen inmediatamente varias preguntas las siguientes tres son las que han dado origen a las tres principales lneas de investigacion: >Todo grafo es el grafo clique de algun grafo?. Dada una clase particular de grafos, >como es la clase formada por los grafos clique de los grafos dados?. El proceso, que partiendo de un grafo dado obtiene iterativamente el grafo clique del 1

7 grafo clique, >es convergente o genera una secuencia innita de distintos grafos?. En relacion con la primer pregunta el artculo de mas vieja data es el de Hamelink [14] donde se muestra que no todo grafo es grafo clique, y se da una condicion suciente para que un grafo sea grafo clique: que la familia de sus cliques tenga la propiedad de Helly (toda subfamilia mutamente intersectante tiene interseccion no vaca). A los grafos que satisfacen esta condicion les llamaremos grafos Helly. Posteriormente Robert y Spencer [22], continuando con las ideas de Hamelink, encuentran una condicion necesaria y suciente para que un grafo sea grafo clique: que exista una familia de completos (no necesariamente los cliques) que cubra las arista del grafo y que tenga la propiedad Helly. A tales familias le llamaremos familias R;S. Esta caracterizacion de los grafos clique, la unica conocida, no ha podido ser implementada en un algoritmo polinomial por lo que el problema de la complejidad del reconocimiento de los grafos clique continua abierto. Siguiendo esta lnea de trabajo, en [10] se desarrolla un algoritmo no polinomial para decidir si un grafo es grafo clique o no y en [12], se prueba que el problema de reconocimiento de los grafos clique puede reducirse al estudio de los grafos de diametro 2. En [11] se presenta una forma de obtener a partir de una familia R;S de un grafo G, otro grafo tal que su grafo clique sea G. La rama de investigacion surgida a partir de la segunda pregunta es mas reciente. Si llamamos K al operador que a cada grafo le hace corresponder su grafo clique, se trata del estudio de la imagen por el operador K de determinadas clases de grafos. En distintos artculos se ha caracterizado la imagen de las clases: Helly [8], Cordales y UV [27], DV y RDV [20], entre otras. En [9] se engloba varios de los artculos antes mencionados, mostrando que el comportamiento del operador clique es uniforme en ciertas clases de grafos de interseccion. En respuesta a la tercer pregunta, el estudio de la convergencia del operador clique, han surgido publicaciones como [5], [6], [7], [15], [16], [19], entre muchas otras. Para una vision actualizada, general pero detallada, de los prinicipales resultados obtenidos en las distintas lneas de investigacion, y de la bibliografa existente, el 2

8 lector interesado puede consultar [26]. Una muestra tanto de la importancia y actualidad como de la produccion en torno al estudio de los cliques de un grafo, es la realizacion del I Latinamerican Workshop on Cliques of Graphs (Rio de Janeiro, Abril 2002). Se espera que esta reunion cientca se desarrolle con cierta periodicidad en distintas ciudades de Latinoamerica. El presente trabajo se relaciona con la primera y segunda pregunta anteriormente planteadas. Buscamos caracterizar los grafos clique en general, y para esto ahondamos en el estudio de los grafos clique de una clase particular: los grafos planares y especialmente buscamos caractersticas de los grafos planares que son grafos clique. >Porque los grafos planares?. Por un lado, aunque en el contexto del estudio de la convergencia del operador, la investigacion del comportamiento del operador clique sobre la clase de los planares fue sugerida por Prisner en [19]. Por otro lado, consideramos que los grafos planares podan resultar accesibles dado que sus cliques contienen a lo sumo cuatro vertices, pero principalmente porque conocamos caracterizaciones de los grafos planares como grafos de interseccion [24], con lo cual esperabamos aplicar los resultados de [9]. Paradojicamente, no fue de all que surgieron los resultados que incluimos en esta Tesis. Mas, la tactica dio sus frutos: en base a lo observado sobre los grafo clique de los grafo planares y sobre los grafos planares que son grafos clique, logramos conclusiones sobre los grafos clique en general y obtuvimos una nueva caraterizacion de estos grafos. Esta Tesis esta organizada de la siguiente forma: En el Captulo 2 damos deniciones basicas y resultados generales sobre familias de conjuntos, grafos, y operadores. En el Captulo 3 estudiamos la imagen directa y la imagen inversa por el operador K, de la clase de los grafos planares. En el primer caso obtendremos distintas condiciones necesarias para que un grafo sea grafo clique de un grafo planar, y caracterizaremos totalmente los grafos K 3 ; libre y K 4 ; libre en estas condiciones. Si bien queda abierto el problema de caracterizar totalmente la clase K(Planares), la resolucion del caso de los grafos K 4 ; libre y de los grafos K 3 ; libre, nos da una idea de la 3

9 complejidad del problema planteado. En el segundo caso probaremos que determinar si el grafo clique de un grafo dado es planar, puede hacerse ecientemente. En el Captulo 4 damos una caracterizacion de los grafos planares Helly y de los 3-Helly, mediante una sencilla descripcion de los triangulos extendidos de estos grafos. En el Captulo 5 generalizamos la nocion de triangulo extendido y obtenemos un marco comun para los resultados de Szwarcter (que caracterizan a los grafos Helly) y de Roberts-Spencer (que caracterizan a los grafos clique). Damos una condicion necesaria para que un grafo planar sea grafo clique y caracterizamos totalmente los triangulos extendidos de un grafo planar que son grafos clique. Dejamos abierta una posibilidad de caracterizacion total de los grafos clique planares mediante la compatibilidad de los cubrimientos de sus triangulos extendidos. En el Captulo 6 mostramos que si a cada triangulo del grafo se le puede asignar un vertice, respetando ciertas condiciones, es posible construir a partir de estos vertices una familia R;S del grafo y viceversa. Obtenemos as unanueva caracterizacion de los grafos cliques. Finalmente presentamos ejemplos de aplicacion de la nueva caracterizacion de los grafos clique, mostrando hacia donde se encaminan nuestros proximos trabajos. Vale mencionar que de los resultados presentados en esta Tesis surgieron las publicaciones [1], [2], [3], y [4]. 4

10 Captulo 2 Deniciones y Resultados Generales En este captulo damos deniciones basicas y resultados generales sobre familias de conjuntos, grafos, operadores, que utilizaremos a lo largo de este trabajo y que son de uso corriente en Teora de Grafos. El objetivo del mismo es presentar claramente, para comodidad del lector, la notacion a utilizar y los resultados que damos por conocidos. No incluimos las demostraciones de estos ya que guran en la bibliografa citada. 2.1 Familias de conjuntos Sea I un conjunto nito y no vaco. Una familia de conjuntos con subndices en I es una secuencia nita de conjuntos nitos y no vacos, F = (F i ) i2i. Los miembros de la familia son los conjuntos F i. Los elementos de la familia son los elementos del conjunto [F = S i2i F i, es decir son los elementos de los conjuntos F i, miembros de F. Sean F =(F i ) i2i y M =(M j ) j2j familias de conjuntos. Decimos que F esta debajo de M, y lo notamos F M, si existe una aplicacion : I! J tal que para todo i 2 I se verica que F i M (i). 5

11 Decimos que F esta estrictamente debajo de M, ylo notamos F M, si existe una aplicacion : I! J, inyectiva, tal que para todo i 2 I se verica que F i M (i). Decimos que F es una subfamilia de M, y lo notamos F M, si existe una aplicacion : I! J, inyectiva, tal que para todo i 2 I se verica que F i = M (i). Es claro que si J 0 J entonces M 0 =(M j ) j2j 0 es una subfamilia de M. Es facil ver que F M implica F M y que F M implica F M, pero en general no valen las implicaciones recprocas. Por otra parte, F[Mindica la familia cuyos miembros son los miembros de F y los miembros de M. Sean u y v elementos de la familia de conjuntos F =(F i ) i2i, decimos que u esta separado de v en F, siexiste i 2 I tal que u 2 F i y v 62 F i. Es facil ver que u esta separado de v en F () v 62 \ F i (2.1.1) i2i=u2f i Si u no esta separado de v en F, decimos que u esta dominado por v en F o bien que v domina a u. Los elementos u y v estan separados si u esta separado de v y v esta separado de u. La familia F se dice separadora si todo par de elementos esta separado, o en otras palabras F es separadora si y solo si no hay en F elementos dominados. Son equivalentes F =(F i ) i2i separadora 8 u v 2[F 9i 2 I tal que u 2 F i y v 62 F i \ 8u 2[F fug = i2i=u2f i F i : (2.1.2) Una familia de conjuntos es mutuamente intersectante si todo par de miembros de la familia tienen interseccion no vaca. La interseccion total o interseccion de una familia F de conjuntos, es el conjunto interseccion de todos sus miembros, el cual denotaremos mediante \F. 6

12 Se dice que una familia de conjuntos tiene la propiedad de Helly o bien que es una familia Helly si toda subfamilia mutuamente intersectante tiene interseccion total no vaca. Analogamente dado k 2 N, una familia de conjuntos se dice k-helly si toda subfamilia mutuamente intersectante, con a lo sumo k miembros, tiene interseccion total no vaca. Proposicion [22] Una familia de conjuntos tiene la propiedad de Helly si y solo si dados tres elementos cualesquiera de la familia, la interseccion de todos los miembros de la familia que contienen al menos dos de los tres elementos dados, es no vaca. 2.2 Grafos Si V es un conjunto no vaco V [2] denota el conjunto de todos los subconjuntos de V que contienen exactamente dos elementos. Un grafo G es un par ordenado (V (G) E(G)) donde V (G) es un conjunto nito, no vaco, cuyos elementos llamamos vertices del grafo, y E(G) es un subconjunto de V (G) [2]. Los elementos de E(G) son las aristas del grafo. Grafos denota al conjunto de todos los grafos. En general indicamos con n a la cantidad de vertices del grafo y con m a la cantidad de aristas: n =j V (G) j, m =j E(G) j. Dos grafos G y G 0 son isomorfos si existe una aplicacion : V (G) ;! V (G 0 ), biyectiva, tal que E(G 0 )=ff (u) (v)g fu vg2e(g)g. Es facil ver que la relacion binaria entre grafos denida por "es isomorfo a", es una relacion de equivalencia. Salvo que se haga mencion en contrario, a lo largo de este trabajo consideraremos como iguales a grafos isomorfos. Decimos que dos vertices, u y v, son adyacentes o vecinos en G y notamos u G v, si fu vg 2 E(G). Si dos vertices de G no son adyacentes notamos u 6 G v. En lo que sigue una arista e = fu vg, se denotara uv u y v se dicen los vertices extremos de e. Una arista e es incidente en un vertice v, si v es un vertice extremo de e. Si v es un vertice de G el entorno abierto de v en G es el conjunto de vertices de G 7

13 adyacentes a v. N G (v) =fw 2 V (G)= w G vg: El entorno cerrado de v incluye ademas al vertice v. N G [v] =N G (v) [fvg: Un vertice v se dice aislado si N G (v) =. Un vertice v se dice universal de G si N G [v] =V (G). El grado en G de un vertice v es el numero de aristas de E(G) incidentes en el. d G (v) =j N G (v) j : En todos los casos anteriores si el contexto es claro puede omitirse el subndice G. Decimos que G 0 =(V (G 0 ) E(G 0 )) es un subgrafo de G =(V (G) E(G)) cuando, V (G 0 ) V (G) ye(g 0 ) E(G): Si V 0 V (G), el subgrafo de G inducido por V 0 es el grafo G[V 0 ]talque V (G[V 0 ]) = V 0 E(G[V 0 ]) = E(G) \ V 0 [2] : Si E 0 E(G), el subrafo de G inducido por E 0 es el grafo G[E 0 ] tal que V (G[E 0 [ ]) = e E(G[E 0 ]) = E 0 : e2e 0 G 0 se dice subgrafo inducido de G, si G 0 = G[V (G 0 )]. Usaremos la notacion G 0 G y G 0 G para indicar que G 0 es un subgrafo y, respectivamente, un subgrafo inducido de G. 8

14 Si V 0 V (G), G;V 0 es el grafo que se obtiene quitando a G los vertices pertenecientes a V 0 y las aristas incidentes en estos vertices. G ; V 0 = G[V (G) ; V 0 ]: Si E 0 E(G), G;E 0 es el grafo que se obtiene quitando a G las aristas pertenecientes a E 0, pero no sus vertices extremos. V (G ; V 0 )=V (G) E(G ; E 0 )=E(G) ; E 0 : G v es el subgrafo entorno de v en G, denido como el subgrafo de G inducido por el entorno abierto de v en G. G v = G[N G (v)]: Sean G y G 0 grafos. El grafo union de G y G 0 es el grafo G [ G 0 tal que V (G [ G 0 )=V (G) [ V (G 0 ) y E(G [ G 0 )=E(G) [ E(G 0 ). Un grafo G se dice completo si dos cualesquiera de sus vertices son adyacentes, es decir si E(G) = V (G) [2]. Un subgrafo completo es un subgrafo que es un grafo completo. Un completo de un grafo G es un subconjunto C de V (G) tal que G[C] es un subgrafo completo. El tama~no de un completo es su cardinal. Diremos que un completo contiene a una arista, si los vertices extremos de la arista pertenecen al completo. Si C es un completo, el correspondiente subgrafo completo G[C] se denotara C. Un triangulo de un grafo G es un completo de G con tres vertices. T (G) denotara el conjunto de todos los triangulo de G. Un clique de G es un completo de G, maximal respecto a la relacion de inclusion de conjuntos. Mientras el contexto sea claro y no se preste a confusion llamaremos tambien completo a un subgrafo completo, y clique aunsubgrafo cuyo conjunto de vertices es un clique. 9

15 La familia de cliques de G se notara C(G). Los elementos de esta familia son los vertices de G, decimos entonces que el vertice u esta separado (dominado) del vertice v, siu esta separado (dominado) del vertice v en C(G). Resulta entonces que u es un vertice dominado si existe otro vertice v tal que, \ v 2 C: (2.2.1) C2C(G) u2c Un conjunto independiente o conjunto estable de G es un subconjunto de vertices de G, tales que dos cualesquiera de ellos no son adyacentes entre s. El tama~no de un conjunto estable es la cantidad de vertices que posee.!(g) indica el tama~no del clique maximo de G y (G) el tama~no del conjunto independiente maximo de G. Dado k 2 N, simbolizamos mediante K k al grafo completo con k vertices. Un grafo se dice K k ; libre si ninguno de sus subgrafos es isomorfo a K k. En general un grafo se dice H ; libre si ninguno de sus subgrafos inducidos es isomorfo a H. Llamaremos K k ; libre a la clase o conjunto de todos los grafos que son K k ; libre. Un grafo G se dice bipartido si V (G) puede particionarse en dos conjuntos, V 1 y V 2, estables. El grafo se dice bipartido completo si para todo u 2 V 1 y v 2 V 2 se tiene que uv 2 E(G). K s t indica el grafo bipartido completo tal que V 1 posee s vertices y V 2 posee t vertices. Sean u y v vertices de un grafo G y k 2 N. Una cadena en G, delongitud k, entre u y v, es una secuencia de vertices de G: w 0 w 1 ::: w k, tal que w 0 = u, w k = v y para todo 1 i k, w i;1 y w i son adyacentes en G. w 0 y w k son los vertices extremos de la cadena, los demas vertices se llaman interiores. Si para todo i 6= j, w i 6= w j la cadena se dice un camino. Un grafo G se dice conexo si para todo par de vertices de G, existe un camino en G que los conecta. Una componente conexa de un grafo es un subgrafo conexo maximal. Un vertice v de G se dice de corte si el numero de componentes conexas del grafo 10

16 G ; v, es mayor al de G. Un bloque del grafo G es un subgrafo de G conexo, sin vertices de corte, y maximal respecto a esta propiedad. Dado un grafo G una representacion de G en el plano Eucldeo, es la imagen en el plano de un par de aplicaciones inyectivas: una del conjunto de vertices de G en los puntos del plano y otra del conjunto de aristas de G en el conjunto de curvas del plano, tales que, si u y v son los vertices extremos de una arista e, entonces los puntos del plano correspondientes a u y a v por la primer aplicacion son los puntos extremos de la curva correspondiente a la arista e por la segunda aplicacion. Un grafo es planar si admite una representacion en el plano Eucldeo tal que las curvas correspondientes a dos aristas distintas no se cruzan salvo, tal vez, en sus puntos extremos, una tal representacion se dice una representacion plana de G obien una inmersion de G en el plano. Un grafo plano es un grafo planar con una dada representacion plana. Es claro que si G 0 es isomorfo a un grafo planar G, entonces G 0 es planar y mas aun toda representacion plana de G es una representacion plana de G 0. Planares denota la clase de todos los grafos planares. A pesar de lo complejo que puede parecer a priori el problema de determinar si un grafodadoesplanar o no, Kuratowski dio en1930 un teorema de caracterizacion de los grafos planares que ha dado lugar al reconocimiento lineal de estos grafos [17]. Dicho teorema se basa en la idea de subdivision: Decimos que el grafo G 0 se obtiene por subdivision de la arista e = uv del grafo G, si V (G 0 ) = V (G) [fw e g, donde w e 62 V (G), y E(G 0 )=E(G) ;fuvg[fuw e w e vg. G 0 es una subdivision de G si se puede obtener apartirdeg por una secuencia nita de subdivisiones de aristas. Teorema (Kuratowski) Un grafo G es planar si y solo si no tiene como subgrafo una subsivision de K 5 ni de K 3 3, (Figura 2.1). Es claro que la planaridad es una propiedad hereditaria para subgrafos, y, por lo tanto, para subgrafos inducidos, es decir: G 2 Planares y G 0 G =) G 0 2 Planares: (2.2.2) 11

17 K K 3,3 5 Figura 2.1: 2.3 El Operador Interseccion Sea F =(F i ) i2i una familia de conjuntos, el grafo de interseccion de F, es un grafo que reeja la relacion de interseccion entre los miembros de la familia, es decir es un grafo que posee un vertice por cada miembro de la familia y dos vertices son adyacente si y solo si los correspondientes miembros tienen interseccion no vaca. El operador interseccion, que notamos L, hace corresponder a cada familia de conjuntos su grafo interseccion. Formalmente denimos el grafo interseccion L(F) de la familia F = (F i ) i2i como el grafo cuyo conjunto de vertices es I, y dos vertices distintos i y j son adyacentes si y solo si F i \ F j 6=. Diremos que el vertice i de L(F) es correspondiente al miembro F i de F y recprocamente. En la siguiente proposicion resumimos resultados basicos ya conocidos sobre el operador interseccion por los mismos se puede consultar, por ejemplo, [13]. Proposicion F 0 F6=) L(F 0 ) L(F). F 0 F=) L(F 0 ) L(F). L es suryectivo pero no inyectivo. L restrigido a la clase de las familias Helly y separadoras es inyectivo. 12

18 2.4 El Operador Clique El grafo clique de G es el grafo de interseccion de la familia de cliques de G, es decir es el grafo L(C(G)). El operador clique, que simbolizamos mediante K, hace corresponder a un grafo G su grafo clique, es decir K(G) =L(C(G)). Cabe observar que como el grafo clique es grafo de interseccion, tiene sentido hablar de la correspondencia entre los cliques de G y los vertices de K(G). Si Clase es una clase cualquiera de grafos, entonces K(Clase) denotara la clase formada por los grafos clique de los grafos pertenecientes a Clase. Diremos que la clase Clase es ja para el operador clique si K(Clase) = Clase. Un grafo G se dice un grafo clique, si existe un grafo H tal que K(H) =G en otros terminos, si G es el grafo clique de algun grafo H. K(Grafos) indica la clase de los grafos cliques, es decir la imagen mediante el operador clique de la clase de todos los grafos. Los siguientes son resultados basicos, ya conocidos, sobre el operador clique, [13]. Proposicion G 0 G 6=) K(G 0 ) K(G). G 0 G =) K(G 0 ) K(G). K no es suryectivo, ni inyectivo. K restrigido a la clase de los grafos cuya familia de cliques es Helly y separadora es inyectivo. Como hemos mencionado, el operador clique no es un operador suryectivo, es decir K(Grafos) Grafos pero K(Grafos) 6= Grafos. El ejemplo mas sencillo de grafo que no es grafo clique es el de grafo P, que llamaremos Piramide, representado en la Figura

19 Figura 2.2: Grafo P. Tiene sentido entonces hablar del problema de reconocimiento de los grafos cliques, que, en la forma clasica, se enuncia de la siguiente manera: Entrada: Un grafo G =(V (G) E(G)). Pregunta: Existe un grafo H tal que K(H) =G? Alafecha no se conoce un algoritmo eciente para la solucion de este problema [26]. La caracterizacion de los grafos clique, dada por Roberts y Spencer, que citamos en el Teorema 2.4.1, es hasta ahora la unica conocida y no ha permitido la elaboracion de un algoritmo de reconocimiento que trabaje en una cantidad de tiempo que dependa polinomialmente de la cantidad de vertices del grafo ingresado. En adelante diremos simplemente algoritmo polinomial o eciente. Una familia de completos de un grafo G es una familia de conjuntos (F i ) i2i, tal que para todo i 2 I, F i es un completo de G. Diremos que la familia de completos (F i ) i2i, cubre las aristas de G si para toda arista uv de G existe i 2 I tal que fu vg F i. Un cubrimientos por completos de un grafo G es una familia de completos de G que cubre las aristas de G. Una familia R;S de un grafo G es una familia de completos de G que cubre sus aristas y que ademas tiene la propiedad de Helly. Una familia R;S;S de un grafo G es una familia R;S que ademas es separadora. Diremos que un cubrimiento por completos, (una familia R;S, una familia R;S;S), 14

20 de un grafo G es minimal si ninguna subfamilia es un cubrimiento por completos (una familia R;S, una familia R;S;S, respectivamente) de G. Acontinuacion enunciamos el teorema debido Roberts y Spencer, que proporciona la caracterizacion de los grafos clique sobre la cual hemos hecho referencia. Teorema (Roberts-Spencer)[22] Un grafo G es un grafo clique si y solo si existe una familia R;S de G. Un grafo G es un grafo Helly, si la familia de cliques de G, C(G), tiene la propiedad de Helly. Sea Helly, la clase de todos los grafos Helly. Para cualquier grafo G, C(G) es un cubrimiento por completos de G, es claro entonces que que si C(G) tiene la propiedad Helly, entonces C(G) es una familia R;S de G, por lo tanto Helly K(Grafos). Mas aun, en [8], Escalante demuestra que Helly es una clase ja para el operador clique, Helly = K(Helly): Por otra parte, Jayme Szwarcter da en [25], una caracterizacion de los grafos Helly (ver Teorema 4.1.1) que permite el reconocimiento eciente de estos grafos. Pertenecer a la clase Helly o a la clase K(Grafos) no son propiedades hereditarias para subgrafos inducidos. Un sencillo contraejemplo es el grafo Helly que se obtiene agregando a la Piramide (Figura 2.2) un vertice universal. Es facil probar los siguientes lemas, sobre los cuales volveremos en varias oportunidades: Lema [22] Si C es un clique de G de tama~no menor o igual que 3, y F es una familia R;S de G entonces C es un miembro de F, por lo tanto, Lema Vale que si G 2 K 4 ; libre G 2 K(Grafos) () G 2 Helly: K 3 ; libre Helly = K(Helly) K(Grafos): 15

21 Lema Sea G un grafo y E 0 el conjunto de aristas de G cuyos vertices extremos conforman un clique de G, G 2 K(Grafos) $ G ; E 0 2 K(Grafos): Se deduce de este ultimo lema que el estudio de los grafos clique puede limitarse al caso de los grafos cuyos cliques contienen al menos tres vertices. Si G es un grafo, K ;1 (G) esla imagen inversa de G por el operador clique, es decir el conjunto de todos los grafos H tales que K(H) = G. Si Clase es una clase de grafos K ;1 (Clase) =fk ;1 (G) G 2 Claseg. Es claro que G 2 K(Grafos) si y solo si K ;1 (G) 6=, y por otra parte si K ;1 (G) 6= entonces K ;1 (G) contiene una cantidad innita de grafos no isomorfos entre s. El siguiente resultado permite obtener los grafos en la imagen inversa por el operador K, de un grafo clique dado, a partir de ciertas familias R;S del grafo en cuestion, las familias R;S;S. Teorema [11] Sean G y H grafos. G = K(H) si y solo si existe F, familia R;S;S de G, tal que H = L(F). 16

22 Captulo 3 K(Planares) y K ;1 (Planares) En este captulo estudiamos la imagen directa y la imagen inversa por el operador K, de la clase de los grafos planares. En el primer caso obtendremos distintas condiciones necesarias para que un grafo sea grafo clique de un grafo planar, i.e. para que el grafo pertenezca a K(Planares), y caracterizaremos totalmente los grafos K 3 ; libre y K 4 ; libre en estas condiciones. Si bien queda abierto el problema de caracterizar totalmente la clase K(Planares), la resolucion del caso de los grafos K 4 ; libre y de los grafos K 3 ; libre, nos da una idea de la complejidad del problema planteado. En el segundo caso probaremos que determinar si el grafo clique de un grafo dado es planar, puede hacerse ecientemente en otras palabras veremos que la clase de grafos K ;1 (Planares) tiene reconocimiento polinomial. 3.1 K(Planares) Si G 2 K(Planares) yv 2 V (G), existe un grafo planar H tal que G = K(H) yun clique C de H correspondiente a v. Como H es planar, C tiene a lo sumo tama~no 4, entonces en H hay a lo sumo 4 cliques que intersectan a C y son disjuntos entre si por lo tanto en G, el conjunto independiente maximo del subgrafo entorno de v, contiene a lo sumo cuatro vertices, es decir: 17

23 Lema Si G 2 K(Planares) y v 2 V (G), entonces (G v ) 4. En forma mas general este resultado se enuncia, Lema Sea G = K(H) y v 2 V (G). El tama~no de un conjunto independiente maximo en el subgrafo entorno de v en G es menor o igual al tama~no del clique de H correspondiente a v. El siguiente lema es equivalente al Lema precedente. Lema Si G 2 K(Planares) entonces G es K 1 5 ; libre. El grafo K 1 5. La recproca de esta proposicion no es en general cierta como se veenelcasog = K 3 3, (Figura 2.1). Demostraremos que este grafo no esta enk(planares) (ver Subseccion 3.1.3), sin embargo para todo vertice v de K 3 3, (G v )=3. Es bueno observar en este momento, a partir del caso K 3 3, lo complejo que puede resultar determinar que un grafo dado no esta en K(Planares): K 3 3 es un grafo clique pues es un grafo K 3 ; libre (Lema 2.4.3). Para saber si K 3 3 pertenece a la clase K(Planares), debemos investigar los grafos en su imagen inversa por el operador clique, para ver si alguno de ellos es planar. Obtener grafos en la imagen inversa por el operador K, puede hacerse, por ejemplo, mediante la tecnica referida en el Teorema En la Figura 3.1 vemos un grafo, que llamaremos H, tal que K(H) =K 3 3. Este grafo H, no es planar (se puede ver facilmente que H es una subdivision de K 5 ). Sin embargo esto no implica que K K(Planares), pues en la imagen inversa por 18

24 Figura 3.1: Grafo H. K de K 3 3 hay ademas de H una cantidad innita de grafos, no isomorfos a H, alguno de los cuales podra ser planar, aun cuando H no lo sea. Es claro que la propiedad de pertenecer a la clase de grafos K(Planares), no es una propiedad hereditaria por subgrafos, ni por subgrafos inducidos, simplemente porque, como lo hemos observado en el captulo anterior, la propiedad de pertenecer a la clase K(Grafos) no lo es. Ahora, aunque un subgrafo inducido de un grafo clique puede no ser grafo clique, en el siguiente resultado veremos que un subgrafo inducido que satisface cierta condicion es necesariamente grafo clique. Si G = K(H) yv 2 V (G), notemos C v al clique de H correspondiente al vertice v. Teorema Sea G = K(H) y G 0 G. Llamemos H 0 al subgrafo de H, H 0 S = v2v (G C 0 ) v. Si para todo v 2 V (G) ; V (G 0 ), j N G (v) T V (G 0 ) j 2, entonces G 0 = K(H 0 ). Demostracion: Basta probar que los cliques de H 0 son exactamente los cliques de H correspondientes a los vertices de G 0, es decir C(H 0 )=(C v ) v2v (G ). 0 Supongamos que C es un clique de H 0 distinto de C v para todo v 2 V (G 0 ). Es claro que existe un clique de H que contiene a C, sea v 0 el vertice de G correspondiente a ese clique resulta que v 0 2 V (G) ; V (G 0 ) y C C v0 (Figura 3.2). 19

25 C v 1 C C v 0 H G G=K(H) H K v 1v2 v 0 C v 2 v 3 C v 3 Figura 3.2: Observemos que fv 2 V (G 0 )=C v T C 6= g fv 2 V (G 0 )=C v T Cv0 6= g = fv 2 V (G 0 )=v G v 0 g. El primer conjunto tiene cardinal estrictamente mayor que uno, pues estamos suponiendo C 6= C v para todo v 2 G 0. El ultimo conjunto tiene cardinal menor o igual que dos por hipotesis. Resulta que j fv 2 V (G 0 )=C v T C 6= g j= 2, pero esto es una contradiccion, pues si C intersecta a exactamente dos cliques, C v1 y C v2, y no esta contenido en ninguno de ellos, deben existir vertices x e y, tal que x 2 C \ (C v1 ; C v2 ) y 2 C \ (C v2 ; C v1 ) pero como xy es una arista de C y por lo tanto de H 0, debe existir, por denicion de union de grafos, w 2 V (G 0 )talquexy es una arista de C w yas x e y son vertices de C w, y porlotanto C tambien intersecta C w. 2 Por otra lado aunque la clase K(Grafos) no puede ser caracterizada por subgrafos prohibidos, el teorema anterior permite encontrar ciertas estructuras prohibidas dentro de un grafo pertenciente a la clase K(Grafos) y en particular dentro de un grafo perteneciente a la clase K(Planares): si un grafo G tiene un subgrafo G

26 K(Grafos) en las condiciones del enunciado, entonces G 62 K(Grafos). Ademas, como la planaridad es una propiedad hereditaria, resulta que si un grafo G tiene un subgrafo G 0 62 K(Planares) en las condiciones del teorema anterior, entonces G 62 K(Planares). Por ejemplo, cualquier grafo que se obtiene a partir de un grafo que no es grafo clique, por el agregado sucesivo devertices de grado dos, no es grafo clique. Observar el caso ilustrado en la siguiente gura a partir de la Piramide. Grafos que no son grafos clique. Corolario Sea G = K(H) y G 0 un bloque de G, entonces G 0 = K(H 0 ) donde H 0 = S v2v (G 0 ) C v. Lema Si G 2 K(Planares) entonces cada bloque de G pertenece a K(Planares). Demostracion: Es inmediata a partir del Corolario y del hecho de que la planaridad es una propiedad hereditaria. 2 La recproca de este resultado no es, en general, cierta. Por ejemplo, vimos en el Lema que K 1 5 no esta en K(Planares), sin embargo cada bloque de K 1 5 lo 21

27 esta. Ocurre en este ejemplo que el vertice de corte de K 1 5, no satisface la condicion del Lema 3.1.1, pero s lo hace en cada uno de los bloques, esto se ve mas generalmente en el siguiente resultado. Lema Sea v un vertice decorte de un grafo G y G 1 G 2 ::: G k los bloques de G a los que pertenece v. Entonces (G v )= P 1ik (G iv). Demostracion: Es inmediata. Destaquemos simplemente que G iv es el subgrafo entorno de v en G i. 2 Lema Si G 2 K(Planares), v es un vertice de corte de G y G 1 G 2 ::: G k son los bloques de G a los que pertenece v, entonces P 1ik (G iv) 4. Demostracion: Es inmediata a partir del Lema y del Lema Corolario Si G 2 K(Planares), entonces todo vertice de corte de G esta en a lo sumo 4 bloques de G K(Planares) \ K 4 ; libre Buscamos caracterizar K(Planares) \ K 4 ; libre. Los resultados obtenidos se desarrollaron a partir de las siguientes ideas basicas: de acuerdo al Teorema 2.4.5, G 2 K(Planares) si y solo si existe una familia R;S;S de G tal que el grafo interseccion de esta familia sea planar. Pensemos entonces en las familias R;S;S de un grafo K 4 ; libre. Por el Lema 2.4.2, si G es K 4 ; libre y admite una familia R;S entonces C(G) es subfamilia de cualquier familia R;Sde G, es decir G tiene una unica familia R;S minimal: la familia de sus cliques. Las demas familias R;S se obtienen agregando a la familia de los cliques miembros repetidos o bien miembros contenidos en otros miembros. Algo similar ocurre respecto a la separacion de la familia: si C(G) no es separadora, 22

28 sera necesario agregar miembros para que as sea. Es claro que al agregar miembros, el grafo interseccion de la familia se torna mas complejo, con lo cual es de esperar que si en la imagen inversa por el operador clique hay algun grafo planar, este grafo planar sea el grafo interseccion de la familia R;S;S de G formada por la familia de cliques de G con la menor cantidad posible de miembros agregados es natural pensar que tal familia R;S;S es la familia formada por los cliques de G y un miembro fug, por cada vertice u 2 V (G) dominado en G. Usaremos el siguiente lema en la demostracion del teorema de caracterizacion. Lema Sea G un grafo y (G i ) i2i una familia nita de subgrafos conexos de G. El grafo L(F), interseccion de la familia F =(V (G i )) i2i, es conexo si y solo si S i2i G i es conexo. Demostracion: Para probar que S i2i G i es conexo, consideremos u y v vertices de este grafo. Existen G iu, G iv tales que u 2 V (G iu ) y v 2 V (G iv ). Sean i u e i v los correspondientes vertices de L(F). Como L(F) es conexo existe un camino i 0 i 1 ::: i k tal que i 0 = i u e i k = i v. Como para todo j, 1 j k, i j;1 es adyacente a i j en L(F), resulta que los correspondientes conjuntos V (G j;1) yv (G j )def tienen interseccion no vaca, podemos entonces considerar vertices w j,1 j k, en estas intersecciones. Llamemos ademas w 0 = u y w k+1 = v. As tenemos que para todo j, 1 j k +1, w j;1 y w j pertenecen a V (G j ), como los subgrafos G j son todos conexos, resulta que para todo 1 j k + 1 existe en S i2i G i un camino entre w j;1 y w j y por ende una cadena entre w 0 = u y w k+1 = v. Para probar la implicacion recproca sean i 0 e i 0 0 vertices de L(F) sean V (G i 0 ) y V (G i 0 0 ) los correspondientes miembros de la familia F. Sean u y v vertices de S i2i G i tal que u 2 V (G i0 ) y v 2 V (G i 0 0 ). Como por hipotesis S i2i G i es conexo existe un camino v 1 v 2 :::v k tal que v 1 = u y v k = v. Como para todo j, 1 j k ; 1, la arista e j = v j v j+1 es una arista de S i2i G i, existe un subgrafo G ij, i j 2 I, tal que e j 2 E(G ij ), (sin perdida de generalidad se puede suponer i 1 = i 0 e i k;1 = i 0 0 ), y por lo tanto v j y v j+1 pertenecen a V (G ij ), de donde V (G ij ) y V (G ij+1 ) tienen 23

29 interseccion no vaca. Es claro entonces que los vertices de L(F), i j correspondiente a los miembros V (G ij ) conforman una cadena en L(F), as tenemos una cadena entre i 1 = i 0 e i k;1 = i Los grafos pertenecientes a la clase K(Planares)\K 4 ; libre son caracterizados por el siguiente teorema. Teorema Sea G grafo clique K 4 ; libre. G 2 K(Planares) si y solo si 1. K(G) es un grafo planar. 2. Toda arista de G esta en a lo sumo 3 cliques de G, y 3. Si una arista uv de G esta en 3 cliques de G: fu v ag, fu v bg y fu v cg, entonces los vertices a, b y c no estan en una misma componente conexa de G ; T, donde T es el conjunto de aristas de los cliques de G que contienen a u o a v. Demostracion: Sea G 2 K(Planares) \ K 4 ; libre. Como G 2 K(Planares), existe un grafo planar H tal que G = K(H). De acuerdo con el Teorema 2.4.5, existe F, una familia R;S ; S de G satisfaciendo L(F) =H. Como G es K 4 ; libre, por el Lema 2.4.2, C(G) es una subfamilia de F, entonces L(C(G)) = K(G) es un subgrafo inducido de L(F) = H (Proposicion 2.3.1). Con esto probamos que K(G) esplanar. Supongamos que una arista uv de G esta en cuatro cliques diferentes. Como F es una familia separadora debe existir un miembro F u tal que u 2 F u y v 62 F u (Equivalencias 2.1.2), claramente F u no es ninguno de los cuatro cliques mencionados. Como F u y los cuatro cliques son miembros de F y todos ellos son mutuamente intersectantes pues contienen a u, su interseccion genera un K 5 en L(F) = H. Esto contradice la planaridad de H. Hemos probado que toda arista de G esta en alosumo3 cliques. Probaremos la condicion 3 por contradiccion. Si 3 no es cierta, existe una arista uv de G en tres cliques: A = fu v ag, B = fu v bg y C = fu v cg y se satisface que 24

30 B A w HZ HHHH ZZ Z H ZZHHHH w wc XXXXXXXXXXXXXXXXXXXXXX F u Z H w wf v Figura 3.3: Subgrafo S de H = L(F). los vertices a, b y c estan en una misma componente conexa X, de G ; T, donde T es el conjunto de las aristas de los cliques de G que contienen u o v. Observemos que, por la propia denicion de T, Si e 2 E(G ; T )y e 2 E(C 0 ) C 0 clique de G =) u 62 C 0 y v 62 C 0 : (3.1.1) Ahora, vimos que por ser F una familia separadora debe contener un miembro F u tal que u 2 F u y v 62 F u por la misma razon debe existir otro miembro F v tal que v 2 F v y u 62 F v. La interseccion de los cinco miembros de F: A, B, C, F u y F v genera en L(F) el subgrafo S de la Figura 3.3. F u y F v no pueden ser adyacentes en H por planaridad. Observar que llamamos en la misma forma a los miembros de F y a los correspondientes vertices de L(F). El subgrafo S es planar, pero demostraremos -a partir de el- que existe un subgrafo de L(F),i.e. de H, el cual no es planar pues contiene una subdivision de K 3 3. Mas precisamente, mostraremos un subgrafo S 0 de L(F), conexo y disjunto de S el cual tiene vertices adyacentes a A, B y C, con lo cual habra una subdivision de K 3 3. Sea C X = (C i ) i2i la familia formada por todos aquellos cliques de G que contienen alguna arista de X. Claramente C X es una subfamilia de C(G) y por lo tanto de F, entonces S 0 = L(C X ) es un subgrafo inducido de L(F) (Proposicion 2.3.1). Si C i es un miembro de C X, por denicion de C X y la implicacion 3.1.1, C i no contiene 25

31 a u ni a v, por lo tanto C i no es A, nib, nic, y tampoco es F u o F v. Se deduce que S 0 y S son subgrafos disjuntos, no tienen ningun vertice en comun. Por otra parte, como cada subgrafo C S i y i2i C i son conexos, por lo demostrado en el Lema , el subgrafo S 0 = L(C X ) es conexo. Hemos demostrado que S 0 es un subgrafo conexo de L(F) disjunto de S. Ahora, como a, b y c son vertices de la componente conexa X, existen aristas de X incidentes en esos vertices, por lo tanto hay un miembro de C X conteniendo a a, un miembro conteniendo a b y un miembro conteniendo a c pueden ser un mismo miembro o no. Claramente los vertices de S 0 correspondientes a estos miembros son adyacentes en L(F) aa, ab, yac respectivamente, tal como queramos demostrar. Para demostrar la recproca, consideremos un grafo clique G, K 4 ;libre. Por el Lema 2.4.2, G es un grafo Helly, por lo tanto C(G) es una familia R;S de G. Llamemos Dom(G) = fu 1 u 2 ::: u s g al conjunto de los vertices dominados de G. En lo que sigue suponemos que Dom(G), es no vaco, en caso que lo fuese la demostracion puede seguirse en forma analoga. Claramente la familia F S = C(G) (fu i g) 1is tiene la propiedad de Helly pues C(G) la tiene y es separadora pues no tiene elementos dominados, por lo tanto es una familia R;S ; S de G. Concluimos por el Teorema que H = L(F) es tal que G = K(H). Probaremos que si se satisfacen las condiciones 1, 2 y 3, H es un grafo planar y por lo tanto G 2 K(Planares). Mas precisamente, probaremos inductivamente que para todo j, 0 j s, el grafo H j = L(F j )esplanar, donde F 0 = C(G) F j = C(G) [ (fu i g) 1ij cuando j > 0 La proposicion es verdadera cuando j =0,porque H 0 = L(F 0 )=L(C(G)) = K(G) que es planar por la hipotesis 1. Suponiendo que para un dado j = ` ; 1 0, H`;1 es planar, probaremos que H` tambien lo es. Es claro que H` es el grafo planar H`;1 con el agregado de un nuevo vertice fu`g, y las aristas que lo hacen adyacente a 26

32 aquellos vertices de H`;1 correspondientes a los cliques de G que contienen al vertice u`. Veamos que tales cliques son a lo sumo tres. Como u` es un vertice dominado de G debe existir en G un vertice v que lo domina. Como v domina a u`, v pertenece a todo clique que contiene a u` (Equivalencia 2.2.1) se deduce que la arista vu` esta en todo clique que contiene a u`, entonces, por la hipotesis 2, u` no puede estar mas que en tres cliques de G. Consideraremos por separado el caso en que u` esta enuno o en dos cliques de G y el caso en que u` esta en exactamente tres cliques. Caso a: u` esta en uno (dos) cliques de G. Para obtener H` debemos agregar a H`;1 el vertice fu`g y hacer este vertice adyacente a un unico vertice (dos vertices que son extremos de una arista) de H`;1, entonces es claro que H` es planar si H`;1 lo es. Caso b: u` esta en tres cliques de G. Estos cliques deben ser K 3,puesG es K 4 ;libre. Sean estos cliques A = fu` v ag, B = fu` v bg y C = fu` v cg. Si H`;1 admite una representacion plana tal que el triangulo con vertices A, B y C es la frontera de una cara, para obtener una representacion de H`, podemos agregar a H`;1 el vertice fu`g en el centro de esta cara y hacerlo adyacente a A, B y C sin perder la planaridad, y la demostracion del teorema esta terminada. Veamos que, en las condiciones del teorema, una tal representacion siempre existe, pues de no ser as, se contradice la hipotesis 3 en otras palabras demostraremos que si no existe una representacion de H`;1 como la dicha, los vertices a, b y c de G estan en un subgrafo conexo de G ; T, donde T es el conjunto de todas las aristas de los cliques de G que contienen a u` o a v. Si H`;1 no admite una representacion plana con el triangulo de vertices A, B, C como frontera de una cara, es porque en H`;1 hay subgrafos conexos, S y S 0, disjuntos, que no contienen ninguno de los vertices A, B o C, pero que contienen vertices adyacentes a A, B y C, como se muestra en la Figura 3.4. Veamos que uno de los dos subgrafos, S o S 0 es tal que cada uno de sus vertices corresponde a un miembro de F`;1 que no contiene a u` ni a v esto se deduce facilmente de los siguientes hechos: 27

33 v QP B QQQ PPPPPPPPPPPPPPPPP v '$ Q ``````````````````````` QQQ &% S C v A '$ &% S' Figura 3.4: H`;1 = L(F`;1). i) Los vertices de S y de S 0 corresponden todos a miembros de F`;1 distintos de los cliques A, B o C (Ver Figura 3.4). ii) Estamos suponiendo en el caso b) que los unicos miembros de F`;1 a los que pertenece u` son A, B and C. iii) v es un elemento de la familia F`;1 que esta en los miembros A, B,C y tal vez en mas pero, como por hipotesis inductiva, L(F`;1) es planar, todo elemento de la familia esta en a lo sumo cuatro miembros, de donde v esta en a lo sumo un miembro mas, este miembro podra corresponder aunvertice de S odes 0,peronodelosdos. Podemos entonces asumir sin perdida de generalidad que: los vertices de S 0 corresponden a miembros que no contienen a u` ni a v (3.1.2) Llamemos F 0 a la subfamilia de F`;1 tal que L(F 0 ) = S 0. Como cada miembro de la subfamilia F 0 es el conjunto de vertices de un subgrafo conexo de G, y como S 0 = L(F 0 ) es conexo, por el Lema , es conexo el subgrafo, que llamaremos X, union de los subgrafos de G cuyos conjuntos de vertices son los miembros de F`;1 correspondientes a los vertices de S 0. Veamos que a, b y c son vertices de X. En S 0 hay unvertice adyacente a A = fu` v ag por la armacion ese vertice debe corresponder a un miembro de F 0 que contiene 28

34 a a, porlotanto a 2 V (X). De la misma manera lo probamos para b y c. Finalmente probaremos que X es un subgrafo de G ; T. Sea e una arista de X, debemos ver que e no esta en ningun clique que contiene a u` ni a v. Por denicion de X, e es la arista de un clique de G tal que corresponde a un vertice de S 0. Por la armacion los vertices extremos de e no son u` ni v, entonces e no esta en un clique que contenga u`, pues estos cliques son unicamente A, B y C. Por la misma razon, si e esta en un clique que contiene a v, este clique debe corresponder a un vertice de S, pero entonces resulta que hay un vertice de S 0 adyacente a un vertice de S, lo cual contradice la planaridad de H`;1. 2 En la demostracion anterior no solo hemos probado que existe un grafo planar en la imagen inversa sino que lo hemos construido, probamos entonces el siguiente corolario. Corolario Sea G un grafo clique K 4 ; libre, Dom el conjunto de vertices dominados de G y F la familia C(G) S (fug) u2dom. G 2 K(Planares) si y solo si L(F) es planar. Complejidad Algortmica Cada una de las condiciones jadas en el Teorema de esta seccion, es testeable en tiempo polinomial para un grafo K 4 ;libre, por lo tanto K(Planares)\K 4 ; libre es una clase de grafos con reconocimiento polinomial K(Planares) \ K 3 ; libre Buscamos caracterizar K(Planares) \ K 3 ; libre. El grafo lnea de un grafo dado G se dene como el grafo interseccion de la familia de conjuntos E G =(e) e2e(g), cuyos miembros son las aristas del grafo. El grafo lnea de G se denota Lin(G). De acuerdo a las deniciones dadas en el Captulo 2 resulta que Lin(G) =L(E G ). El siguiente Teorema debido a Sedlacek caracteriza a los grafos tales que su grafo lnea es un grafo planar. 29

35 Teorema [23, Sedlacek] Sea G un grafo. Lin(G) es planar si y solo si 1. G 2 Planares, 2. Todo vertice de G tiene grado a lo sumo 4, y 3. Si un vertice de G tiene grado 4, entonces es un vertice de corte. Si G es un grafo K 3 ; libre, sinvertices aislados, todo clique de G es un K 2, es decir hay una correspondencia biunvoca entre las aristas y los cliques de G, de donde C(G) =E G y por lo tanto G es K 3 ; libre =) K(G) =Lin(G): Es claro entonces que el Teorema de Sedlacek nos permite deducir cuando un grafo K 3 ; libre esta en K ;1 (Planares), pero no nos sirve para ver cuando un grafo K 3 ; libre esta enk(planares), pues aunque el grafo en cuestion sea K 3 ; libre, los grafos en la imagen inversa por el operador K pueden no ser K 3 ; libre. Sin embargo a traves del Teorema podemos reducir un problema en el otro: todo grafo K 3 ;libre satisface inmediatamente el hecho de ser grafo clique, y satisface la segunda y la tercer hipotesis del Teorema , se deduce que un grafo K 3 ; libre pertenece a K(Planares) si y solo si K(G) 2 Planares, i.e. si y solo si G pertenece a K ;1 (Planares) por lo tanto hemos probado el siguiente teorema. Teorema Sea G un grafo K 3 ; libre. Son equivalentes: 1. G 2 K(Planares). 2. G 2 K ;1 (Planares). 3. (a) G 2 Planares, (b) Todo vertice de G tiene grado a lo sumo 4, y (c) Si un vertice de G tiene grado 4, entonces es un vertice de corte. 30

36 El siguiente corolario nos dice que un grafo K 3 ; libre que no es planar, no "viene" por el operador clique de un grafo planar y no "va" por el operador clique a un grafo planar. Corolario Si G es K 3 ;libre y G 62 Planares, entonces G 62 K(Planares) y K(G) 62 Planares. Complejidad Algortmica Cada una de las condiciones jadas en el el punto 3 del Teorema de esta seccion, son testeables en tiempo polinomial para un grafo K 3 ; libre, por lo tanto K(Planares) \ K 3 ; libre y K ;1 (Planares) \ K 3 ; libre son clases de grafos con reconocimiento polinomial Ejemplos Probaremos facilmente a partir de los resultados anteriores que ninguno de los grafos de la Figura 3.5 esta en K(Planares), es decir en la imagen inversa por el operador K de estos grafos, no hay ningun grafo planar. G 1 es K 3 ; libre y tiene un vertices de grado 4 que no es de corte, por lo tanto G 1 62 K(Planares). G 2 es K 4 ; libre y K(G 2 ) no es planar, concluimos que G 2 62 K(Planares). K(G 3 ) es planar pero G 3 G 3 62 K(Planares). tiene una arista que pertenece a cuatro cliques, entonces K(G 4 ) es planar, toda arista de G 4 esta en a lo sumo tres cliques pero hay una arista que esta en exactamente tres cliques y los vertices a, b and c no satisfacen la tercer hipotesis del Teorema , por lo tanto concluimos que G 4 62 K(Planares). 31