Séparer deux sommets s et t graphe non orienté (non pondéré)
Fermé
randomperson
-
21 déc. 2020 à 17:33
yg_be Messages postés 23405 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 20 décembre 2024 - 22 déc. 2020 à 18:22
yg_be Messages postés 23405 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 20 décembre 2024 - 22 déc. 2020 à 18:22
A voir également:
- Séparer deux sommets s et t graphe non orienté (non pondéré)
- Moyenne pondéré - Guide
- Séparer pdf - Guide
- Deux ecran pc - Guide
- Itinéraire google map entre deux adresses - Guide
- Deux comptes whatsapp - Guide
4 réponses
yg_be
Messages postés
23405
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
20 décembre 2024
Ambassadeur
1 557
21 déc. 2020 à 18:33
21 déc. 2020 à 18:33
bonjour,
as-tu déjà choisi une représentation du graphe?
qu'as-tu essayé?
pour que ton projet reste personnel, ceci te guidera sans doute: https://www.commentcamarche.net/infos/25899-demander-de-l-aide-pour-vos-exercices-sur-ccm/
as-tu déjà choisi une représentation du graphe?
qu'as-tu essayé?
pour que ton projet reste personnel, ceci te guidera sans doute: https://www.commentcamarche.net/infos/25899-demander-de-l-aide-pour-vos-exercices-sur-ccm/
pour le moment j'avais juste un algo et un micro bout de code
je vais essayer d'être plus clair mais ce n'est pas mon point fort '^^
j'ai un graph, avec un nombre de vertex et d'edges variable, qui est non pondéré et non orienté. chaque vertex porte un numéro
j'essaie, de quelque manière que ce soit de séparer deux vertex donnés s et t. Mon problème, c'est que j'avais pensé à un algo qui fonctionne en récursive et qui n'est donc pas assez performant.
j'avais également trouvé l'algorithme de stoer wagner, mais celui-ci renvoie le poids de la coupe minimale, or moi je souhaiterais connaître l'ensemble d'arêtes à couper et pas leur poids
je ne sais pas si c'est plus clair?
je vais essayer d'être plus clair mais ce n'est pas mon point fort '^^
j'ai un graph, avec un nombre de vertex et d'edges variable, qui est non pondéré et non orienté. chaque vertex porte un numéro
j'essaie, de quelque manière que ce soit de séparer deux vertex donnés s et t. Mon problème, c'est que j'avais pensé à un algo qui fonctionne en récursive et qui n'est donc pas assez performant.
j'avais également trouvé l'algorithme de stoer wagner, mais celui-ci renvoie le poids de la coupe minimale, or moi je souhaiterais connaître l'ensemble d'arêtes à couper et pas leur poids
je ne sais pas si c'est plus clair?
yg_be
Messages postés
23405
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
20 décembre 2024
1 557
21 déc. 2020 à 20:24
21 déc. 2020 à 20:24
"de quelque manière que ce soit", es-tu certain? n'est-ce pas alors très simple?
pourquoi ne donnes-tu pas un exemple de graphe, avec le résultat attendu?
pas ailleurs, quand tu écris "l'algorithme de stoer wagner renvoie le poids de la coupe minimal", je pense que tu confonds "algorithme" avec une fonction toute faite que tu envisages d'utiliser.
pourquoi ne donnes-tu pas un exemple de graphe, avec le résultat attendu?
pas ailleurs, quand tu écris "l'algorithme de stoer wagner renvoie le poids de la coupe minimal", je pense que tu confonds "algorithme" avec une fonction toute faite que tu envisages d'utiliser.
"n'est-ce pas alors très simple?" -> cet algo doit fonctionner dans n'importe quel cas de figure qui respecte les contraintes que j'ai dites plus haut (graphe non orienté non pondéré en 2d)
"pourquoi ne donnes-tu pas un exemple de graphe, avec le résultat attendu?"
https://rperrot.developpez.com/articles/algo/theorie/graphes/images/graphe.jpg
en prenant par exemple ce graphe tout bête (attention je voudrais pouvoir aller jusqu'à un très grand nombre de vertex si possible)
- on voudrait séparer la source 1 et la target 2 en coupant le minimum d'arêtes possible
- on a une liste de toutes les arêtes du graphe (1-5, 5-3, 4-2 etc)
-on peut couper 2 arêtes par exemple, l'arête 1-5 et l'arête 1-4. Ainsi, les vertex 1 et 2 seront séparés (plus aucune chaîne possible entre les deux)
et encore merci de prendre le temps de me répondre :)
"pourquoi ne donnes-tu pas un exemple de graphe, avec le résultat attendu?"
https://rperrot.developpez.com/articles/algo/theorie/graphes/images/graphe.jpg
en prenant par exemple ce graphe tout bête (attention je voudrais pouvoir aller jusqu'à un très grand nombre de vertex si possible)
- on voudrait séparer la source 1 et la target 2 en coupant le minimum d'arêtes possible
- on a une liste de toutes les arêtes du graphe (1-5, 5-3, 4-2 etc)
-on peut couper 2 arêtes par exemple, l'arête 1-5 et l'arête 1-4. Ainsi, les vertex 1 et 2 seront séparés (plus aucune chaîne possible entre les deux)
et encore merci de prendre le temps de me répondre :)
yg_be
Messages postés
23405
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
20 décembre 2024
1 557
21 déc. 2020 à 21:59
21 déc. 2020 à 21:59
tout à coup tu écris "en coupant le minimum d'arêtes possible", au lieu de "de quelque manière que ce soit": tu as choisi de ne pas préciser cela plus tôt. tu gardes encore beaucoup d'informations cachées?
quel est ton réel énoncé?
quand tu écris "l'algorithme de stoer wagner renvoie le poids de la coupe minimal", je pense que tu confonds "algorithme" avec une fonction toute faite que tu envisages d'utiliser. as-tu analysé et compris l'algorithme?
quel est ton réel énoncé?
quand tu écris "l'algorithme de stoer wagner renvoie le poids de la coupe minimal", je pense que tu confonds "algorithme" avec une fonction toute faite que tu envisages d'utiliser. as-tu analysé et compris l'algorithme?
yg_be
Messages postés
23405
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
20 décembre 2024
1 557
22 déc. 2020 à 18:22
22 déc. 2020 à 18:22
un exemple de code (les vertex sont numérotés de 0 à 5):
import igraph
def stmincut(g,s,t):
stmc=igraph.Graph.st_mincut(g,s,t)
return(stmc.partition)
nvx=6
gr = igraph.Graph()
gr.add_vertices(nvx)
gr.add_edges([(0,3), (0,4),(3,4), (2,3),(1,5),(3,5),(1,3),(2,4)])
print(gr)
print(stmincut(gr,0,1))
non y a pas d'infos cachées mdr
je croyais m'être exprimé(e) clairement. Quand je disais "de quelque manière que ce soit", je voulais dire, pour aterrir à ce résultat.
Je n'ai pas d'énoncé, puisque c'est pour un projet comme je l'ai dit plus haut.
Oui je me suis mal exprimée, il s'agit bien d'un algorithme (stoer et wagner), avec comme output le poids de la coupe minimale. Je pense avoir compris l'algorithme
je croyais m'être exprimé(e) clairement. Quand je disais "de quelque manière que ce soit", je voulais dire, pour aterrir à ce résultat.
Je n'ai pas d'énoncé, puisque c'est pour un projet comme je l'ai dit plus haut.
Oui je me suis mal exprimée, il s'agit bien d'un algorithme (stoer et wagner), avec comme output le poids de la coupe minimale. Je pense avoir compris l'algorithme
yg_be
Messages postés
23405
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
20 décembre 2024
1 557
21 déc. 2020 à 23:05
21 déc. 2020 à 23:05
tu n'as mentionné le résultat attendu qu'en #7.
de ce que je lis, l'algorithme de stoer et wagner détermine la coupure optimale. si tu programmes cet algorithme, tu peux choisir l'output du programme.
de ce que je lis, l'algorithme de stoer et wagner détermine la coupure optimale. si tu programmes cet algorithme, tu peux choisir l'output du programme.
yg_be
Messages postés
23405
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
20 décembre 2024
1 557
>
yg_be
Messages postés
23405
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
20 décembre 2024
22 déc. 2020 à 11:43
22 déc. 2020 à 11:43
j'ai trouvé que ceci décrivait très clairement l'algorithme:
https://basics.sjtu.edu.cn/~dominik/teaching/2016-cs214/presentation-slides/2016-12-06-StoerWagner-BigNews.pdf
https://basics.sjtu.edu.cn/~dominik/teaching/2016-cs214/presentation-slides/2016-12-06-StoerWagner-BigNews.pdf
21 déc. 2020 à 19:45
oui c'est un graphe non pondéré et non orienté
https://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/6n-graf.svg/220px-6n-graf.svg.png
il ressemblera à ça par exemple
j'ai essayé avec un algo en récursive (DFS), mais la complexité temporelle est exponentielle, il n'est donc pas assez performant
21 déc. 2020 à 19:50
donne un exemple complet qui fonctionne, avec des données.
21 déc. 2020 à 19:51
maintenant, tu écris "il n'est donc pas assez performant"
penses-tu être clair?