Práctica 9: Planaridad (Algoritmos 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:

1.No (Es contraible a K5 por los ejes que tocan la "estrella" por afuera)
2.No (Es contraible a K5 por el eje que toca el triángulo por arriba)
3.No (Si se contrae uniendo los 2 nodos de arriba a la izquierda le queda un subrafo isomorfo a K3,3).
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).
5.No (Contiene un subgrafo contraible a K3,3)

Ejercicio 09.02:

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.

Demostración por inducción en la cantidad de hojas:

Caso base:
Si T no tiene ninguna hoja => T es un vértice aislado => Fácilmente podemos dibujarlo de forma planar.
No hay arboles con una sola hoja.
Si T tiene dos hojas => T es un K2, es decir, dos vertices unidos por una arista => Tambien es facil dibujarlo de forma planar.

Paso inductivo:
HI = Para todo arbol T con, a lo sumo, k hojas => T es planar
Sea T un árbol de k+1 hojas.
Sea T' = T - (w,v), con v una hoja de T.
Entonces T' tiene k hojas => Por HI, T' es planar.
Sea R una región de la representación planar de T' que tiene a w en su frontera.
Luego, podemos dibujar a v dentro de R y unirlo con w mediante una arista.
De esta forma obtenemos una representación planar de T.
Entonces T es planar, como queríamos probar.

Ejercicio 09.03:

a)
Sea G un grafo planar con k componentes conexas, n vértices y m aristas.
Sea R la cantidad de regiones que determina cualquier representación planar de G.
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)
Entonces: R = Σ R_i
Pero esta formula cuenta la "región exterior" una vez por cada componente conexa, en lugar de hacerlo una única vez.
Entonces: R = (Σ R_i) - k + 1.
Pero: Σ R_i = m - n + 2 * k.
Entonces: R = m - n + 2 * k - k + 1.
Finalmente: R = m - n + k + 1

b)
Sea G un grafo planar con k componentes conexas, n vértices y m aristas.
Sea G' = G + C, donde C es un camino simple que incide en exactamente un vértice de cada componente conexa de G.
Entonces, G' es planar (pues solo unimos las componentes conexas), conexo y m' = m + k - 1 y n' = n.
Luego, vale que: m' <= 3 * n' - 6 = 3 * n - 6
Finalmente: m' = m + k - 1 <= m + k + 1 <= m <= 3 * n - 6.
Entonces m <= 3 * n - 6, como quería probar.

Ejercicio 09.04:

G planar y para todo v, d(v) >= 3 -> 2 = n-m+r y 3*n <= 2*m = Σd(v) -> n <= 2/3*m
-> 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:

a) Sup. que no. Entonces para todo v, d(v) >= 6. Como G es planar -> m <= 3*n-6.
6*n <= Σ d(v) = 2*m -> 6*n <= 2*m -> m >= 3*n ABS (m <= 3*n-6)

b) Sup. que no. Entonces para todo v, d(v) >= 5 -> Σ d(v) = 2*m >= 5*n
G es planar -> m <= 3*n-6
-> 2*(3*n-6) >= 2*m >= 5*n
-> 6*n-12 >= 5*n
-> n >= 12
-> ABS

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

G es planar -> r = m-n+2. Queremos averiguar m-n+1 (o sea, sin la region que cubre todo)
n = p + 2*l
2*mInt = Σ d(v) = 4*p + 2*l -> mInt = 2*p + l
m = mExt + mInt = 2*l + (2*p + l) = 3*l + 2*p
-> m-n+1 = (3*l + 2*p) - (p + 2*l) + 1 = l + p + 1
Se puede verificar en el grafico: 8 lineas + 16 puntos + 1 = 25 regiones

Ejercicio 09.09:

a)
2*m = d1*n -> m = d1*n/2
d2*r = 2*m = d1*n -> r = d1/d2*n

b)Usando que 1. d2*r = 2*m = d1*n y 2. n-m+r=2 -> r+n = 2+m:
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

c)
(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

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

Ejercicio 09.10:

a)
b)

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.