Edición de «Práctica 9: Planaridad (Algoritmos III)»

{{Back|Algoritmos y Estructuras de Datos III}}

==Propiedades==
(Para todo G: grafo)

* (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 K3,3
* (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

==Ejercicio 09.01:==
<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>3.No (Si se contrae uniendo los 2 nodos de arriba a la izquierda le queda un subrafo isomorfo a K3,3).
<br>4.No (Sobre el rombo de fuera, si se contrae el nodo de arriba con el de la derecha, y el de abajo con el de la izquierda, queda entonces un 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>
<br>Demostración por inducción en la cantidad de hojas: 
<br>
<br> Caso base:
<br>Si T no tiene ninguna hoja => T es un vértice aislado => Fácilmente podemos dibujarlo de forma planar.
<br>No hay arboles con una sola hoja.
<br>Si T tiene dos hojas => T es un K2, es decir, dos vertices unidos por una arista => Tambien es facil dibujarlo de forma planar.
<br>
<br> Paso inductivo:
<br> HI = Para todo arbol T con, a lo sumo, k hojas => T es planar
<br>Sea T un árbol de k+1 hojas.
<br>Sea T' = T - (w,v), con v una hoja de T.
<br>Entonces T' tiene k hojas => Por HI, T' es planar.
<br>Sea R una región de la representación planar de T' que tiene a w en su frontera.
<br>Luego, podemos dibujar a v dentro de R y unirlo con w mediante una arista.
<br>De esta forma obtenemos una representación planar de T.
<br>Entonces T es planar, como queríamos probar.

==Ejercicio 09.03:==
<br>a)
<br>Sea G un grafo planar con k componentes conexas, n vértices y m aristas.
<br>Sea R la cantidad de regiones que determina cualquier representación planar de G.
<br>Para cada una de las componentes conexas de G vale la formula de Euler, es decir, R_i = m_i - n_i + 2. (cantidad de regiones de la i-esima componente conexa)
<br>Entonces: R = Σ R_i
<br>Pero esta formula cuenta la "región exterior" una vez por cada componente conexa, en lugar de hacerlo una única vez.
<br>Entonces: R = (Σ R_i) - k + 1.
<br>Pero: Σ R_i = m - n + 2 * k.
<br>Entonces: R = m - n + 2 * k - k + 1.
<br>Finalmente: R = m - n + k + 1
<br>
<br>b)
<br>Sea G un grafo planar con k componentes conexas, n vértices y m aristas.
<br>Sea G' = G + C, donde C es un camino simple que incide en exactamente un vértice de cada componente conexa de G.
<br>Entonces, G' es planar (pues solo unimos las componentes conexas), conexo y m' = m + k - 1 y n' = n.
<br>Luego, vale que: m' <= 3 * n' - 6 = 3 * n - 6 
<br>Finalmente: m' = m + k - 1 <= m + k + 1 <= m <= 3 * n - 6.
<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>-> 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>6*n <= Σ d(v) = 2*m -> 6*n <= 2*m -> m >= 3*n ABS (m <= 3*n-6)

<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> -> 2*(3*n-6) >= 2*m >= 5*n 
<br> -> 6*n-12 >= 5*n 
<br> -> n >= 12 
<br> -> ABS

<br>c) Sup. G y Gc son planares
<br> -> m(G) <= 3*n-6, m(Gc) = n(n-1)/2 - m(G) >= n(n-1)/2 - (3*n-6), y 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

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.
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. Por lo tanto: Σ d(Ri)>=r*k.
Reemplazando en la formula de Euler r = m-n+2 (porque es planar y conexo) tenemos:
m-n+2 < 2*m/k 

Despejamos m, y listo.
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> n = p + 2*l
<br> 2*mInt = Σ d(v) = 4*p + 2*l -> mInt = 2*p + l
<br> m = mExt + mInt =  2*l + (2*p + l) = 3*l + 2*p
<br> -> m-n+1 = (3*l + 2*p) - (p + 2*l) + 1 = l + p + 1
<br> Se puede verificar en el grafico: 8 lineas + 16 puntos + 1 = 25 regiones

==Ejercicio 09.09:==
<br>a)
<br>2*m = d1*n -> m = d1*n/2
<br>d2*r = 2*m = d1*n -> r = d1/d2*n

<br>b)Usando que '''1. d2*r = 2*m = d1*n''' y '''2. n-m+r=2 -> r+n = 2+m''':
<br>n*(2*d1 + 2*d2 - d1*d2) = 2*d1*n + 2*d2*n - d2*d1*n =(1.) 2*d2*r + 2*d2*n - d2*2*m = 2*d2*(r+n) - d2*2*m =(2.) 2*d2*(2+m) - d2*2*m = 4*d2 + d2*2*m - d2*2*m = 4*d2

<br>c)
<br>(d1-2)(d2-2) = d1*d2 - 2*d1 - 2*d2 + 4 = d1*d2 - (2*d1 + 2*d2) + 4 = -(2*d1 + 2*d2 - d1*d2) + 4 < 0 + 4 = 4

<br>d)Usando que '''d1 >= 3 y d2 >= 3''':
<br>(d1-2)(d2-2) < 4 <=> (d1-2)(d2-2) <= 3
<br>-> 1 = (3-2) <= (d2-2) = (d2-2)(3-2) <= (d1-2)(d2-2) <= 3 -> 3 <= d2 <= 5
<br>Entonces reemplazando los 3 casos de d2:
<br>d2 = 3 -> (d1-2)(3-2) <= 3 <=> d1-2 <= 3 <=> d1 <= 5 -> 3 <= d1 <= 5
<br>d2 = 4 -> (d1-2)(4-2) <= 3 <=> (d1-2)*2 <= 3 <=> d1-2 <= 3/2 ~ 1 -> d1 <= 3 -> d1 = 3
<br>d2 = 5 -> (d1-2)(5-2) <= 3 <=> (d1-2)*3 <= 3 <=> d1-2 <= 1 -> d1 <= 3 -> 3 <= d1 <= 3 -> d1 = 3
<br>Con lo cual, los grafos son:
<br>{d1=3,d2=3}{d1=4,d2=3}{d1=3,d2=4}{d1=3,d2=5}{d1=5,d2=3}
<br>http://mathworld.wolfram.com/images/eps-gif/PlatonicGraphs_1000.gif

==Ejercicio 09.10:==
<br>a)
<br>b)
<pre>
Inicialización. Tomar como R inicial un circuito de G.
• Mientras R no sea una representación planar de G:
	• Particionar R en partes relativas a G\R
	• Identificar para cada parte p el conjunto F(p) de las caras en las que p es potencialmente dibujable
	Si para algún p, F(p) es vacío
		Parar y Return FALSE
	Sino
		si hay algun p para el cual F(p) tiene una sola cara f
			elegir esa cara
		sino
			elegir una cara cualquiera f correspondiente a un p cualquiera.
	Determinar un camino q, formado por ejes de p, entre un par de nodos de contacto de p.
	Poner R = R U q
Return R representación planar de G.
</pre>

[[Category: Prácticas]]