He encontrado definiciones de árboles como "grafos no dirigidos que están conectados y no tienen ciclos" en múltiples libros de texto y referencias. Sin embargo, ninguno de ellos parece ofrecer una comprensión clara de la noción de ciclos que subyace a esta definición.
¿Cuál es la interpretación correcta de los ciclos en estas definiciones? ¿No hay vértices repetidos? ¿No hay aristas repetidas? ¿Ciclos simples?
Un paseo cerrado es un conjunto de vértices $(v_1,v_2,...,v_n,v_1)$ tal que $v_i$ es adyacente a $v_{i+1}$ para $1 \leq i \leq n-1$ y $v_n$ es adyacente a $v_1$ .
Las aristas de un paseo cerrado son las aristas $v_iv_{i+1}$ para $1 \leq i \leq n-1$ y el borde $v_nv_1$ .
Un ciclo es un paseo cerrado sin vértices repetidos, además de $v_1$ y sin bordes repetidos. Esta es la definición que desea. Si permites aristas repetidas en la definición de ciclos para un árbol, entonces el paseo cerrado $(v_1, v_2, v_1)$ constituiría un ciclo, pero éste estaría contenido en el grafo de cualquier árbol con al menos dos vértices.
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.
