Sé que no tiene un circuito hamiltoniano porque los vértices c y f serán atravesados dos veces para volver a a. Sólo confirmo esto. Principalmente quiero saber si tengo la definición de los circuitos de Euler distintos en un grafo, y si el grafo de abajo es un ejemplo de esto, es decir, {a,b,c} y {f,g,h}, siendo los 2 circuitos de Euler distintos.
Un circuito de Euler, por definición, atraviesa cada borde del gráfico exactamente una vez, por lo que ninguna $\langle a,b,c\rangle$ ni $\langle d,e,f\rangle$ es un circuito de Euler. A partir de $a$ y contando dos circuitos como el mismo si uno es simplemente la inversión del otro, obtengo los siguientes cuatro circuitos de Euler distintos:
$$\begin{align*} &a,c,d,f,g,h,f,e,c,b\\ &a,c,d,f,h,g,f,e,c,b\\ &a,c,e,f,g,h,f,d,c,b\\ &a,c,e,f,h,g,f,d,c,b \end{align*}$$
Tienes razón en cuanto a la falta de un circuito Hamilton en este gráfico y la razón de ello.
Como bien dices, el gráfico no tiene Ciclo Hamiltoniano, ya que tiene un vértice de corte (en realidad tiene dos, a saber $c$ y $f$ ).
En cuanto al número de circuitos eulerianos distintos, hay más de dos si se toma la definición de distinto como
Dos circuitos eulerianos son distintos, si no son reversos exactos el uno del otro.
En este caso, los tres circuitos
$$(a,c,d,f,g,h,f,e,c,b,a)$$ $$(a,c,d,f,h,g,f,e,c,b,a)$$ $$(a,c,e,f,g,h,f,d,c,b,a)$$
son ejemplos de circuitos eulerianos distintos.
Como se indica en la respuesta de Brian, hay exactamente 4 ciclos eulerianos distintos, a saber
$$a,c,d,f,g,h,f,e,c,b$$ $$a,c,d,f,h,g,f,e,c,b$$ $$a,c,e,f,g,h,f,d,c,b$$ $$a,c,e,f,h,g,f,d,c,b$$
Para contarlas, y asegurarse de que no hay más de 4, mira el número de veces que el paseo se "cruza". Como sólo hay dos vértices ( $c$ y $f$ ) donde puede producirse dicho cruce, el número de cruces puede ser 0,1 o 2. Sólo hay un paseo sin cruce, a saber $$a,c,d,f,g,h,f,e,c,b$$
También hay un único paseo con dos cruces, a saber $$a,c,e,f,g,h,f,d,c,b$$
y hay dos paseos con un solo cruce, el que tiene un cruce en $c$ $$a,c,e,f,h,g,f,d,c,b$$
y el que tiene un cruce en $f$ $$a,c,d,f,h,g,f,e,c,b.$$
Para aclarar las afirmaciones anteriores, dos circuitos eulerianos son distintos si no son inversos el uno del otro y no son desplazamientos cíclicos entre sí. Para ver por qué es necesaria la restricción adicional, consideremos dos circuitos eularianos del gráfico anterior:
c, a, b, c, e, f, g, h, f, d
c, e, f, g, h, f, d, c, a, b
y observe que estos Circuitos parten del mismo vértice y no son inversos el uno del otro. Sin embargo, no son distintos, porque el segundo circuito es un desplazamiento de 3 letras del primero.
En la práctica, la forma más fácil de contar los circuitos eularianos distintos es encontrar un vértice de grado 2 y contar todos los circuitos eularianos que parten en una sola dirección, lo que da como resultado un recuento de 4 para el gráfico anterior. Sin embargo, cuando no existe tal vértice, hay que tener cuidado para evitar volver a contar el mismo circuito.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
