Kēnigsbergas tiltu problēma — Eilera pierādījums un grafu teorijas sākums
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īkēja sākties un beigties vienā un tajā pašā vietā. Ēlers pierādīja, ka šai problēmai nav risinājuma.
Eilera ideja — pārveidot problēmu par grafu
Eilers problēmu vienkāršoja, pārveidojot to par abstraktu shēmu: katru sauszemes gabalu (divas salas un divas krasta daļas) viņš attēloja kā punktu (virsotni), bet katru tiltu — kā līniju (malu), kas savieno divas virsotnes. Tādējādi pilsētas tiltu tīklojums kļuva par saistītu grafu ar četriem virsotnēm un septiņām malām.
Kā Eilers pierādīja, ka risinājuma nav
Galvenā novērojuma doma ir šāda: katru reizi, kad gājējs nonāk kādā vietā, lai izietu tālāk, viņam jāienāk pa vienu tiltu un jāiziet pa citu — tas nozīmē, ka noņemtie (izmantojamie) tilti katrā "vidējā" vietā ir pāru skaitā. Tāpēc, ja maršruts nav slēgts (sākas un beidzas dažādās vietās), tikai divās vietās — sākuma un beigu punktā — var būt nepāra skaits izejošu tiltu; visām pārējām vietām jābūt pāra skaitā.
Formulēti matemātiski: par saistītu grafu ir spēkā sekojošs nosacījums:
- ja visas virsotnes ir pāra pakāpes, grafā eksistē slēgts ceļš, kas ietver visas malas tieši vienu reizi (t.s. Eulerova cikla);
- ja tieši divas virsotnes ir nepāra pakāpes, eksistē atvērts ceļš, kas sākas vienā un beidzas otrā no šīm nepārajām virsotnēm (t.s. Eulerova taka);
- ja ir vairāk nekā divas nepāra virsotnes, tad nav iespējams iziet cauri visām malām tieši vienu reizi.
Konkrētajā Kēnigsbergas gadījumā grafā bija četras virsotnes, un visu šo virsotņu pakāpes (tiltu skaits, kas pievienots katrai zemes daļai) izrādījās nepāra — konkrēti 3, 3, 3 un 5 (kopā 14 malas = 2·7). Tā kā nepāroto virsotņu bija vairāk nekā divas, Eilera secinājums bija skaidrs: nav iespējams izstaigāt pilsētu tā, lai katru tiltu šķērsotu tieši vienu reizi.
Vēsturisks un teorētisks nozīmīgums
Eilera raksts (1736. gadā publicētais "Solutio problematis ad geometriam situs pertinentis") tiek uzskatīts par grafu teorijas dzimšanu. Lai gan Eilers neizmantoja mūsdienu terminus "grafi" vai "virsotnes", viņa ideja par objektu savienojumu un to īpašību analīzi atklāja jaunu matemātikas virzienu. No šīs vienkāršās uzbūves attīstījās gan grafu teorija, gan topoloģijas sākotnējās idejas par pozīcijas īpašībām, kas nemainās deformējot objektu.
Mūsdienās Eilera princips un Eulerova taka ir plaši izmantoti — no pilsētplānošanas un maršrutu optimizācijas līdz ķīmijas molekulārām struktūrām un datortīklu analīzēm. Kēnigsbergas tiltu problēma palikusi par klasiķu piemēru, kas parāda, kā vienkārša, ikdienišķa uzdevuma pārdomāšana var novest pie jaunas teorijas radīšanas.
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.
