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 83: | Línea 83: | ||
==Ejercicio 09.07:== | ==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 | ||