En cuanto a los ciclos, no me di cuenta pero hay un error.
Por dos cuestiones:
- En un ciclo no importa cuál es el primer vértice. Es decir es lo mismo el ciclo de longitud \( 3 \), \( a-b-c-a \), que \( b-c-a-b \), que \( c-a-b-c. \)
- Y a no ser que estemos considerando grafos dirigidos (donde tienen una orientación) tampoco importa el sentido en que se recorra, es lo mismo \( a-b-c-a \) que \( a-c-b-a \).
Para que se entienda bien: si el grafo fuera \( K_3 \), un triángulo, solo había un ciclo.
Entonces con estas consideraciones el número de ciclos de longitud \( i \) es:
\( \dfrac{1}{2i}A(n,i) \)
(se divide entre \( i \) porque cada posibilidad está contada tres veces dependiendo de que vértice pongamos de primero; y entre dos porque están contadas en dos sentidos de recorridos distintos).
Y el número total de ciclos sería:
\( \displaystyle\sum_{i=3}^n{}\dfrac{1}{2i}A(n,i) \)
Creo que es por convención, vi que hay dos formas de contar ciclos, importando el orden y el vertice principal o sin importar esto, y cuando no importa simplemente es contar subgrafos isomorfos
Aquí también me parece que tienes prejuicios; ¿has entendido como he contado los caminos de longitud uno?¿has entendido como he contado los de longitud dos?¿cuál es el problema entonces? Es como si te molestase que no hubiese una fórmula "uniforme" para los dos casos.
Por cierto que también podríamos añadir los caminos de longitud cero: serían tantos como vértices.
Explico mejor porque ni yo entendí lo que dije
Para el grafo bipartito \( K_1,n \) quiero contar la cantidad de caminos simples de longitud k, como tu bien dijiste hay dos casos
- Los que unen \( x_0 \) con cualquiera de \( B \)
Acá no hay necesidad de contar de longitud k ya que son de longitud 1, son n posibilidades
- Los que unen cualquiera de \( B \) con \( x_0 \), o después luego con otro diferente de B
Acá hay caminos de longitud 1 y de longitud 2, los de 1 es ir de un vertice de B hacia \( x_0 \) y listo y los otros ir de un vertice de B hacia \( x_0 \) y luego volver a otro de B diferente
Y lo que yo había llegado era
\( A(n,k+1)=\dfrac{n!}{(n-(k+1))!} \)
¿Que paso? que cuando yo decia, caminos de largo 1, es decir \( k=1 \) me daba \( n(n-1) \) pero si haces el conteo normal como tu hiciste, estos serian los caminos de largo 2
¿Que paso? pues creo que hice el conteo mal
y serian \( A(n,k) \) ¿Porque? cuando hice el conteo \( \left\{{{x_1,x_0}}\right\}...\left\{{{x_k,x_k+1}}\right\} \)
Para \( x_1 \) tenemos n posiblidades, para \( x_0 \) una sola, pues tenemos solo un vertice aislado, y aca fue el error mio, luego para \( x_k \) tenemos \( n-(k-1) \) y para \( x_k+1 \) tenemos \( n-((k+1)-1) \) y Yo dije, pues son
\( A(n,k+1)=\dfrac{n!}{(n-(k+1))!} \) , pero no, no vi que para el vertice aislado hay una posiblidad entonces serian
\( A(n,k)=\dfrac{n!}{(n-(k))!} \)*1
y ahora si hago k=1 da n, si hago k=2 da n(n-1)
Tengo otra confusión es cierto que para contar caminos de largo x necesito elegir x+1 vertices?
Si.
Saludos.
Con razón, tenia unos problemas pensando en eso
aveces pensaba que contar caminos de largo k eran elegir k vertices, y por eso me cuando me daban arreglos de i+1 pensaba que estaba mal, ya que decia que tenia que ordenar k vertices para un camino de longitud k pero no...
¡Gracias Luis!
