| dbo:abstract
|
- 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? A problémát (管梅谷)(wd) 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. 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. (hu)
- 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? A problémát (管梅谷)(wd) 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. 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. (hu)
|
