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 135: | Línea 135: | ||
==Ejercicio 09.08:== | ==Ejercicio 09.08:== | ||
<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>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 | |||
<br>b)Sumando la desigualdad de cada componente conexa parece que: m <= 3*n-6*k | <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 | El problema con esto es que está aplicando la fórmula a c.c. que pueden no cumplir la hipótesis de la desigualdad (que n >= 3). Por esa razón hay que tener cuidado en el análisis. | ||
b)(2da opinion) | b)(2da opinion) |