J'essaie de structurer un algorithme efficacegraphe non orienté, et arête e (u, v), et décide si l’arête appartient à un cycle du graphe, mais pas à tous les cycles! Mon approche consiste à supprimer le bord (u, v) du graphique et à exécuter BFS pour voir si v est toujours accessible depuis u. Si oui, alors le graphique d'origine a un cycle contenant e, sinon il n'y a pas de "t". Mais je ne suis pas sûr de savoir comment modifier l’algorithme pour qu’il décide si le bord n’appartient pas à tous les cycles du graphe.
Réponses:
1 pour la réponse № 1Un graphe non dirigé peut contenir une arête qui appartient à tous ses graphes de cycles uniquement si ce graphe a un seul cycle.
Voyons un exemple. Edge (2,3) appartient à deux cycles, mais vous pouvez toujours trouver un troisième cycle auquel un tel bord n’appartient pas.
Après avoir vérifié que le bord appartient àPour certains cycles, vous pouvez vérifier si c’est le seul cycle du graphique en supprimant cette arête et en vérifiant si le graphique réduit a des cycles. Merci à @nomanpouigt pour l'avoir signalé.