Version imprimable
Voulez-vous m'aider à résoudre cet exercice
On considère le graphe suivant :
1. Combien de cycles simples possède-t-il ?
2. Combien de chaines simples de longueur 5 possède-t-il ?
3. Dénombrez toutes les chaines entre les deux sommets 0 et 3
Pièce jointe 599875
:salut:
Nous ne sommes pas là pour faire tes exercices (cf. les règles). Par contre, si tu as des questions sur l'énoncé, sur la manière d'aborder la résolution, sur la correction d'une solution, n'hésite pas ;).
Pour trouver les chaines dans un gaphe, on utilise en général la puissance matricielle. ça donne toutes les chaines simples non simples et élémentaires et certaines chaines sont comptées plus qu'une fois en fait plusieurs chaines.
Si on veut des chaines élémentaires on peut utiliser un parcours en profondeur à partir d'un sommet donné mais là encore si je veux toutes les chaines on doit répéter l'opération à partir d'autres sommets là encore il y aura des répétitions.
avec un seul parcours, un cycle est compté plusieurs fois et les cycles qui sont donnés sont élémentaires alors qu'on veut des cycles simples.
Puis quand on effectue un parcours on dénombre les chaines et cycles. est ce qu'il y a une façon de donner le nombre de chaines simples et cycles sans dénombrer sachant qu'utiliser les puissances matricielles de la matrice d'adjacence n'est pas une solution
Bonjour :coucou:
Très beau pseudo.
Et tu sais ça comment, toi ? Commence par le faire. On verra après pour les commentaires. J'ai la solution sous les yeux. En même temps, c'est le tableur qui a fait les calculs. C'est peut-être ça, la solution : utiliser un tableur.Citation:
utiliser les puissances matricielles de la matrice d'adjacence n'est pas une solution
salut
voici un site (click ici) qui te permettra de comprendre ta demande
je t'extrait les deux information importante a exploité pour ta demande
reste plus qu'a travailler un peu ;)Citation:
Un cycle est une chaîne fermée dont toutes les arêtes sont distinctes
Une chaîne est fermée lorsque l'origine et l'extrémité de la chaîne sont confondues.
