Wikipédia

« Problème d'affectation » : différence entre les versions

Navigation interactive dans l’historique
← Modification précédenteModification suivante →
Contenu supprimé Contenu ajouté
VisuelWikicode
HerculeBot (discuter | contributions)
Robots
2 914 110 modifications
[Bot] Correction de cacographie. remplacement de Université Libre de Bruxelles par Université libre de Bruxelles
correction de N a Z (sinon solution triviale pour minimiser les poids : ne pas prendre d'arretes).
Ligne 5 :
== Définition formelle ==
Le problème peut être énoncé de la manière suivante<ref>{{lien web|url=http://homepages.ulb.ac.be/~bfortz/ro.pdf|titre=Recherche opérationnelle et applications|site=[[Université libre de Bruxelles]]|auteur=Bernard Fortz|année=2012}}.</ref>.
Étant donné un graphe biparti <math>G =((S,T),E)</math>, avec une fonction de poids sur les arêtes : <math>c:E \rightarrow \mathbb{NZ}</math>, trouver un [[couplage (théorie des graphes)|couplage]], c'est-à-dire sous-ensemble d'arêtes <math>F\subset E</math> tel que les arêtes ne partagent pas de sommet, en minimisant la somme des poids des arêtes de <math>F</math>, c'est-à-dire: <math>\sum_{e\in F} c(e)</math>.
 
== Algorithmes ==
Ce document provient de « https://fr.wikipedia.org/wiki/Problème_d%27affectation ».