Graphe

[ghghgh]

Bonjour,
quelqu'un pourrait me passer un pseudo-code, sur comment détecter un (plusieurs) isthmes dans un graphe non-orienté

une des conditions d'une arrête/isthme est :
"une arrête est un isthme d'un graphe si, et seulement si, elle n'est dans contenue dans aucun cycle", donc pour trouver les isthmes, on peut donc faire ça à coup de DFS pour détecter les cycles.
Mais, si je pourrais avoir des détails sur quel structure, comment faire récursivement, pour marquer/stocker ? les arrêtes appartenant aux cycles, puis continuer le parcours de graphe afin de détecter les autres cycles, les enregistrer/ou marquer, puis finalement, énumérer tous les isthmes du graphe.

Voilà, voilà... merci pour votre aide :D

[bruce.ml]

Salut,

si tu as un algorithme qui detecte les cycles c'est assez simple, tu enregistres toutes les arrêtes qui sont dans des cycles, et celles que tu cherches sont celles qui n'ont pas été enregistrées. Je suis pas certain de bien saisir la question ...

[ghghgh]

oui, c'est ce que je veux, mais j'ai du mal à MARQUER les arrêtes qui sont contenues dans le cycle... le détecter c'est facile, mais connaître toutes les arrêtes dedans, tu ferais comment ?
peux-tu me montrer en pseudo-code ou en caml ? :)

genre nbNoeuds = 12, nbArcs = 15;

noeudDepart l noeudArrivee
1 l 2
1 l 3
2 l 4
2 l 5
3 l 5
4 l 6
6 l 7
6 l 10
6 l 11
7 l 8
8 l 9
8 l 10
9 l 10
10 l 11
11 l 12

en sortie tu as
nbIsthmes = 3
noeudDebut l noeudFin (de l'arrête)
2 l 4
4 l 6
11 l 12

voilà, en espérant avoir été suffisamment clair ?
:)
merci

[Patastronch]

Si t'as une clique avec les sommets avec , alors toutes les arretes | avec appartiennent a une clique. Pourquoi ? Parcequ'une corde reliant deux sommet appartenant a une clique appartien elle meme a une clique.

Le plus délicat dans ta facon de faire c'est pas comment marquer les sommets donc, mais savoir si énumérer toutes les cliques est serieusement réalisable en temps raisonnable pour des gros graphes (dans le pire cas , dans un graphe a n sommets il peut y avoir cliques). De plus je doute quil soit nécessaire d'énumérer toutes les cliques. Par exemple si A,B,C,D est une clique alors inutile d'énumérer les cliques incluses dans celle la comme A,B,C ou A,C,D ... puisque toutes leurs aretes auront deja ete marquées.

Pour accélerer la recherche tu peux deja te baser sur les degré des sommets. Si un sommet est de degré 1 alors son arrete est un ishtme. Par exemple tu prends tous les sommets de degré 1 et tu les suprime en suprimant leurs arretes (ce sont des isthmes) tu réitere le procédé jusqu'a qu'il y ai plus de sommet de degré 1. IL y a surment des possibilitées pour faire un prétraitement sur le graphe, mais j'ia pas le temps de me pencher la dessus pour le moment.
En d'autres termes => enumerer toutes les cliques, ca risque d'etre tres long ...
Du coup faut écrémer, et faire de l'énumération implicite si tu veux garder cette facon de faire.

[Patastronch]

Bon avec un peu de reflexion je me dit que la meilleur facon de faire c'est :

Pour chaque arrete N
Si N appartiens a une clique la marquer
Fin pour
Retourner les arretes non marquées.

Pour savoir si une arrete N=(s1,s2) appartiens a une clique c 'est pas compliqué. Une facon de faire serait de supprimer cette arrete et de regarder s'il existe un chemin entre s1 et s2.

Cette maniere de faire, dans le pire cas est en n² pour un graphe a n sommet. Ce qui est deja plus viable que la complexité précédente.