Kēnigsbergas tiltu problēma
Septiņi Kēnigsbergas tilti ir vēsturiski slavena matemātikas problēma. Šo problēmu 1735. gadā atrisināja Leonhards Eulers. Tas aizsāka grafu teoriju. Tas vēlāk noveda pie topoloģijas attīstības.
Kēnigsbergas pilsēta Prūsijā (tagad Kaļiņingrada, Krievija) atradās abpus Pregeles upei. Tā ietvēra divas lielas salas, kas bija savienotas viena ar otru un ar cietzemi ar septiņiem tiltiem.
Problēma bija atrast veidu, kā izstaigāt pilsētu, šķērsojot katru tiltu vienu reizi un tikai vienu reizi. Uz salām nevarēja nokļūt pa citiem ceļiem, kā tikai pa tiltiem. Katrs tilts katru reizi bija jāšķērso pilnībā. Pastaiga nedrīkstēja sākties un beigties vienā un tajā pašā vietā. Ēlers pierādīja, ka šai problēmai nav risinājuma.
Kēnigsbergas karte Ēlera laikā, kurā redzams septiņu tiltu faktiskais izvietojums, izceļot Pregēlas upi un tiltus.
Eilesera analīze
Pirmkārt, Ēlers norādīja, ka maršruta izvēlei katras zemes masas iekšienē nav nozīmes. Vienīgā svarīgā maršruta īpašība ir kārtība, kādā tiek šķērsoti tilti. Tāpēc viņš mainīja problēmu uz abstraktu. Tas lika pamatus grafu teorijai. Viņš likvidēja visas īpašības, izņemot sauszemes masu sarakstu un tiltus, kas tās savieno. Grafu teorijas valodā viņš aizstāja katru zemes masu ar abstraktu "virsotni" jeb mezglu. Tad katru tiltu viņš aizstāja ar abstraktu savienojumu, "malu". Krāja (ceļš) fiksēja, kuras divas virsotnes (zemes masīvi) ir savienotas. Šādā veidā viņš izveidoja grafiku.
→
→ 
Uzzīmētais grafiks ir abstrakts problēmas attēls. Tātad malas var savienot jebkādā veidā. Svarīgi ir tikai tas, vai divi punkti ir savienoti vai nav. Grafa attēla maiņa nemaina pašu grafiku.
Tālāk Ēlers novēroja, ka (izņemot pastaigas galapunktus), kad vien ieejot kādā punktā pa tiltu, pa kādu tiltu arī iziet no punkta. Jebkurā grafika gājienā to reižu skaits, kad ieejam kādā punktā, ir vienāds ar to reižu skaitu, kad to atstājam. Ja katrs tilts ir šķērsots tieši vienu reizi, no tā izriet, ka katrai zemes masai (izņemot tās, kas izvēlētas kā sākumpunkts un finišs) to tiltu skaitam, kas skar šo zemes masu, jābūt pāra skaitlim. Tas ir tāpēc, ka, ja ir n tiltu, tas ir šķērsots tieši 2n reižu. Tomēr visām četrām sākotnējā uzdevumā minētajām sauszemes masām pieskaras nepāra skaits tiltu (vienai no tām pieskaras 5 tilti, bet pārējām trim - 3 tilti). Ir ne vairāk kā divas masas, kas var būt pastaigas galapunkti. Tātad apgalvojums, ka pastaiga šķērso katru tiltu vienu reizi, noved pie pretrunas.
Mūsdienu valodā Eilejs parāda, ka tas, vai ir vai nav iespējams veikt gājienu pa grafiku, šķērsojot katru malu vienu reizi, ir atkarīgs no mezglu grādiem. Mezgla pakāpe ir to malu skaits, kas tam pieskaras. Ēlers parāda, ka pastaigas nepieciešamais nosacījums ir tāds, ka grafam jābūt savienotam un tam jābūt tieši nulles vai diviem nepāra pakāpes mezgliem. Šo Ēlera rezultātu vēlāk pierādīja Kārlis Hierholcers. Šādu pastaigu tagad sauc par Ēlera ceļu jeb Ēlera pastaigu. Ja ir nepāra pakāpes mezgli, tad jebkurš Eulera ceļš sākas vienā no tiem un beidzas otrā. Tā kā vēsturiskās Kēnigsbergas grafā ir četri nepāra pakāpes mezgli, tam nevar būt Eulera ceļš.
1735. gada 26. augustā Ēlera darbs tika iesniegts Sanktpēterburgas Akadēmijai. Tas tika publicēts 1741. gadā žurnālā Commentarii academiae scientiarum Petropolitanae kā Solutio problemis ad geometriam situs pertinentis (Problēmas risinājums attiecībā uz stāvokļa ģeometriju). Tas ir pieejams angļu valodā The World of Mathematics.
Nozīme matemātikas vēsturē
Matemātikas vēsturē Ēlera Kēnigsbergas tilta problēmas risinājums tiek uzskatīts par pirmo grafiku teorijas teorēmu. Grafu teorija tagad parasti tiek uzskatīta par kombinatorikas nozari.
Pašreizējais tiltu stāvoklis
Divi no septiņiem sākotnējiem tiltiem tika iznīcināti Kēnigsbergas bombardēšanas laikā Otrā pasaules kara laikā. Vēl divi tilti tika nojaukti vēlāk. To vietā tika izbūvēta moderna automaģistrāle. Pārējie trīs tilti ir saglabājušies, lai gan tikai divi no tiem ir no Ēlera laikiem (viens tika pārbūvēts 1935. gadā). Tādējādi 2000. gadā Kaļiņingradā bija pieci tilti.
No grafiku teorijas viedokļa diviem no mezgliem tagad ir 2. pakāpe, bet pārējiem diviem - 3. pakāpe. Tāpēc tagad ir iespējams Eulera ceļš, bet, tā kā tam jāsākas vienā salā un jābeidzas otrā, tas ir nepraktisks tūristu vajadzībām.
Saistītās lapas
- Ikosas spēle
- Hamiltona ceļš
- Ūdens, gāze un elektrība
- Ceļojošā pārdevēja problēma
Jautājumi un atbildes
J: Kas ir Kēnigsbergas septiņu tiltu problēma?
A: Septiņi Kēnigsbergas tilti ir slavena matemātiska problēma, kas paredz atrast veidu, kā izstaigāt pilsētu, šķērsojot katru no septiņiem tās tiltiem tikai vienu reizi.
J: Kas atrisināja Kēnigsbergas septiņu tiltu problēmu?
A: Leonhards Eulers atrisināja Kēnigsbergas septiņu tiltu problēmu 1735. gadā.
J: Ko radīja Kēnigsbergas septiņu tiltu problēmas atrisinājums?
A: Kēnigsbergas septiņu tiltu problēmas atrisināšana noveda pie grafu teorijas sākuma, kas vēlāk noveda pie topoloģijas attīstības.
J: Kur atrodas Kēnigsberga?
A: Kēnigsberga atrodas Prūsijā, kas tagad ir daļa no Kaļiņingradas, Krievijā.
J: Kāds bija Kēnigsbergas plānojums?
A: Kēnigsberga bija izvietota abpus Pregeles upei, un tajā bija divas lielas salas, kas bija savienotas viena ar otru un ar cietzemi ar septiņiem tiltiem.
J: Kādas bija prasības, lai atrisinātu Kēnigsbergas septiņu tiltu problēmu?
A: Lai atrisinātu problēmu, bija jāatrod veids, kā izstaigāt pilsētu, katru tiltu šķērsojot tikai vienu reizi, turklāt katru reizi katru tiltu šķērsojot pilnībā. Uz salām nevarēja nokļūt pa citu ceļu, izņemot pa tiltiem, un pastaiga nebija jāsāk un jābeidzas vienā un tajā pašā vietā.
Vai Ēlers pierādīja, ka Kēnigsbergas septiņu tiltu problēmai ir risinājums?
Atbilde: Nē, Ēlers pierādīja, ka Kēnigsbergas septiņu tiltu problēmai nav risinājuma.
