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 35: | Línea 35: | ||
==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:== | ||
<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 52: | ||
<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 58: | ||
<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 121: | Línea 74: | ||
m <= 3*n-6 = 3*(n-2) <= k(n-2) (la minima longitud de un circuito es 3) | m <= 3*n-6 = 3*(n-2) <= k(n-2) (la minima longitud de un circuito es 3) | ||
(Ahora lo seguimos) | (Ahora lo seguimos) | ||
==Ejercicio 09.08:== | ==Ejercicio 09.08:== | ||
Línea 142: | Línea 84: | ||
El problema con esto es que está aplicando la fórmula a componentes conexas que podrían no cumplir la hipótesis de la desigualdad (que pide n >= 3). Por esa razón hay que tener cuidado con la justificación dada. | El problema con esto es que está aplicando la fórmula a componentes conexas que podrían no cumplir la hipótesis de la desigualdad (que pide n >= 3). Por esa razón hay que tener cuidado con la justificación dada. | ||
==Ejercicio 09.09:== | ==Ejercicio 09.09:== | ||
Línea 245: | Línea 184: | ||
<br>d) | <br>d) | ||
==Ejercicio 09.18:== | ==Ejercicio 09.18:== | ||
Línea 254: | Línea 190: | ||
* 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 199: | ||
==Ejercicio 09.20:== | ==Ejercicio 09.20:== | ||
El grafo de Grotzsch. | El grafo de Grotzsch. | ||
==Ejercicio 09.21:== | ==Ejercicio 09.21:== | ||
Línea 276: | Línea 209: | ||
<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 224: | ||
==Ejercicio 09.22:== | ==Ejercicio 09.22:== | ||
Creo que sale con Teorema de Brooks | |||
==Ejercicio 09.23:== | ==Ejercicio 09.23:== | ||
Línea 324: | Línea 247: | ||
<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:== |