Séparer deux sommets s et t graphe non orienté (non pondéré)

randomperson -
yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention - 22 déc. 2020 à 18:22

Bonjour,

Pour un projet personnel, je souhaiterais savoir s'il existait un moyen de séparer deux sommets d'un graphe non pondéré non orienté.

En cherchant sur internet, j'ai trouvé plusieurs algorithmes qui ne me conviennent pas car j'aimerais savoir précisément quelles arêtes couper (elles porteront des noms préalablement définis)

Les algorithmes type Karger (probabilistes) ne sont pas suffisament fiables.

En espérant pouvoir trouver de l'aide ici!

Merci beaucoup d'avance!

Afficher la suite

A voir également:

Séparer deux sommets s et t graphe non orienté (non pondéré)
Deux ecran pc - Guide
Comment faire deux colonnes sur word - Guide
Séparer pdf - Guide
Nombre de jours entre deux dates excel - Guide
Moyenne pondéré - Guide

4 réponses

Réponse 1 / 4

yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention Ambassadeur 1 584

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/

randomperson

bonjour,
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

yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention 1 584 > randomperson

montre-nous le code que tu as essayé, cela permettra peut-être de comprendre ce que tu essaies de réaliser.
donne un exemple complet qui fonctionne, avec des données.

yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention 1 584 > yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention

au départ, tu écris "algorithmes qui ne me conviennent pas car j'aimerais savoir précisément quelles arêtes couper"
maintenant, tu écris "il n'est donc pas assez performant"

penses-tu être clair?

Réponse 2 / 4

randomperson

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?

yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention 1 584

"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.

Réponse 3 / 4

randomperson

"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 :)

yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention 1 584

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?

yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention 1 584

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))

Réponse 4 / 4

randomperson

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

yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention 1 584

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.

yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention 1 584 > yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention

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

Discussions similaires

Supprimer conversation messenger pour tout le monde

les 2 petits points sur le e ou sur le i

Découvrez pourquoi mes SMS affichent deux 'check' !

2 orientations de page dans un meme doc word

Votre réponse

Discussions similaires