Briefträgerproblem
Modell der Graphentheorie / aus Wikipedia, der freien encyclopedia
Liebe Wikiwand-AI, fassen wir uns kurz, indem wir einfach diese Schlüsselfragen beantworten:
Können Sie die wichtigsten Fakten und Statistiken dazu auflisten Briefträgerproblem?
Fass diesen Artikel für einen 10-Jährigen zusammen
ZEIGE ALLE FRAGEN
Das Briefträgerproblem ist ein Modell aus der Graphentheorie, bei welchem man sich des übertragenen Bildes eines Postboten, der auf dem kürzesten Weg Briefe austrägt, bedient: Ein Postbote soll die Briefe (auf beiden Seiten der Straße gleichzeitig) in einem Straßennetzwerk (Stadt) zustellen.
Seinen englischen Namen (Chinese postman problem) erhielt das Briefträgerproblem durch Alan Goldman nach dem chinesischen Mathematiker Mei Ko Kwan, der das Problem erstmals 1962 untersuchte.[1] Eine Lösung wurde 1973 durch Jack Edmonds und Ellis L. Johnson angegeben.[2]