Conteo de ciclos

Re: Conteo de ciclos

de Claudio Qureshi -
Número de respuestas: 0

Si, exacto. Entre tres vértices adyacentes se pueden definir 6 ciclos diferentes de longitud 3.

Hay otro tipo de problema en que dado un grafo G se pide hallar todos los subgrafos isomorfos a C3 (otra forma de preguntar lo mismo es pedir que cuenten cuantas copias de C3 hay en G). En ese caso habría que contar todos los ciclos de longitud 3 que tiene el grafo sin importar el punto inicial ni el sentido (aqui dados tres vértices adyacentes, el subgrafo inducido por esos vértices sería un subgrafo isomorfo a C3). Para pasar de un problema al otro simplemente hay que multiplicar el resultado por 6.