Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si
inicias sesión o
creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.
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 61: |
Línea 61: |
|
| |
|
| ==Ejercicio 09.03:== | | ==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.
| |
|
| |
|
| |
|
| |
|
| |
|
| |
| <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>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 |