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.No (Si se contrae uniendo los 2 nodos de arriba a la izquierda le queda un subrafo isomorfo a K3,3). | <br>3.No (Si se contrae uniendo los 2 nodos de arriba a la izquierda le queda un subrafo isomorfo a K3,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. | ||
<br> | <br> Por induccion. Sea T un arbol de k+1 nodos.Sea T'=T-v. Por HI T' es planar. | ||
Al agregar a v a T', en ningun momento hace falta re dibujar el grafo por lo tanto T es planar. (le hace falta chamuyo a la dem,casos base, pero para dar otra idea) | |||
==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 55: | ||
<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 256: | Línea 214: | ||
<br> Otra forma: | <br> Otra forma: | ||
Ir borrando | Ir borrando ejes, hasta que el subgrafo que queda al sacar cualquier eje queda critico. | ||
==Ejercicio 09.19:== | ==Ejercicio 09.19:== | ||
Línea 266: | Línea 224: | ||
==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 234: | ||
<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: |