Pitong Tulay ng Königsberg
Ang Pitong Tulay ng Königsberg ay isang tanyag na nalutas na problemang pangmatematika na pinukaw ng aktuwal na pook at sitwasyon. Ang lungsod ng Königsberg, Prusya (ngayon ay Kaliningrad, Rusya na) ay nasa Ilog Pregel, at may dalawang malaking pulo na pinagdurugtong, at idinurugtong sa pangunahing lupa, ng pitong tulay. Ang problema ay kailangang mapagpasiyahan kung posibleng maglakad sa isang ruta na tumutulay sa bawat tulay ng isang beses lamang.
Ang solusyon ni Euler
[baguhin | baguhin ang wikitext]Noong 1736, pinatunayan ni Leonhard Euler na imposible ito. Sa pagpapatunay ng resulta, isinapormula ni Euler ang problema alinsunod sa teoriyang grap. Ginawa niyang abstrakto ang kaso ng Königsberg - una, sa pamamagitan ng pag-alis ng lahat ng katangian maliban sa mga kalupaan at mga tulay na nagdurugtong sa mga ito; pangalawa, sa pamamagitan ng pagpapalit ng bawat kalupaan ng isang tuldok, na tinawag na vertex o node, at bawat tulay ng isang guhit, na tinawag na edge o link. Ang kinalabasang istrukturang pangmatematika ay tinatawag na grap.
→
→
Ang hugis ng grap ay mababago sa anumang paraan nang hindi nababago ang grap mismo, hangga't ang mga link ng mga node ay hindi binabago. Hindi mahalaga kung ang mga link ay tuwid o baluktok, o ang isang node ay nasa kaliwa o nasa kanan ng isa pa.
Napagtanto ni Euler na ang problema ay malulutas alinsunod sa mga degree ng mga node. Ang degree ng isang node ay ang dami ng edge na nakadikit dito; sa grap ng tulay ng Königsberg, tatlong node ang may degree na 3 at ang isa ay may degree na 5.
Pinatunayan ni Euler na ang isang circuit na may anyong inaasam ay posible lamang kung ang tangi kung ang grap ay magkadugtong, at may eksaktong sero o dalawang node na may gansal na degree. Ang ganitong paglakad ay tinatawag na Eulerian path o lakarang Euler. Dagdag pa, kung may dalawang node na may gansal na degree, ang mga iyon ay dapat na simula at dulong tuldok ng Eulerian path. Dahil ang grap na kaugnay ng Königsberg ay may apat na node na may gansal na degree, hindi ito puwedeng magkaroon ng Eulerian path.
Ang alternatibong anyo ng problema ay humihiling ng isang path na tumutulay sa lahat ng tulay at mayroon ding iisang pinagmulan at pinagtapusang tuldok. Ang ganitong lakad ay tinatawag na Eulerian circuit o tour ni Euler. May Eulerian circuit kung at tangi kung ang grap ay magkadugtong at walang node na may gansal na degree. Mapapansin na ang lahat ng Eulerian circuit ay Eulerian path din.
Ang gawa ni Euler ay ihinayag sa Akademiya ng St. Petersburg noong Agosto 26, 1735 at inilathala sa pamagat na Solutio problematis ad geometriam situs pertinentis (Ang solusyon ng problemang may kinalaman sa heometriya ng posisyon) sa diyornal na Commentarii academiae scientiarum Petropolitanae noong 1741.[1]
Kahalagahan sa kasaysayan ng matematika
[baguhin | baguhin ang wikitext]Sa kasaysayan ng matematika, ang paglutas ni Euler sa problema ng tulay ng Königsberg ay itinuturing na unang teoriya ng teoriyang grap, na kinikilala namang sangay ng combinatorics (bagama't pinag-iisipan na rin ang mga problemang combinatorial bago pa man).
Dagdag pa, ang pagkatanto ni Euler na ang susing impormasyon ay ang bilang ng mga tulay at ang listahan ng mga dulo nito (sa halip na ang eksaktong posisyon ng mga ito) ay parang paghula sa pag-unlad ng topolohiya. Ang pagkakaiba ng aktuwal na layout at ng schematic ng grap ay isang magandang halimbawa na ang topolohiya ay hindi interesado sa mga di-nagbabagong hugis ng mga bagay.
Iba pang anyo
[baguhin | baguhin ang wikitext]Ang klasikong paglalahad ng problema, na ibinigay sa itaas, ay gumagamit ng mga di-tinukoy na node - alalaong baga'y, magkakapareho sila maliban sa kung paano sila pinagdugtong. May naiibang anyo kung saan ang mga node ay tinukoy - ang bawat node ay binigyan ng natatanging pangalan o kulay.
Ang hilagang pampang ng ilog ay kinalalagyan ng Schloß (bigkas: Shlos), o kastilyo, ng Bughaw na Prinsipe; ang timog ay ng Pulang Prinsipe. Ang silangang pampang ay lugar ng Kirche (bigkas: Kir.tse) ng Obispo, o simbahan; at sa maliit na pulo sa sentro ay ang Gasthaus (bigkas: Gast.haws), o inn (pook na puwedeng mag-inuman).
Nauunawaan na ang problema na kailangang sundin ay dapat may pagkakasunod-sunod, at nagsisimula sa isang pahayag ng orihinal na problema: Nakagawian na ng mga mamamayan, na matapos ang ilang oras sa Gasthaus, na tangkaing lakarin ang mga tulay, marami ang nakakabalik para sa inuman na nagsasabing nagtagumpay sila. Subalit walang makaulit ng tagumpay na ito kapag nag-umaga na.
8: Nang sinuri ng Bughaw na Prinsipe ang sistema ng mga tulay ng bayan sa pamamagitan ng teoriyang grap nahinuha niya na ang mga tulay ay hindi puwedeng lakarin. Nag-isip siya ng isang lihim na plano na lumikha ng ikawalong tulay para makapagsimula siya sa gabi sa kanyang Schloß, lakarin ang mga tulay, at magtapos sa Gasthaus upang maipagyabang ang kanyang tagumpay. Siyempre pa ayaw niyang magaya ng Pulang Prinsipe ang nagawa niya. Saan dapat magtayo ng ikawalong tulay ang Bughaw na Prinsipe?
9: Nagalit ang Pulang Prinsipe sa masalimuot na solusyon ng kapatid niya sa problema, at nais niyang magtayo ng ika-siyam na tulay, na magpapahintulot sa kanyang magsimula sa kanyang Schloß, lakarin ang mga tulay, at magtapos sa Gasthaus at ipamukha sa kapatid niya ang kanyang tagumpay. Pagkatapos ay hindi dapat "malakad" ng kapatid niya ang mga tulay. Saan dapat itayo ng Pulang Prinsipe ang ika-siyam na tulay?
10: Masama ang loob na pinanood ng Obispo ang masiglang pagtatayo ng mga tulay na ito. Sa palagay niya nakakasama ito sa Weltanschauung (bigkas: Velt.an.shaw.ung, pananaw sa buhay) ng bayan at, mas malala pa, ay nagpapalaganap ng paglalasing. Nais niyang magtayo ng ika-sampung tulay na magpapahintulot sa lahat ng mamamayan na lakarin ang tulay at makabalik sa kani-kaniyang tulugan. Saan itatayo ng Obispo ang ika-sampung tulay?
Mga Solusyon
[baguhin | baguhin ang wikitext]
Gawing simple ang lungsod, tulad ng nauna, hanggang magi itong grap. Kulayan ang bawat node. Tulad ng klasikong problema, walang lakarang Euler ang posible; hindi makakaapekto ang pagkulay dito. Lahat ng apat na node ay may gansal na bilang ng edge.
8: Ang lakarang Euler ay posible kung ang eksaktong 2 node ay may gansal na bilang ng edge. Kung totoo ito, ang paglakad ay dapat magsimula sa isang node at magtapos sa isa pa. Dahil 4 lamang ang node sa palaisipan, ang solusyon ay simple. Ang paglakad ay dapat magsimula sa bughaw na node at magtapos sa kahel na node. Kaya't magdodrowing ng isang bagong edge sa pagitan ng dalawa pang ibang node. Dahil pareho silang may gansal na bilang ng edge dati, dapat ay mayroon na silang tukol na bilang ng edge, na tutupad sa mga kondisyon. Pagbabago ito sa parity mula gansal patungo sa tukol na degree.
9: Ang ika-9 na tulay ay madali kapag nalutas na ang ika-walo. Ang inaasam ay mapahintulutan ang pula at mapagbawalan ang bughaw bilang panimula; Ang kahel na node ang siya pa ring dulo ng lakaran at ang puting node ay hindi maaapektuhan. Para mabago ang parity ng parehong pula at bughaw na node, magdrowing ng bagong edge sa pagitan nila.
10: Dadalin tayo ng ika-10 tulay sa medyo lihis na direksiyon. Nais ng Obispo na makabalik ang lahat ng mamamayan sa pinagmulan nila. Ito ay isang siklong Euler at nangangailangan na ang lahat ng node ay may tukol na degree. Matapos ang solusyon ng ika-9 na tulay, ang pula at kahel na node ay may gansal na degree, kaya't kailangan silang baguhin sa pamamagitan ng paglalagay ng bagong edge sa pagitan nila.
Kasalukuyang kalagayan ng mga tunay na tulay
[baguhin | baguhin ang wikitext]Dalawa sa pitong orihinal na tulay ay nawasak ng bomba noong Ikalawang Digmaang Pandaigdig. Ang dalawa pa ay sinira na ng mga Ruso at pinalitan ng modernong haywey. Ang tatlong iba pang tulay ay naroroon pa rin, bagama't dalawa lamang sa mga ito ang panahon pa ni Euler (ang isa ay binago ng mga Aleman noong 1935).[2] Kaya't , sa kabuuan, may limang tulay sa modernong Königsberg.
Alinsunod sa teoriyang grap, ang dalawa sa mga node ay mayroon nang degree na 2, at ang dalawa pa ay degree na 3. Samakatuwid puwede na ang isang Eulerian path, pero dahil kailangan nitong magsimula sa isang pula at magtapos sa isa pa, di ito praktikal para sa mga turista.[3]
Mga sanggunian
[baguhin | baguhin ang wikitext]- ↑ The Euler Archive, komentaryo sa lathalain, at orihinal na teksto, sa Latin.
- ↑ Taylor, Peter (2000). "What Ever Happened to Those Bridges?". Australian Mathematics Trust. Inarkibo mula sa orihinal noong 2012-03-19. Nakuha noong 2006-11-11.
{{cite web}}: Unknown parameter|month=ignored (tulong)CS1 maint: date auto-translated (link) - ↑ Stallmann, Matthias (2006). "The 7/5 Bridges of Koenigsberg/Kaliningrad". Nakuha noong 2006-11-11.
{{cite web}}: Unknown parameter|month=ignored (tulong)CS1 maint: date auto-translated (link)