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. A megoldás kulcsa az az észrevétel, hogy ha három adott város között fellépő három távolság közül kettőt ismerünk, akkor a harmadikat már ki tudjuk számolni. A városok ugyanis egy egyenes mentén helyezkednek el, így ez a harmadik távolság aszerint lesz a két ismert távolság összege vagy pedig a különbsége, hogy az a város, amelynek a másik kettőtől mért távolságát ismerjük, elválasztja-e a másik kettőt, vagy sem. Ezt felhasználva a megoldók módszeresen töltögették ki a hiányos táblázatot, míg végül valamennyi hiányzó értékre rátaláltak Az alábbiakból kiderül, hogy ez miért sikerülhetett. Áttekinthetőbb lesz a kép, ha az egyes városokat egy nyolcoldalú sokszög csúcsaiként ábrázoljuk és éllel kötjük össze azokat a csúcsokat, amelyeknek ismerjük a távolságát (1. ábra). Így egy úgynevezett gráfot kapunk.
1. ábra Az ábrából látható, hogy a hét ismert útszakasz mentén a városból indulva a útvonalon eljuthatunk a városig úgy, hogy minden várost pontosan egyszer ejtünk útba. Igaz az is ‐ és ez a lényeg ‐, hogy bármely két város között létezik ismert hosszúságú szakaszokból álló útvonal, mégpedig csak egy. Kiszemelve most már egyet a városok közül ‐ legyen ez például az ‐, a további városok -tól mért távolsága az -ból hozzájuk vezető útvonal mentén haladva határozható meg az adott és az útközben megismert távolságok alapján a bevezetőben említettek szerint. Az város esetében ez az , illetve az útvonalak bejárását jelenti, Az útvonal mentén kapjuk, hogy
az útvonalon pedig
2. ábra Miután pedig ismerjük egy városnak az összes többitől mért távolságát, bármely két város távolsága meghatározható. A teljesen kitöltött táblázatot a 2. ábra mutatja. A szomszédos városok közti távolságok: , , , , , , .
Megjegyzés. Látható, hogy feladatunk az ismertnek adott távolságok bármely értéke mellett egyértelműen megoldható. Ez nyilván általában is igaz, ha az 1. ábra mintájára elkészített gráf összefüggő ‐ azaz bármely két pontja között vezet út és a gráf ún. ,,fa'' is ‐ azaz bármely két pontja között csak egy út vezet. Nem összefüggő gráfra a feladat nem oldható meg, ha pedig vannak olyan városok, amelyek között több út is vezet, akkor az ezek szakaszaira vonatkozó feltételek nem függetlenek, a feladatnak igy nincs mindig megoldása. Mivel egy pontú fának éle van, általában az mondhatjuk, hogy az összes távolságok meghatározásához távolság megadása szükséges és ennyi elegendő is, ha az ismert hosszúságú szakaszok egy fa éleit alkotják. |