Mettons on a (A4,B4) = ({s,a,b,c,d},{t}) = 24 , c'est plus grand que 23 donc on ne le prend pas comme certificat d'optimalité ? Est-ce que on peut appliquer la notion de réseau de flots à la segmentation d'image 2D ?
Bonsoir, La coupe ({s,a,b,c,d},{t}) est réalisable et indique que tout flot à une valeur inférieure à 24. Effectivement cette coupe ne fournit pas le certificat d'optimalité (la preuve) de la valeur 23. Mais elle donne une garantie, une borne supérieure. Oui je pense que les algos de flots max jouent un rôle important en traitement d'images et notamment pour la segmentation mais je ne pas bien ces problèmes, je ne pourrai pas te renseigner davantage.
Bonjour, existe t'il un moyen de prouver que la coupe trouvée est bien celle de capacité minimale ? Ça semble évident ici mais cela semble plus dur de le "voir" si le graphe est plus grand
Oui il te suffit d'exhiber un flot réalisable de la même valeur. Il te suffit de vérifier la faisabilité du flot et de la coupe. Si ils ont la même valeur; tu prouves ainsi l'optimalité des deux. Cela vient du fait que la valeur de n'importe quel flot réalisable est une borne inférieure de la capacité de n'importe quelle coupe. Tu fais ainsi une preuve en exploitant la relation du dualité entre ces deux problèmes. Je dois expliquer ça davantage ici si tu veux jeter un oeil: ua-cam.com/video/G5H6M3fMVB0/v-deo.html
Bonsoir, J'ai simplement pris plusieurs exemples. La capacité de toute coupe dont une borne supérieure de tout flot. Si tu trouves une coupe dont la capacité est égale à la valeur d'un flot réalisable, c'est que celui-çi est donc maximum. Pour avoir une méthode pour trouver une telle coupe minimale. Tu peux utiliser le graphe résiduel de la dernière itération de l'algorithme de Ford et Fulkerson. Dans ce dernier graphe, tu marques les sommets atteignables depuis la source s et tu obtiens la partition, la coupe prouvant l'optimalité du flot. Je dois l'expliquer ici: ua-cam.com/video/G5H6M3fMVB0/v-deo.html J'espère que ça t'aide !
je révise pour mes rattrapages et vous êtes très clair dans vos explications merci beaucoup :)
Super. Bon courage pour tes examens !
merci pour vos vidéos
Tres bonne utilisation du theoreme max-flow min-cut
Merci beaucoup monsieur vous m'avez énormément aidée
Bon courage à toi !
Merci beaucoup monsieur 🙏🏼
merci
Mettons on a (A4,B4) = ({s,a,b,c,d},{t}) = 24 , c'est plus grand que 23 donc on ne le prend pas comme certificat d'optimalité ? Est-ce que on peut appliquer la notion de réseau de flots à la segmentation d'image 2D ?
Bonsoir,
La coupe ({s,a,b,c,d},{t}) est réalisable et indique que tout flot à une valeur inférieure à 24. Effectivement cette coupe ne fournit pas le certificat d'optimalité (la preuve) de la valeur 23. Mais elle donne une garantie, une borne supérieure.
Oui je pense que les algos de flots max jouent un rôle important en traitement d'images et notamment pour la segmentation mais je ne pas bien ces problèmes, je ne pourrai pas te renseigner davantage.
@@rechercheoperationnelle8907 D'accord, merci pour votre réponse, en tout cas votre vidéo est bien 👍
Mercii beaucoup pour cette explication
Merci de ton retour :) !
Bonjour, existe t'il un moyen de prouver que la coupe trouvée est bien celle de capacité minimale ? Ça semble évident ici mais cela semble plus dur de le "voir" si le graphe est plus grand
Oui il te suffit d'exhiber un flot réalisable de la même valeur. Il te suffit de vérifier la faisabilité du flot et de la coupe. Si ils ont la même valeur; tu prouves ainsi l'optimalité des deux. Cela vient du fait que la valeur de n'importe quel flot réalisable est une borne inférieure de la capacité de n'importe quelle coupe. Tu fais ainsi une preuve en exploitant la relation du dualité entre ces deux problèmes.
Je dois expliquer ça davantage ici si tu veux jeter un oeil: ua-cam.com/video/G5H6M3fMVB0/v-deo.html
Merci ♥️
Si tu veux un autre exemple plus complet pour réviser: ua-cam.com/video/G5H6M3fMVB0/v-deo.html
Comment vous avez choisi de prendre ces deux coupes exactes?
Bonsoir,
J'ai simplement pris plusieurs exemples. La capacité de toute coupe dont une borne supérieure de tout flot. Si tu trouves une coupe dont la capacité est égale à la valeur d'un flot réalisable, c'est que celui-çi est donc maximum.
Pour avoir une méthode pour trouver une telle coupe minimale. Tu peux utiliser le graphe résiduel de la dernière itération de l'algorithme de Ford et Fulkerson. Dans ce dernier graphe, tu marques les sommets atteignables depuis la source s et tu obtiens la partition, la coupe prouvant l'optimalité du flot. Je dois l'expliquer ici: ua-cam.com/video/G5H6M3fMVB0/v-deo.html
J'espère que ça t'aide !
J'ai besoin de cours '' formulation arc chemins et flots de plusieurs produits''
Zaim hbb
Merci