Estoy mirando la prueba de que $G$ tiene una Euler tour iff en grados($v$)=out-grado($v$), que he encontrado en este sitio: www.cs.duke.edu/courses/fall09/cps230/hws/hw3/headsol.pdf (Problema 2)
Un ciclo simple es un camino en un grafo que comienza y termina en el mismo vértice sin pasar por el mismo vértice más de una vez.
Un complejo ciclo es un ciclo que pasa por el mismo vértice más de una vez. Fácilmente podemos descomponer un complejo ciclo a un conjunto de ciclos simples por romper el ciclo en aquellos puntos donde el ciclo pasa a través del mismo vértice más de una vez.
Como la primera parte de nuestra prueba, vamos a probar que si $G$ tiene una de Euler de un tour en el grado($v$)=out-grado($v$) para cada vértice $v \in V$.
Ya hemos establecido que un complejo ciclo se puede descomponer a una colección de ciclos simples. Sin embargo vértices en un ciclo simple en grado($v$)=out-grado($v$)=1.
Desde cada vértice en un complejo ciclo, y por lo tanto en una de Euler tour, es parte de uno o más ciclos simples tendrá en grados($v$)=out-grado($v$).
- Me podría dar un ejemplo de un complejo ciclo que se descompone en un conjunto de ciclos simples, donde podemos ver que en los grados($v$)=out-grado($v$)?
La segunda parte de nuestra prueba nos obliga a demostrar que si en el grado($v$)=out-grado($v$) para cada vértice $v \in V$, $G$ tiene una Euler-tour.
Deje $C$ ser el complejo ciclo que incluye la mayoría de los bordes en $G$.
En orden para $G$ a no ser una de Euler tour, debe haber algunos vértices que $C$ pasa a través de ( ya que el gráfico está conectado ) pero no agota todos los bordes. Ya hemos establecido que los vértices de un complejo ciclo tienen la propiedad de que en el grado($v$)=out-grado($v$). Por lo tanto, $G'=G-C$ también tienen esa propiedad. Si un componente conectado en un gráfico que tiene en grado($v$)=out-grado ($v$), a continuación, contiene al menos un ciclo de $C'$. Sin embargo, esto contradice nuestra hipótesis inicial de que $C$ es el ciclo que incluye la mayoría de los bordes en $G$ dado que se iba a construir un ciclo más largo, comenzando en algún vértice común de $C$$C'$, atravesando todas las de $C$s de los bordes y, a continuación, $C'$s de los bordes. Por lo tanto, $C$ es una de Euler tour.
- Primero de todo, dice que "a fin de $G$ a no ser una de Euler tour, debe haber algunos vértices que $C$ pasa a través de ( ya que el gráfico está conectado ) pero no agota todos los bordes. "
No he entendido por qué tenemos que mostrar que $G$ no agota todos los bordes. En orden para $G$ a no ser una de Euler tour, no se podría, asimismo, que $G$ atraviesa una arista más de una vez?
Luego dice que "ya Hemos establecido que los vértices de un complejo ciclo tienen la propiedad de que en el grado($v$)=out-grado($v$). Por lo tanto, $G'=G-C$ también tienen esa propiedad."
¿Por qué se $G'=G-C$ ser un complejo ciclo, a pesar de $G$ no es necesariamente?
También, podría explicar por qué se sostiene que: "Si un componente conectado en un gráfico que tiene en grado($v$)=out-grado ($v$), a continuación, contiene al menos un ciclo de $C'$."
Finalmente, se podría explicar mí la contradicción?
EDIT: yo también quiero describir un algoritmo que se ejecuta en el tiempo $O(E)$ y encuentra una Euler tour de $G$, si es que existe. (Sugerencia: Combinación de borde de ciclos disjuntos.) Si aplicamos DFS, vamos a obtener un conjunto de ciclos formados por distintos conjuntos de aristas, derecho? Pero, ¿cómo podemos saber si se sostiene que en grado(v)=out-grado(v), para todos los vértices en $V$?
Tenemos que hacer algo como eso? algoritmo
