¿Cómo encontrar el camino euleriano en el gráfico dado?

He trazado el siguiente gráfico (fue dado por la matriz de adyacencia):

ingrese la descripción de la imagen aquí

Y tengo que encontrar el camino euleriano allí y enfatizar esto.

Estoy preocupado porque mi libro dice que la acción posterior depende del gráfico inicial. Por ejemplo, si tenemos contador o ciclo en el gráfico inicial, podemos comenzar en cualquier vértice. Si el grafo inicial tiene una cadena debemos partir de cualquier vértice cuya potencia sea impar. Si el grafo inicial tiene una cadena, un vértice inicial depende del grado del vértice y así sucesivamente.

Pero, ¿cómo puedo saber si hay una cadena, un contador o un ciclo en un gráfico y cómo debo proceder después?

Respuestas (1)

Deberías empezar mirando los grados de los vértices, y eso te dirá si puedes esperar encontrar:

  • un recorrido euleriano (algunos dicen "ciclo euleriano") que comienza y termina en el mismo vértice,
  • o un camino euleriano (algunos dicen "camino euleriano") que comienza en un vértice y termina en otro,
  • o ninguno

La idea es que en un grafo dirigido, la mayoría de las veces, un Euleriano cualquiera entrará en un vértice y saldrá de él el mismo número de veces. Entonces, el grado de entrada y el de salida deben ser iguales. (La excepción es el comienzo o el final de un paseo euleriano, donde pueden estar fuera por uno).

Aquí, la mayoría de los vértices tienen el mismo grado de entrada y salida, lo cual es prometedor, pero el vértice 4 tiene dos aristas que salen y solo una que entra, y vértice 6 tiene dos aristas que entran y solo una que sale.

Esto significa que para equilibrar los bordes que entran y salen de los vértices, debe comenzar en el vértice 4 y termina en el vértice 6 .

Ajá. Entonces, hasta donde puedo juzgar, aquí tenemos la cadena de Euler (como lo indican los libros rusos), pero ¿hay un algoritmo para encontrar una cadena? Revisé algunos libros pero no me aclararon las cosas :/
El algoritmo básico consta de dos pasos. (1) En primer lugar, busque un paseo que vaya desde 4 a 6 , entonces (2) por cada arista no utilizada fuera de un vértice v que ya ha visitado, extienda su caminata para tomar ese borde y luego regrese a v .
Para un gráfico pequeño como este, deberías poder dibujar algo.
¿Cómo encontrar el camino euleriano en el gráfico dado?
RespuestasAquíPolítica de privacidad1y, 1v