Property |
Value |
dbo:abstract
|
- En théorie des graphes et en algorithmique, le problème du postier chinois, ou problème du postier (en anglais route inspection problem) consiste à trouver un plus court chemin dans un graphe connexe non orienté qui passe au moins une fois par chaque arête et revient à son point de départ. Le nom du problème vient du fait qu'il a été étudié par le mathématicien chinois Meigu Guan en 1962, et qu'il modélise la tournée d'un facteur devant effectuer le plus efficacement possible sa tournée en passant au moins une fois par chaque rue de son secteur. Le problème peut être réduit à la recherche d'un couplage maximal de poids minimum, et ainsi être résolu en temps polynomial dans le cas général. (fr)
- En théorie des graphes et en algorithmique, le problème du postier chinois, ou problème du postier (en anglais route inspection problem) consiste à trouver un plus court chemin dans un graphe connexe non orienté qui passe au moins une fois par chaque arête et revient à son point de départ. Le nom du problème vient du fait qu'il a été étudié par le mathématicien chinois Meigu Guan en 1962, et qu'il modélise la tournée d'un facteur devant effectuer le plus efficacement possible sa tournée en passant au moins une fois par chaque rue de son secteur. Le problème peut être réduit à la recherche d'un couplage maximal de poids minimum, et ainsi être résolu en temps polynomial dans le cas général. (fr)
|
dbo:thumbnail
| |
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 4329 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
prop-fr:wikiPageUsesTemplate
| |
dct:subject
| |
rdfs:comment
|
- En théorie des graphes et en algorithmique, le problème du postier chinois, ou problème du postier (en anglais route inspection problem) consiste à trouver un plus court chemin dans un graphe connexe non orienté qui passe au moins une fois par chaque arête et revient à son point de départ. Le nom du problème vient du fait qu'il a été étudié par le mathématicien chinois Meigu Guan en 1962, et qu'il modélise la tournée d'un facteur devant effectuer le plus efficacement possible sa tournée en passant au moins une fois par chaque rue de son secteur. (fr)
- En théorie des graphes et en algorithmique, le problème du postier chinois, ou problème du postier (en anglais route inspection problem) consiste à trouver un plus court chemin dans un graphe connexe non orienté qui passe au moins une fois par chaque arête et revient à son point de départ. Le nom du problème vient du fait qu'il a été étudié par le mathématicien chinois Meigu Guan en 1962, et qu'il modélise la tournée d'un facteur devant effectuer le plus efficacement possible sa tournée en passant au moins une fois par chaque rue de son secteur. (fr)
|
rdfs:label
|
- Briefträgerproblem (de)
- Bài toán người đưa thư Trung Hoa (vi)
- Problema del postino cinese (it)
- Problème du postier chinois (fr)
- Задача инспекции дорог (ru)
- Задача листоноші (uk)
- 邮递员问题 (zh)
- Briefträgerproblem (de)
- Bài toán người đưa thư Trung Hoa (vi)
- Problema del postino cinese (it)
- Problème du postier chinois (fr)
- Задача инспекции дорог (ru)
- Задача листоноші (uk)
- 邮递员问题 (zh)
|
rdfs:seeAlso
| |
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:depiction
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageRedirects
of | |
is dbo:wikiPageWikiLink
of | |
is oa:hasTarget
of | |
is foaf:primaryTopic
of | |