¿Por qué no hay un camino circular en todos los grafos no dirigidos?
Por ejemplo: Dados 2 nodos a y b y una arista no dirigida que los conecta
Existe un gráfico de ciclo a-b-a
Además, ¿cuál es el exacto definición de trayectoria circular?
Respuesta
¿Demasiados anuncios?
AVISEK SHARMA
Puntos
550
Camino: Una cadena de vértices y aristas alternas $v_1e_1v_2e_2\dots v_{n-1}e_{n-1}v_n$ , ( $n\geq 2$ ) se dice que es un camino si no se repite ningún vértice.
Camino circular: Una cadena de aristas de vértices alternados $v_1e_1v_2e_2\dots v_{n-1}e_{n-1}v_n$ , ( $n\geq 2$ ) se dice que es una trayectoria circular si no se repite ningún vértice a excepción de $v_1=v_n$ y sin repetición de bordes.
Ahora bien, si el gráfico tiene aristas paralelas $e_1$ y $e_2$ uniendo dos vértices $u$ y $v$ . Entonces $ue_1ve_2u$ es una trayectoria circular de tamaño $2$ . Pero en el caso del grafo simple, como no hay ninguna arista paralela, no hay ningún camino circular de tamaño $2$ . Porque en este caso los bordes se repetirán.
Ahora bien, la mayoría de los libros sólo se refieren a gráficos simples, por lo que no incluyen la parte de "no repetición de aristas". Pero para un gráfico no simple es necesario mencionarlo. De lo contrario, para $n=2$ se produce una ambigüedad lo que usted ha mencionado.
En tu pregunta no has dicho que el gráfico sea simple o no. Pero como no has mencionado la arista, entonces $ab$ y $ba$ son los mismos bordes. Así que aquí la arista se repite, por lo que $aba$ no es una trayectoria circular.
