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 74: |
Línea 74: |
| <br>b) | | <br>b) |
| <br>Sea G un grafo planar con k componentes conexas, n vértices y m aristas. | | <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.
| |
|
| |
|
|
| |
|