Ciclos de un Grafo no Dirigido

Ciclos de un Grafo no Dirigido

de Agustín Torres Mari -
Número de respuestas: 3

Buenas, estaba leyendo el libro del curso y me surgió una duda que viene relacionada al tercer practico del curso.

Si consideramos un grafo no dirigido el cual está compuesto por unicamente dos nodos, los cuales estan unidos por una arista, ¿Se considera como un ciclo?

Mi duda es más que nada porque para determinar si hay un ciclo en un grafo no dirigido bastaría con ver si el conjunto de aristas es no vacío, y si la consigna es devolverlo, bastaría con imprimir dos nodos, lo cual se me hace extraño.

Saludos,

Agustín

En respuesta a Agustín Torres Mari

Re: Ciclos de un Grafo no Dirigido

de Hernan David Beder Rostagnol -
En la pagina 76 del libro dice que un ciclo es un camino v1, v2, ..., vk-1, vk donde k > 2 y todos los primeros k-1 nodos son diferentes y que v1 = vk. En un grafo como el que decis hay k = 2 asi que no es un ciclo.
En respuesta a Hernan David Beder Rostagnol

Re: Ciclos de un Grafo no Dirigido

de Facundo Benavides -
hola hernan, como le comentaba a agustín, la definición si lo permite pero evidentemente no es lo que se buscaba.
para el ejemplo que colocás, si hay 2 nodos distintos y un camino que retorna al primero (ciclo), k=3, con v1==v3 y k-1=2 nodos distintos.
saludos
En respuesta a Agustín Torres Mari

Re: Ciclos de un Grafo no Dirigido

de Facundo Benavides -
hola agustín,
bingo. aunque según la definición del libro la respuesta sería si. la copio para evitarnos enriedos.
"A cycle is a path v1, v2, . . ., vk−1, vk in which k>2, the first k−1 nodes are all distinct, and v1 = vk"
luego, al considerar la definición de árbol (grafo conexo acíclico) vemos que no es lo que se busca. es decir, la definición lo admite tal cual está pero no sirve (errata?) porque básicamente contraviene (a continuación) una definición igualmente importante como la de árbol.
ergo, la respuesta final es no.
saludos