Kínaipostás-probléma

A Wikipédiából, a szabad enciklopédiából

A kínaipostás-probléma (esetleg „kínai postás”-probléma) a gráfelmélet egyik kérdése: legfeljebb hány élismétléssel lehet bejárni egy gráfot úgy, hogy minden élen áthaladjunk legalább egyszer?

A problémával akkor kezdtek el foglalkozni a kínaiak, amikor megpróbáltak a postások számára minél rövidebb útvonalat kijelölni úgy, hogy mindenkinek ki tudják kézbesíteni a levelét, vagyis olyan útvonalakat kerestek, ahol a postás minden úton áthalad legalább egyszer, de a lehető legkevesebbszer halad át olyanon, amelyen már végigment egyszer.

Észrevétel:

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.

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]