A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Megoldás. Megmutatjuk, hogy a válasz igenlő. Legyen minden párra. Határozzuk meg egyenként a továbbiakban potenciálnak nevezett mennyiségeket (nem feltétlenül ebben a sorrendben) a következő szabály szerint. Minden lépésben válasszunk egy olyan indexet, amelyre az potenciált korábban még nem határoztuk meg, és amelyre azon értékek összege, amelyekre -t már korábban meghatároztuk, a lehető legkisebb. Az így megválasztott indexre legyen az potenciál ez a minimális összeg. Tegyük fel, hogy az potenciált az potenciál előtt határoztuk meg, továbbá, hogy az előtt, pedig az után, de előtt meghatározott potenciálokhoz tartozó indexek halmaza. Az eljárásból következtében ekkor
tehát valóban teljesül minden párra. Az indoklás befejezéséhez pedig mindössze annyit kell megfigyelnünk, hogy éppen az () értékek összege, hiszen minden egyes pontosan egyszer szerepel -ben, mégpedig az -t és -t definiáló összegek közül abban, amelyik a később meghatározott potenciálhoz tartozik.
Megjegyzés. A feladat és a megoldása is sokkal világosabb, ha átfogalmazzuk gráfokra. Ilyen szóhasználattal élve azt kell igazolnunk, hogy bárhogyan is rendelünk egy pontú teljes gráf éleihez nemnegatív élhosszakat, a gráfnak létezik egy aciklikus (azaz irányított kört nem tartalmazó) irányítása, és az csúcs mindegyikéhez hozzárendelhető egy-egy nemnegatív potenciál úgy, hogy a csúcsok potenciálösszege ne haladja meg az élek összhosszát, továbbá bármely irányított él esetén az és csúcsok potenciálkülönbsége legalább az él hossza legyen. A megoldás kulcsa, hogy a potenciálok megválasztásának sorrendje az élhosszakhoz tartozó úgynevezett minvissza sorrend. Ez úgy kapható, hogy tetszőleges csúcsból kiindulva, ha már kiválasztottuk a sorrend első néhány elemét, akkor a soron következő csúcs az lesz, amelynek össztávolsága az eddig választott csúcsoktól minimális. Ha ezek után a gráf minden élét a minvissza sorrendben korábban felbukkanó csúcsból a sorrendben később szereplő csúcsba irányítjuk, akkor a potenciálokat természetes módon definiálva éppen a kérdéses számokat kapjuk meg. Érdekes, hogy míg a hasonló módon definiált maxvissza sorrendet sokat vizsgálták (a segítségével például hatékony algoritmus adható arra, hogy egy összefüggő gráfban megtaláljuk a lehető legkevesebb élt, amelyek elhagyásától a gráf már nem marad összefüggő), addig a minvissza sorrendnek a bizottság tudomása szerint nem ismert hasonló alkalmazása.
|