Kínaipostás-probléma
A kínaipostás-probléma, más néven útbejárási probléma a gráfelmélet egyik kérdése: legkevesebb hány élismétléssel lehet bejárni egy gráfot úgy, hogy minden élen áthaladjunk legalább egyszer?[1]
A problémát Kuan Mej-ku () (管梅谷) vetette fel egy 1962-ben megjelent cikkében, amely a postások útvonalának optimizálásáról szólt. Ennek alapján az Amerikai Egyesült Államok Szabványügyi Hivatalánál dolgozó Alan J. Goldman javasolta a kínaipostás-probléma elnevezést.[2]
Ha létezik a gráfban Euler-kör, akkor az egyben egy optimális kínaipostás-útvonal. A postás tényleges útvonalán a többször bejárt éleket megfelelő multiplicitású többszörös éleknek tekintve olyan gráfot kapunk, aminek van Euler-köre. Semelyik élen nem érdemes kettőnél többször átmenni. A feladat azzal ekvivalens, hogy minimum hány él megduplázásával tehető olyanná a gráf, hogy legyen benne Euler-kör, azaz hogy minden csúcs fokszáma páros legyen. (Az összefüggőséget eleve feltételezzük.) Erre van jól működő algoritmus.[3][4]
Jegyzetek
szerkesztés- ↑ Chinese Postman Problem. mathworld.wolfram.com (Hozzáférés: 2020. január 16.)
- ↑ Chinese postman problem. xlinux.nist.gov (Hozzáférés: 2020. január 16.)
- ↑ Útbejárási probléma. www.tankonyvtar.hu (Hozzáférés: 2020. január 16.)
- ↑ Kínai postás probléma. www.math.u-szeged.hu (Hozzáférés: 2020. január 16.)
Kapcsolódó szócikkek
szerkesztés
|
Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle! |