Diferencia entre revisiones de «Práctica 9: Planaridad - Coloreo (Algoritmos III)»
m (Revierto, estaba bien en un principio) |
|||
(No se muestran 72 ediciones intermedias de 14 usuarios) | |||
Línea 1: | Línea 1: | ||
< | {{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 | |||
* (DEF) '''Numero cromatico''' X(G) = minimo # de colores para colorear los vertices de G | |||
* (OBS) | |||
** 1. Si G es Kn -> X(G) = n | |||
** 2. Si G es bipartito y m>0 -> X(G) = 2 | |||
** 3. Si G es un circuito simple par -> X(G) = 2 | |||
** 4. Si G es un circuito simple impar -> X(G) = 3 | |||
** 5. Si G es arbol y n>1 -> X(G) = 2 | |||
* (TEO) Si H es subgrafo de G -> X(H) <= X(G) | |||
* (DEF) w(G) = # de vertices de una clique maxima de G | |||
* (TEO) w(G) <= X(G) <= max d(v)+1 | |||
* (TEO) Si G es conexo y no un circuito impar ni es completo, tq max d(v) >= 3 -> X(G) <= max d(v) | |||
* (TEO) Si G es planar -> X(G) <= 4 | |||
* (DEF) '''Polinomio cromatico''' PG(c) = # de formas de colorear los vertices de G un c colores | |||
* (OBS) | |||
** 1. Si G no tiene ejes -> PG(c) = c^n | |||
** 2. Si G es Kn -> PG(c) = c(c-1)...(c-n+1) | |||
** 3. Si G es un camino simple de k vertices -> PG(c) = c(c-1)^(k-1) | |||
** 4. Si G esta formado por k comp. conexas -> PG(c) = PG1(c)*PG2(c)*...*PGk(c) | |||
* (DEF) '''Indice cromatico''' X'(G) = minimo # de colores para colorear los ejes de G | |||
* (TEO) X'(G) = max d(v) o X'(G) = max d(v)+1 | |||
= Planaridad = | |||
==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 triángulo por arriba) | ||
<br>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.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) | <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>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:== | ==Ejercicio 09.03:== | ||
<br>G planar -> 2 = n-m+r y 3*n <= 2*m = Σd(v) -> n <= 2/3*m | <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. | |||
<br> Este es el ej 9.4 | |||
<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.04:== | ==Ejercicio 09.04:== | ||
<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 | <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) > | <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 -> 2*(3*n-6) >= 2*m >= 5*n -> 6*n-12 >= 5*n -> n >= 12 -> ABS | <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>c) Sup. G y Gc son planares | ||
Línea 40: | Línea 103: | ||
<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 | ||
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.05:== | ==Ejercicio 09.05:== | ||
Línea 46: | Línea 111: | ||
==Ejercicio 09.06:== | ==Ejercicio 09.06:== | ||
<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 52: | Línea 116: | ||
<br> m = mExt + mInt = 2*l + (2*p + l) = 3*l + 2*p | <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> -> 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.07:== | ==Ejercicio 09.07:== | ||
m <= 3*n-6 = 3*(n-2) <= k(n-2) (la minima longitud de un circuito es 3) | |||
(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 | |||
Despejamos m, y listo. | |||
m <= ((n- 2) * k) /(k-2) | |||
==Ejercicio 09.08:== | ==Ejercicio 09.08:== | ||
<br>a)Σ{i=1..k} (ni - mi + ri) = n - m + (r- | <br>a) Hacemos la cuenta en cada componente conexa. El único problema es la región exterior, que se está contando muchas veces (k-1 veces de más): | ||
<br>b)m <= 3*n-6*k | |||
.Σ{i=1..k} (ni - mi + ri) = n - m + (r+(k-1)) = 2k <=> n-m+r=k+1 <=> n-m+r-k = 1 | |||
<br>b)Sumando la desigualdad de cada componente conexa parece que: m <= 3*n-6*k | |||
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. | |||
b)(2da opinion) | |||
La demostración sale igual para probar que vale para los conexos. | |||
==Ejercicio 09.09:== | ==Ejercicio 09.09:== | ||
Línea 63: | Línea 150: | ||
<br>2*m = d1*n -> m = d1*n/2 | <br>2*m = d1*n -> m = d1*n/2 | ||
<br>d2*r = 2*m = d1*n -> r = d1/d2*n | <br>d2*r = 2*m = d1*n -> r = d1/d2*n | ||
<br>b) | |||
<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>c) | ||
<br>d) | <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 | ||
http://mathworld.wolfram.com/images/eps-gif/PlatonicGraphs_1000.gif | |||
<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:== | ==Ejercicio 09.10:== | ||
Línea 88: | Línea 188: | ||
</pre> | </pre> | ||
= Coloreo = | |||
==Ejercicio 09.11:== | ==Ejercicio 09.11:== | ||
Notas: | Notas: | ||
Línea 104: | Línea 203: | ||
==Ejercicio 09.12:== | ==Ejercicio 09.12:== | ||
<br>a) | <br>a) | ||
<br>Vertices = Variables | |||
<br>Ejes = Relacion "depende de" | |||
<br>Colores = Posiciones de Memoria | |||
<br>b) | <br>b) | ||
==Ejercicio 09.13:== | ==Ejercicio 09.13:== | ||
<br>Vertices = Comisiones | <br>Vertices = Comisiones | ||
<br>Ejes = | <br>Ejes = Relacion "comparte legisladores con" | ||
<br>Colores = Reuniones | |||
==Ejercicio 09.14:== | ==Ejercicio 09.14:== | ||
<br>a) | <br>a) | ||
<br>Vertices = Experimentos | |||
<br>Ejes = Relacion "se superpone con" | |||
<br>Colores = Observatorios | |||
<br>b) | <br>b) | ||
==Ejercicio 09.15:== | ==Ejercicio 09.15:== | ||
<br>Vertices = Matematicos | |||
<br>Ejes = Relacion "tiene conflicto con" | |||
<br>Colores = Hoteles | |||
==Ejercicio 09.16:== | ==Ejercicio 09.16:== | ||
<br>Vertices = Radios | |||
<br>Ejes = Relacion "esta a menos de 100 km de" | |||
<br>Colores = Frecuencias | |||
==Ejercicio 09.17:== | ==Ejercicio 09.17:== | ||
<br>a) Sup. que no es conexo. Sea G' = G-C1, es decir, G sin la comp. conexa C1. | <br>a) Sup. que no es conexo. Sea G' = G-C1, es decir, G sin la comp. conexa C1. | ||
Línea 129: | Línea 245: | ||
<br>d) | <br>d) | ||
Por abs. Supongamos que G tiene una clique de corte S. Sean Gi,...,Gs las componentes de sacar a S de G, pero ademas esas componentes tiene la clique S. | |||
Como el grafo es color critico, vale que cada componente es k-1 coloreable. | |||
En particular como S es una cloque cada vertice de esa clique usa colores distintos. Ahora tenemos que los Gi son k-1 coloreables y cada una tiene distintos colores en S. Si cada Gi usa los mismos colores en S, se puede generar un coloreo k-1 de G. (no fiarse de mi dem., pero quiza sirve de idea) | |||
==Ejercicio 09.18:== | ==Ejercicio 09.18:== | ||
Por induccion: | |||
* CB n = 2 ! | |||
* 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 | |||
<br> Otra forma: | |||
Ir borrando vértices, hasta que el subgrafo que queda al sacar cualquier vertice queda critico. | |||
==Ejercicio 09.19:== | ==Ejercicio 09.19:== | ||
<br>a) | <br>a) | ||
<br>=>)Sup. que G tiene un circuito C de long. impar -> X(C)= 3 -> no hay forma de usar solo 2 colores -> ABS | <br>=>)Sup. que G tiene un circuito C de long. impar -> X(C)= 3 -> no hay forma de usar solo 2 colores -> ABS | ||
<br><=)Como G no tiene circuitos de long. impar -> G es bipartito -> X(G) = 2 (ya que se puede usar un color para la primer particion y otro para la segunda) -> G es 2-coloreable OK | <br><=)Como G no tiene circuitos de long. impar -> G es bipartito -> X(G) = 2 (ya que se puede usar un color para la primer particion y otro para la segunda) -> G es 2-coloreable OK | ||
<br>b) | <br>b) Con BFS (si llego a un vertice marcado y se quiere pintar con el mismo color -> no es 2-coloreable) | ||
<br>c) | <br>c) O(n+m) | ||
==Ejercicio 09.20:== | ==Ejercicio 09.20:== | ||
El grafo de Grotzsch. (Es el grafo de Mycielski 4, M_4.) | |||
==Ejercicio 09.21:== | ==Ejercicio 09.21:== | ||
Línea 150: | Línea 276: | ||
<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') -> X(G)+X(Gc) = X(G')+X( | <br>2. dG(v) >= X(G') y dGc(v) >= X(Gc') -> | ||
X(G') <= X(G) + 1 <= dG(v) + 1 y | |||
X(G'c) <= X(Gc) + 1 <= dGc(v) + 1 entonces | |||
<br>X(G') + X(G'c) <= dG(v) + dGc(v) + 2 (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 165: | Línea 293: | ||
==Ejercicio 09.22:== | ==Ejercicio 09.22:== | ||
<br> | |||
<br> | Por absurdo. | ||
<br> | Supongamos que G no es ninguno de los que dice el enunciado, entonces se puede usar el teorema de brooks. | ||
<br> X(G) <= maximoGrado(G). | |||
<br> Como el grafo es regular, maximoGrado(G)= d(G). | |||
<br> Para el grafo complemento vale que X(Gc) <= maximoGrado(Gc)+1 = d(Gc)+1. | |||
(el complemento de un regular es regular). | |||
<br> d(Gc)+1 = n-d(G)+1-1 | |||
<br> X(G) + X(Gc) <= d(G)+n-d(G) = n Absurdo, porque deberia ser n+1 | |||
==Ejercicio 09.23:== | ==Ejercicio 09.23:== | ||
<br>a) | <br>a) Si toda region tiene un numero par de aristas frontera -> todos los circuitos de G tienen longitud par -> G es bipartito -> G es 2-coloreable | ||
<br>b) | <br>b) Sup. que G es 2-coloreable -> G es bipartito -> el caso con mas ejes seria el del bipartito completo, entonces tomando V1 como una de las particiones, la cant. de ejes seria |V1|(8-|V1|) = 13 | ||
-> -1|V1|^2 + 8|V1| - 13 = 0. Pero no hay un numero entero que cumpla esto -> ABS | |||
Hay otra manera de resolver este punto. Suponemos que G es 2-Coloreable. Entonces G es bipartito. Como el enunciado dice que G es planar, y asumimos que es bipartito, G debe cumplir con m<=2n-4. (esta es una condiciòn de los grafos planares bipartitos). | |||
Como m=13 y n=8, m<=2n-4 <=> 13<=12, lo cual no es cierto. Luego nuestro supuesto de que G es bipartito es falso. | |||
<br>c) | <br>c) | ||
==Ejercicio 09.24:== | ==Ejercicio 09.24:== | ||
En la clase se mostró la demo de que todo grafo planar puede ser coloreado con 5 colores. Esta demo usaba el hecho de que todo grafo planar tiene al menos un vertice de grado menor o igual a 5. | |||
Este ejercicio es similar a dicha demostración, salvo por el hecho de que aquí sabemos, por enunciado, que tenemos al menos un vertice de grado menor o igual a 4. | |||
==Ejercicio 09.25:== | ==Ejercicio 09.25:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>1. k(k-1) | ||
<br>2. k(k-1)^2 | |||
<br>3. k(k-1)(k-2) | |||
<br>4. k(k-1)^2(k-2) + k(k-1)^2 = (k-1)^4+(k-1) | |||
<br> | |||
Numerar los vertices de C4 v1,v2,v3,v4 | |||
<br>v1---v2 | |||
<br>|____| | |||
<br>v4---v3 | |||
<br>En el circuito el primer termino de la suma corresponde a v2,v4 con distintos colores, lo que obliga a v3 tener k-2 elecciones. | |||
El segundo termino corresponde a v2 y v4 con los mismos colores. | |||
<br>5. k(k-1)(k-2)(k-3) | |||
<br>6. k(k-1)(k-2)(k-1)^2 | |||
<br>7. k(k-1)(k-2)...(k-(n-1)) | |||
<br>b) Vamos tomando k crecientes a partír de 0. Luego, el primer valor de k para el que PG(k)!=0 es el número cromático. | |||
Por ejemplo en el 2) PG(0)=0, PG(1)=0, PG(2)=2. Entonces X(G)=2. | |||
==Ejercicio 09.26:== | ==Ejercicio 09.26:== | ||
<br>a) | <br>a) | ||
Línea 207: | Línea 370: | ||
<br>b) | <br>b) | ||
==Ejercicio 09.34:== | ==Ejercicio 09.34:== | ||
<br>1. X'(G) = 4 | |||
<br>2. X'(G) = 3 (es bipartito) | |||
<br>3. X'(G) = 3 (n-1, es completo con n par) | |||
<br>4. X'(G) = 5 (n, es completo con n impar) | |||
==Ejercicio 09.35:== | ==Ejercicio 09.35:== | ||
Se puede resolver coloreando los ejes de un multigrafo, asignando vertices a los profesores y los alumnos, y cada eje representa 1 hora, entonces por ej. si un profesor le da 3 horas a un grupo, hay 3 ejes entre los dos vertices. | |||
[[Category: Prácticas]] |
Revisión actual - 23:42 27 jun 2015
Propiedades[editar]
(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
- (DEF) Numero cromatico X(G) = minimo # de colores para colorear los vertices de G
- (OBS)
- 1. Si G es Kn -> X(G) = n
- 2. Si G es bipartito y m>0 -> X(G) = 2
- 3. Si G es un circuito simple par -> X(G) = 2
- 4. Si G es un circuito simple impar -> X(G) = 3
- 5. Si G es arbol y n>1 -> X(G) = 2
- (TEO) Si H es subgrafo de G -> X(H) <= X(G)
- (DEF) w(G) = # de vertices de una clique maxima de G
- (TEO) w(G) <= X(G) <= max d(v)+1
- (TEO) Si G es conexo y no un circuito impar ni es completo, tq max d(v) >= 3 -> X(G) <= max d(v)
- (TEO) Si G es planar -> X(G) <= 4
- (DEF) Polinomio cromatico PG(c) = # de formas de colorear los vertices de G un c colores
- (OBS)
- 1. Si G no tiene ejes -> PG(c) = c^n
- 2. Si G es Kn -> PG(c) = c(c-1)...(c-n+1)
- 3. Si G es un camino simple de k vertices -> PG(c) = c(c-1)^(k-1)
- 4. Si G esta formado por k comp. conexas -> PG(c) = PG1(c)*PG2(c)*...*PGk(c)
- (DEF) Indice cromatico X'(G) = minimo # de colores para colorear los ejes de G
- (TEO) X'(G) = max d(v) o X'(G) = max d(v)+1
Planaridad[editar]
Ejercicio 09.01:[editar]
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:[editar]
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:[editar]
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.
Este es el ej 9.4
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.04:[editar]
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 n2-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.05:[editar]
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.06:[editar]
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.07:[editar]
m <= 3*n-6 = 3*(n-2) <= k(n-2) (la minima longitud de un circuito es 3) (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
Despejamos m, y listo. m <= ((n- 2) * k) /(k-2)
Ejercicio 09.08:[editar]
a) Hacemos la cuenta en cada componente conexa. El único problema es la región exterior, que se está contando muchas veces (k-1 veces de más):
.Σ{i=1..k} (ni - mi + ri) = n - m + (r+(k-1)) = 2k <=> n-m+r=k+1 <=> n-m+r-k = 1
b)Sumando la desigualdad de cada componente conexa parece que: m <= 3*n-6*k
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.
b)(2da opinion) La demostración sale igual para probar que vale para los conexos.
Ejercicio 09.09:[editar]
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:[editar]
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.
Coloreo[editar]
Ejercicio 09.11:[editar]
Notas:
- W(G) <= X(G) <= max d(G)+1
- Si G es planar -> X(G) <= 4
a)
1. 3 <= X(G) <= 4; X(G) =
2. 3 <= X(G) <= 4; X(G) = 3
3. 3 <= X(G) <= 5; X(G) =
4. 3 <= X(G) <= 4; X(G) = 3
b)
Ejercicio 09.12:[editar]
a)
Vertices = Variables
Ejes = Relacion "depende de"
Colores = Posiciones de Memoria
b)
Ejercicio 09.13:[editar]
Vertices = Comisiones
Ejes = Relacion "comparte legisladores con"
Colores = Reuniones
Ejercicio 09.14:[editar]
a)
Vertices = Experimentos
Ejes = Relacion "se superpone con"
Colores = Observatorios
b)
Ejercicio 09.15:[editar]
Vertices = Matematicos
Ejes = Relacion "tiene conflicto con"
Colores = Hoteles
Ejercicio 09.16:[editar]
Vertices = Radios
Ejes = Relacion "esta a menos de 100 km de"
Colores = Frecuencias
Ejercicio 09.17:[editar]
a) Sup. que no es conexo. Sea G' = G-C1, es decir, G sin la comp. conexa C1.
Como es color critico -> X(G') < X(G) y X(C1) < X(G)
Sea f1 un coloreo para C1' / ese coloreo se realiza con X(C1') colores. Definamos analogamente f2 para C1. Podemos construir un coloreo valido para G haciendo f1∪f2 -> tenemos un coloreo de max{ X(G'), X(C1) } -> X(G) < k -> ABS (porque X(G) = k)
b) Sup. Ex. v є V / d(v) < k-1. Hacemos G' = G-v
Como es color critico -> X(G') < X(G) (Obs: para todo G, X(G-v)=X(G)-1)
Sea f' un coloreo para G' con X(G)-1 colores. Si coloreamos a v con el color menor no usado por sus vecinos -> f(v) <= k-1 -> tenemos un coloreo para G con menos de k colores -> ABS
c) Sea C1 una comp. conexa de G-v -> X(C1+v) < X(G) y X(G-C1) < X(G)
Coloreamos en forma optima C1+v1 con f1 y G-C1 con f2.
- Si f1(v)=f2(v) -> tenemos un coloreo con menos de k colores -> ABS
- Si f1(v)!=f2(v) -> reordenamos los colores de f2 de forma que la particion en conj. indep. sea la misma y volvemos al caso f1(v)=f2(v) -> ABS
d)
Por abs. Supongamos que G tiene una clique de corte S. Sean Gi,...,Gs las componentes de sacar a S de G, pero ademas esas componentes tiene la clique S.
Como el grafo es color critico, vale que cada componente es k-1 coloreable.
En particular como S es una cloque cada vertice de esa clique usa colores distintos. Ahora tenemos que los Gi son k-1 coloreables y cada una tiene distintos colores en S. Si cada Gi usa los mismos colores en S, se puede generar un coloreo k-1 de G. (no fiarse de mi dem., pero quiza sirve de idea)
Ejercicio 09.18:[editar]
Por induccion:
- CB n = 2 !
- 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
Otra forma:
Ir borrando vértices, hasta que el subgrafo que queda al sacar cualquier vertice queda critico.
Ejercicio 09.19:[editar]
a)
=>)Sup. que G tiene un circuito C de long. impar -> X(C)= 3 -> no hay forma de usar solo 2 colores -> ABS
<=)Como G no tiene circuitos de long. impar -> G es bipartito -> X(G) = 2 (ya que se puede usar un color para la primer particion y otro para la segunda) -> G es 2-coloreable OK
b) Con BFS (si llego a un vertice marcado y se quiere pintar con el mismo color -> no es 2-coloreable)
c) O(n+m)
Ejercicio 09.20:[editar]
El grafo de Grotzsch. (Es el grafo de Mycielski 4, M_4.)
Ejercicio 09.21:[editar]
a) Por induccion en n:
- CB: n = 1
X(G) = X(Gc) = 1 -> 2 <= 2 OK
- PI:
Saco un vertice -> G' = G-v
X(G)+X(Gc) = X(G')+X(Gc')+k (k cte.). Separamos en casos:
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
2. dG(v) >= X(G') y dGc(v) >= X(Gc') ->
X(G') <= X(G) + 1 <= dG(v) + 1 y
X(G'c) <= X(Gc) + 1 <= dGc(v) + 1 entonces
X(G') + X(G'c) <= dG(v) + dGc(v) + 2 (como dGc(v)=n-dG(v)-1) dG(v)+(n-dG(v)-1)+2 = n+1 OK
b) Probamos ambas desigualdades:
- qvq n <= X(G)*X(Gc)
n <= X(G)*mayor particion del coloreo -> n <= X(G)*α(G) = X(G)*w(Gc)
X(G)*w(Gc) <= X(G)*X(Gc) -> n <= X(G)*X(Gc) OK
- qvq X(G)*X(Gc) <= [(n+1)/2]^2
Como para todo a,b: √(a*b) <= (a+b)/2 -> X(G)*X(Gc) <= [(X(G)+X(Gc))/2]^2 <= [(n+1)/2]^2 (por a)
c)
(X(G)+X(Gc))/2 >= (por b) √(X(G)*X(Gc)) >= √n -> X(G)+X(Gc) >= 2√n
Ejercicio 09.22:[editar]
Por absurdo.
Supongamos que G no es ninguno de los que dice el enunciado, entonces se puede usar el teorema de brooks.
X(G) <= maximoGrado(G).
Como el grafo es regular, maximoGrado(G)= d(G).
Para el grafo complemento vale que X(Gc) <= maximoGrado(Gc)+1 = d(Gc)+1.
(el complemento de un regular es regular).
d(Gc)+1 = n-d(G)+1-1
X(G) + X(Gc) <= d(G)+n-d(G) = n Absurdo, porque deberia ser n+1
Ejercicio 09.23:[editar]
a) Si toda region tiene un numero par de aristas frontera -> todos los circuitos de G tienen longitud par -> G es bipartito -> G es 2-coloreable
b) Sup. que G es 2-coloreable -> G es bipartito -> el caso con mas ejes seria el del bipartito completo, entonces tomando V1 como una de las particiones, la cant. de ejes seria |V1|(8-|V1|) = 13
-> -1|V1|^2 + 8|V1| - 13 = 0. Pero no hay un numero entero que cumpla esto -> ABS
Hay otra manera de resolver este punto. Suponemos que G es 2-Coloreable. Entonces G es bipartito. Como el enunciado dice que G es planar, y asumimos que es bipartito, G debe cumplir con m<=2n-4. (esta es una condiciòn de los grafos planares bipartitos). Como m=13 y n=8, m<=2n-4 <=> 13<=12, lo cual no es cierto. Luego nuestro supuesto de que G es bipartito es falso.
c)
Ejercicio 09.24:[editar]
En la clase se mostró la demo de que todo grafo planar puede ser coloreado con 5 colores. Esta demo usaba el hecho de que todo grafo planar tiene al menos un vertice de grado menor o igual a 5. Este ejercicio es similar a dicha demostración, salvo por el hecho de que aquí sabemos, por enunciado, que tenemos al menos un vertice de grado menor o igual a 4.
Ejercicio 09.25:[editar]
a)
1. k(k-1)
2. k(k-1)^2
3. k(k-1)(k-2)
4. k(k-1)^2(k-2) + k(k-1)^2 = (k-1)^4+(k-1)
Numerar los vertices de C4 v1,v2,v3,v4
v1---v2
|____|
v4---v3
En el circuito el primer termino de la suma corresponde a v2,v4 con distintos colores, lo que obliga a v3 tener k-2 elecciones.
El segundo termino corresponde a v2 y v4 con los mismos colores.
5. k(k-1)(k-2)(k-3)
6. k(k-1)(k-2)(k-1)^2
7. k(k-1)(k-2)...(k-(n-1))
b) Vamos tomando k crecientes a partír de 0. Luego, el primer valor de k para el que PG(k)!=0 es el número cromático.
Por ejemplo en el 2) PG(0)=0, PG(1)=0, PG(2)=2. Entonces X(G)=2.
Ejercicio 09.26:[editar]
a)
b)
c)
Ejercicio 09.27:[editar]
a)
b)
c)
d)
e)
f)
Ejercicio 09.28:[editar]
a)
b)
c)
d)
Ejercicio 09.29:[editar]
a)
b)
c)
d)
e)
Ejercicio 09.30:[editar]
Ejercicio 09.31:[editar]
a)
b)
Ejercicio 09.32:[editar]
Ejercicio 09.33:[editar]
a)
b)
Ejercicio 09.34:[editar]
1. X'(G) = 4
2. X'(G) = 3 (es bipartito)
3. X'(G) = 3 (n-1, es completo con n par)
4. X'(G) = 5 (n, es completo con n impar)
Ejercicio 09.35:[editar]
Se puede resolver coloreando los ejes de un multigrafo, asignando vertices a los profesores y los alumnos, y cada eje representa 1 hora, entonces por ej. si un profesor le da 3 horas a un grupo, hay 3 ejes entre los dos vertices.