Edición de «Práctica 9: Planaridad - Coloreo (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 1: | Línea 1: | ||
==Propiedades== | |||
=Propiedades= | |||
(Para todo G: grafo) | (Para todo G: grafo) | ||
* (DEF) G es '''planar''' <=> se puede dibujar en un plano sin que sus ejes se crucen | * (DEF) G es '''planar''' <=> se puede dibujar en un plano sin que sus ejes se crucen | ||
* (TEO) G es planar <=> no contiene un subgrafo homeomorfo a K5 o | * (TEO) G es planar <=> no contiene un subgrafo homeomorfo a K5 o K33 | ||
* (TEO) G es planar y conexo -> n-m+r = 2 | * (TEO) G es planar y conexo -> n-m+r = 2 | ||
* (COR) G es planar y conexo -> 3*r >= 2*m y m <= 3*n-6 | * (COR) G es planar y conexo -> 3*r >= 2*m y m <= 3*n-6 | ||
Línea 32: | Línea 30: | ||
* (TEO) X'(G) = max d(v) o X'(G) = max d(v)+1 | * (TEO) X'(G) = max d(v) o X'(G) = max d(v)+1 | ||
= Planaridad | <table bgcolor="blue"><tr><td><font color="white"> Planaridad </font></td></tr></table> | ||
==Ejercicio 09.01:== | ==Ejercicio 09.01:== | ||
<br>1.No (Es contraible a K5 por los ejes que tocan la "estrella" por afuera) | <br>1.No (Es contraible a K5 por los ejes que tocan la "estrella" por afuera) | ||
<br>2.No (Es contraible a K5 por el eje que toca el | <br>2.No (Es contraible a K5 por el eje que toca el triangulo por arriba) | ||
<br>3 | <br>3. | ||
<br>4 | <br>4. | ||
<br>5.No (Contiene un subgrafo contraible a K3,3) | <br>5.No (Contiene un subgrafo contraible a K3,3) | ||
==Ejercicio 09.02:== | ==Ejercicio 09.02:== | ||
<font color="red"> (Esta mal esto) | |||
<br> Sup. que no. Sea T arbol. Como T no es planar <math> \Rightarrow </math> m > 3n-6 | |||
<br> Como T es arbol <math> \Rightarrow </math> m = n-1 | |||
<br> Entonces n-1 <math> > </math> 3n-6 <=> 5 > 2n <=> n < 5/2 <math> \Rightarrow </math> n <math> \le </math> 2. | |||
<br> Pero entonces los unicos arboles posibles (K1 y K2) son planares <math> \Rightarrow </math> ABS | |||
</font> | |||
<br> A ver esta: | |||
<br> Sea T arbol. T es planar <=> no contiene un subgrafo homeomorfo a K5 o K33. Como no son isomorfos (todo arbol tiene hojas -> hay vertices de grado 1, pero K5 y K33 no tienen) -> y no se pueden obtener de otro grafo mediante subdiv. elementales (ya que cualquier subdiv. de K5 o K33 tiene ciclos -> no se puede llegar a un arbol) entonces vale. | <br> Sea T arbol. T es planar <=> no contiene un subgrafo homeomorfo a K5 o K33. Como no son isomorfos (todo arbol tiene hojas -> hay vertices de grado 1, pero K5 y K33 no tienen) -> y no se pueden obtener de otro grafo mediante subdiv. elementales (ya que cualquier subdiv. de K5 o K33 tiene ciclos -> no se puede llegar a un arbol) entonces vale. | ||
==Ejercicio 09.03:== | ==Ejercicio 09.03:== | ||
<br>G planar y para todo v, d(v) >= 3 -> 2 = n-m+r y 3*n <= 2*m = Σd(v) -> n <= 2/3*m | <br>G planar y para todo v, d(v) >= 3 -> 2 = n-m+r y 3*n <= 2*m = Σd(v) -> n <= 2/3*m | ||
<br>-> 2 = n-m+r <= 2/3*m-m+r <=> 6 <= 2*m-3*m+3*r = 3*r-m <=> m <= 3*r-6 | <br>-> 2 = n-m+r <= 2/3*m-m+r <=> 6 <= 2*m-3*m+3*r = 3*r-m <=> m <= 3*r-6 | ||
Línea 93: | Línea 59: | ||
<br>b) Sup. que no. Entonces para todo v, d(v) >= 5 -> Σ d(v) = 2*m >= 5*n | <br>b) Sup. que no. Entonces para todo v, d(v) >= 5 -> Σ d(v) = 2*m >= 5*n | ||
<br> G es planar -> m <= 3*n-6 | <br> G es planar -> m <= 3*n-6 -> 2*(3*n-6) >= 2*m >= 5*n -> 6*n-12 >= 5*n -> n >= 12 -> ABS | ||
<br>c) Sup. G y Gc son planares | <br>c) Sup. G y Gc son planares | ||
Línea 103: | Línea 65: | ||
<br> -> n(n-1)/2 - (3*n-6) <= m(Gc) <= (3*n-6) | <br> -> n(n-1)/2 - (3*n-6) <= m(Gc) <= (3*n-6) | ||
<br> Con lo cual hay que ver para que valores se cumple n(n-1)/2 - (3*n-6) <= (3*n-6). Esto pasa si n<sup>2</sup>-13*n+24 <= 0 <=> (n-10,77)(n-2,22) <= 0 -> n <= 10 y n >= 3. Pero por HI n >= 11 -> ABS | <br> Con lo cual hay que ver para que valores se cumple n(n-1)/2 - (3*n-6) <= (3*n-6). Esto pasa si n<sup>2</sup>-13*n+24 <= 0 <=> (n-10,77)(n-2,22) <= 0 -> n <= 10 y n >= 3. Pero por HI n >= 11 -> ABS | ||
==Ejercicio 09.05:== | ==Ejercicio 09.05:== | ||
Línea 111: | Línea 71: | ||
==Ejercicio 09.06:== | ==Ejercicio 09.06:== | ||
<br>He aqui el dibujo de la parrilla: | |||
<br>http://serv2.imagehigh.com/imgss/4482747_parrilla.JPG | |||
<br>Nota: p = puntos, l = cuerdas | |||
<br> G es planar -> r = m-n+2. Queremos averiguar m-n+1 (o sea, sin la region que cubre todo) | <br> G es planar -> r = m-n+2. Queremos averiguar m-n+1 (o sea, sin la region que cubre todo) | ||
<br> n = p + 2*l | <br> n = p + 2*l | ||
Línea 119: | Línea 82: | ||
==Ejercicio 09.07:== | ==Ejercicio 09.07:== | ||
==Ejercicio 09.08:== | ==Ejercicio 09.08:== | ||
<i>(Preguntar)</i> | |||
<br>a) | <br>a)Σ{i=1..k} (ni - mi + ri) = n - m + (r-k+1) = 2k <=> n-m+r=3k-1 | ||
<br>b)m <= 3*n-6*k | |||
<br>b) | |||
==Ejercicio 09.09:== | ==Ejercicio 09.09:== | ||
Línea 188: | Línea 129: | ||
</pre> | </pre> | ||
= Coloreo | <table bgcolor="blue"><tr><td><font color="white"> Coloreo </font></td></tr></table> | ||
==Ejercicio 09.11:== | ==Ejercicio 09.11:== | ||
Notas: | Notas: | ||
Línea 245: | Línea 187: | ||
<br>d) | <br>d) | ||
==Ejercicio 09.18:== | ==Ejercicio 09.18:== | ||
Línea 254: | Línea 193: | ||
* PI: | * PI: | ||
Sea G' = G-v (G sin el vertice v). Agregamos el vertice. Si X(G') < X(G), G era k-critico y listo. Si no, X(G') = X(G), con lo cual, si G' tenia un subgrafo k-critico, G tambien lo tiene -> OK | Sea G' = G-v (G sin el vertice v). Agregamos el vertice. Si X(G') < X(G), G era k-critico y listo. Si no, X(G') = X(G), con lo cual, si G' tenia un subgrafo k-critico, G tambien lo tiene -> OK | ||
==Ejercicio 09.19:== | ==Ejercicio 09.19:== | ||
Línea 266: | Línea 202: | ||
==Ejercicio 09.20:== | ==Ejercicio 09.20:== | ||
El grafo de Grotzsch | <br>El grafo de Grotzsch (Jaja no es fruta, miren:) | ||
<br>http://serv2.imagehigh.com/imgss/4459632_g_grotzsch.gif | |||
==Ejercicio 09.21:== | ==Ejercicio 09.21:== | ||
Línea 276: | Línea 213: | ||
<br>X(G)+X(Gc) = X(G')+X(Gc')+k (k cte.). Separamos en casos: | <br>X(G)+X(Gc) = X(G')+X(Gc')+k (k cte.). Separamos en casos: | ||
<br>1. X(G) = X(G') o X(Gc) = X(Gc') -> k <= 1 -> X(G)+X(Gc) <= X(G')+X(Gc')+1 <= (HI) n+1 OK | <br>1. X(G) = X(G') o X(Gc) = X(Gc') -> k <= 1 -> X(G)+X(Gc) <= X(G')+X(Gc')+1 <= (HI) n+1 OK | ||
<br>2. dG(v) >= X(G') y dGc(v) >= X(Gc') -> | <br>2. dG(v) >= X(G') y dGc(v) >= X(Gc') -> X(G)+X(Gc) = X(G')+X(Gc')+2 <= dG(v)+dGc(v)+2 = | ||
X(G | <br>(como dGc(v)=n-dG(v)-1) dG(v)+(n-dG(v)-1)+2 = n+1 OK | ||
<br>b) Probamos ambas desigualdades: | <br>b) Probamos ambas desigualdades: | ||
Línea 293: | Línea 228: | ||
==Ejercicio 09.22:== | ==Ejercicio 09.22:== | ||
Creo que sale con Teorema de Brooks | |||
==Ejercicio 09.23:== | ==Ejercicio 09.23:== | ||
<br>a) | <br>a) | ||
<br>b) Sup. que G es 2-coloreable -> G es bipartito -> el caso con mas ejes seria el del bipartito completo, entonces tomando V1 como una de las particiones, la cant. de ejes seria |V1|(8-|V1|) = 13 | <br>b) Sup. que G es 2-coloreable -> G es bipartito -> el caso con mas ejes seria el del bipartito completo, entonces tomando V1 como una de las particiones, la cant. de ejes seria |V1|(8-|V1|) = 13 | ||
-> -1|V1|^2 + 8|V1| - 13 = 0. Pero no hay un numero entero que cumpla esto -> ABS | -> -1|V1|^2 + 8|V1| - 13 = 0. Pero no hay un numero entero que cumpla esto -> ABS | ||
<br>c) | <br>c) | ||
==Ejercicio 09.24:== | ==Ejercicio 09.24:== | ||
==Ejercicio 09.25:== | ==Ejercicio 09.25:== | ||
<br>a) | <br>a) | ||
Línea 324: | Línea 242: | ||
<br>2. k(k-1)^2 | <br>2. k(k-1)^2 | ||
<br>3. k(k-1)(k-2) | <br>3. k(k-1)(k-2) | ||
<br>4. k(k-1)^2(k-2) + k(k-1)^2 = (k-1)^ | <br>4. k(k-1)^2(k-2) + k(k-1)^2(k-1) = k(k-1)^2)(k-2 + k-1) = k(k-1)^2)(2k-3) | ||
<br>5. k(k-1)(k-2)(k-3) | <br>5. k(k-1)(k-2)(k-3) | ||
<br>6. k(k-1)(k-2)(k-1)^2 | <br>6. k(k-1)(k-2)(k-1)^2 | ||
<br>7. k(k-1)(k-2)...(k-(n-1)) | <br>7. k(k-1)(k-2)...(k-(n-1)) | ||
<br>b) | <br>b) Creo que es igual a la cant. de raices del polinomio cromatico | ||
==Ejercicio 09.26:== | ==Ejercicio 09.26:== | ||
Línea 370: | Línea 280: | ||
<br>b) | <br>b) | ||
==Ejercicio 09.34:== | ==Ejercicio 09.34:== | ||
==Ejercicio 09.35:== | ==Ejercicio 09.35:== | ||