Kínaipostás-probléma

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

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 (管梅谷)(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.[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]

  1. Chinese Postman Problem. mathworld.wolfram.com (Hozzáférés: 2020. január 16.)
  2. Chinese postman problem. xlinux.nist.gov (Hozzáférés: 2020. január 16.)
  3. Útbejárási probléma. www.tankonyvtar.hu (Hozzáférés: 2020. január 16.)
  4. 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]