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 30: |
Línea 30: |
|
| |
|
| ==Ejercicio 08.04:== | | ==Ejercicio 08.04:== |
| Probamos las 2 implicaciones por separado:
| |
|
| |
| =>) Como G es conexo y tiene circuito euleriano, cada nodo tiene grado par y por lo tanto G contiene algun ciclo C. Si sacamos los ejes de C pueden pasar 2 cosas:
| |
| Si C era el único circuito, luego trivial.
| |
| Si no nos queda G' donde cada nodo también tendrá grado par, y por lo tanto volvemos a aplicar esto recursivamente.
| |
|
| |
| (Una demostración más formal se puede hacer usando inducción, ya que justamente como dije arriba, es cuestión de aplicar recursivamente una función que nos saque un circuito).
| |
|
| |
| <=) Sea G conexo y particionable en K circuitos: C1, C2, ... , Ck
| |
| Si sacamos los ejes de C1, luego como G es conexo nos quedan nodos que habían en común entre C1, y otro Ci (Esto es casi trivial probarlo). Luego hay que nuevamente ir recorriendo los ciclos, sabiendo que tendremos nodos compartidos con ciclos no recorridos anteriormente, y esto se podrá hacer k veces, y luego habremos encontrado nuestro circuito euleriano.
| |
|
| |
| ==Ejercicio 08.05:== | | ==Ejercicio 08.05:== |
| Supongamos que NO. | | Supongamos que NO. |