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 72: |
Línea 72: |
|
| |
|
| ==Ejercicio 08.09:== | | ==Ejercicio 08.09:== |
| <br>a) (Tiene que salir con algo parecido a este teorema) | | <br>a) |
| <br> Un grafo conexo es euleriano <=> para todo v, d(v) es par
| |
| <br> =>) Un vertice que aparece k veces en un circuito euleriano (o k+1, si es el vertice de inicio y final se cuenta 2 veces) debe tener grado 2k -> OK
| |
| <br> <=) Sea W = {v0,e0,..,e(l-1),vl} (vi vertices, ei ejes) el camino mas largo que usa cada eje solo una vez. Como no se puede extender, contiene todos los ejes en vl. Como la cantidad de ejes es par -> vl=v0 -> W es un circuito. Sup. que no es euleriano -> G tiene un eje e =(u,vi) para algun u fuera de W. Entonces el camino {u,e,vi,ei,..,e(l-1),vl,e0,..,e(i-1),vi} es mas largo que W -> ABS
| |
| | |
| <br>b) Se puede encontrar con el siguiente algoritmo: | | <br>b) Se puede encontrar con el siguiente algoritmo: |
| <pre> | | <pre> |