Königsbergeko zazpi zubietako ebazkizuna

Königsbergeko zazpi zubietako ebazkizuna matematikaren historian ospetsua den ebazkizuna da. 1736. urtean Leonhard Euler matematikariak ebatzi zuen soluziorik ez zuela erakutsiz. Horrela, esan daiteke grafo-teoria eta topologia izeneko adarrak sortu zirela matematikaren baitan.

Königsberg hiria Pregolia ibaiko bi ertzetan kokatzen zen eta ibaiak besarkatzen zituen bi uharte zabal ere hartzen zituen, bi ertzetara 7 zubien bitartez loturik, irudiak erakusten duen bezala.

Hirian zehar, zazpi zubiak behin bakarrik zeharkatzen dituen txango bat bilatzea da ebazkizunaren xedea, ibaia zubietatik bakarrik zeharkatuz, eta zubiak oso osorik ibili behar direla.

Lehorrean jarraitzen den ibilbideak ebazpenerako garrantzirik ez duenez, zazpi zubietako mapa grafo baten bitartez azal daiteke, zubiak ertz moduan irudikatuz:

→ →

Ibilbide bateko abiapuntuan eta helmugan ezik, erpin batera sartu ondoren, atera ere egin behar da. Beraz, ibilbide batean erpin batera heltzen den aldi kopurua bat dator, muturretako erpinetan ezik, erpin batetik ateratzen den aldi kopuruarekin. Beraz, zubiak edo ertzak behin bakarrik zeharkatu behar badira, erpin guztietako mailak bikoitiak izan behar dira, muturreko erpinetan ezik. Erpin berean hasi eta bukatu nahi bada, Eulerren zirkuitua osatu nahi bada alegia, abiapuntuko eta helmugako erpineko maila ere bikoitia izan beharko da.

Zazpi zubietako ebazkizunean, zazpi zubietako mapari dagokion grafoko lau erpinak maila bakoitikoak direnez, ezin da osatu Eulerren zirkuiturik, ez eta Eulerren ibilbiderik ere, hau da ezin dira zeharkatu zazpi zubiak zubirik errepikatu gabe.

Azterketa honetatik Eulerren teorema sortzen da. Ertzak behin bakarrik zeharkatzen dituen ibilbide bati ibilbide eulertar deritzo. Ibilbide eulertarra izateko, abiapuntuan eta helmugan ezik (bi erpinetan ezik, alegia), beste erpin guztietako mailak bikoitiak izan behar dira. Erpin berean hasi eta bukatzen bada, zirkuitu eulertarra dagoela esaten da, kasu honetan erpin guztietako mailak (abiapuntua eta helmuga barne) bikoitiak direlarik.

• Grafo eulertar