Edición de «Práctica 9: Planaridad (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: | ||
{{Back|Algoritmos y Estructuras de Datos III}} | {{Back|Algoritmos y Estructuras de Datos III}} | ||
=Propiedades= | |||
(Para todo G: grafo) | (Para todo G: grafo) | ||
Línea 9: | Línea 9: | ||
* (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 | ||
=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 triángulo por arriba) | <br>2.No (Es contraible a K5 por el eje que toca el triángulo por arriba) | ||
Línea 16: | Línea 16: | ||
<br>5.No (Contiene un subgrafo contraible a K3,3) | <br>5.No (Contiene un subgrafo contraible a K3,3) | ||
=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> | ||
Línea 36: | Línea 36: | ||
<br>Entonces T es planar, como queríamos probar. | <br>Entonces T es planar, como queríamos probar. | ||
=Ejercicio 09.03:= | |||
<br>a) | <br>a) | ||
<br>Sea G un grafo planar con k componentes conexas, n vértices y m aristas. | <br>Sea G un grafo planar con k componentes conexas, n vértices y m aristas. | ||
Línea 56: | Línea 56: | ||
<br>Entonces m <= 3 * n - 6, como quería probar. | <br>Entonces m <= 3 * n - 6, como quería probar. | ||
=Ejercicio 09.04:= | |||
<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 | ||
=Ejercicio 09.05:= | |||
<br>a) Sup. que no. Entonces para todo v, d(v) >= 6. Como G es planar -> m <= 3*n-6. | <br>a) Sup. que no. Entonces para todo v, d(v) >= 6. Como G es planar -> m <= 3*n-6. | ||
<br>6*n <= Σ d(v) = 2*m -> 6*n <= 2*m -> m >= 3*n ABS (m <= 3*n-6) | <br>6*n <= Σ d(v) = 2*m -> 6*n <= 2*m -> m >= 3*n ABS (m <= 3*n-6) | ||
Línea 76: | Línea 76: | ||
<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 | ||
Ojo que en estos 3 ejercicios se uso m <= 3n-6, esto se dió en la teórica solo para grafos planares conexos. Igualmente esta fórmula también vale para los no conexos, por el resultado del ej 9. | Ojo que en estos 3 ejercicios se uso m <= 3n-6, esto se dió en la teórica solo para grafos planares conexos. Igualmente esta fórmula también vale para los no conexos, por el resultado del ej 9.8.b | ||
=Ejercicio 09.06:= | |||
Sea G = K5. | Sea G = K5. | ||
Si a G le agrego un nodo, (con o sin aristas) este grafo será no planar y no será homeomorfo a K3,3 ni a K5. | Si a G le agrego un nodo, (con o sin aristas) este grafo será no planar y no será homeomorfo a K3,3 ni a K5. | ||
=Ejercicio 09.07:= | |||
Como Σ d(Ri) = 2*m, y además tenemos circuitos de longitud minima k, entonces d(Ri)>=k | m <= 3*n-6 = 3*(n-2) <= k(n-2) (la minima longitud de un circuito es 3) | ||
Reemplazando en la formula de | (Ahora lo seguimos) | ||
ó, otra solucion puede ser: | |||
Como Σ d(Ri) = 2*m, y además, | |||
como tenemos circuitos de longitud minima k, entonces d(Ri)>=k, por lo tanto Σ d(Ri)>=r*k. | |||
Reemplazando en la formula de eular r = m-n+2;(porque es planar y conexo) tenemos: | |||
m-n+2 < 2*m/k | m-n+2 < 2*m/k | ||
Línea 90: | Línea 97: | ||
m <= ((n- 2) * k) /(k-2) | m <= ((n- 2) * k) /(k-2) | ||
=Ejercicio 09.08:= | |||
<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 98: | Línea 105: | ||
<br> Se puede verificar en el grafico: 8 lineas + 16 puntos + 1 = 25 regiones | <br> Se puede verificar en el grafico: 8 lineas + 16 puntos + 1 = 25 regiones | ||
=Ejercicio 09.09:= | |||
<br>a) | <br>a) | ||
<br>2*m = d1*n -> m = d1*n/2 | <br>2*m = d1*n -> m = d1*n/2 | ||
Línea 120: | Línea 127: | ||
<br>http://mathworld.wolfram.com/images/eps-gif/PlatonicGraphs_1000.gif | <br>http://mathworld.wolfram.com/images/eps-gif/PlatonicGraphs_1000.gif | ||
=Ejercicio 09.10:= | |||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
Línea 139: | Línea 146: | ||
Return R representación planar de G. | Return R representación planar de G. | ||
</pre> | </pre> | ||