Saith Pont Königsberg

Problem o fewn mathemateg a ddatryswyd gan Leonhard Euler yw Saith Bont Königsberg, fe ysbrydolwyd y broblem gan y ddinas Königsberg yn Rwsia a elwir yn Kaliningrad erbyn hyn. Lleolir y ddinas hon ar lannau afon Pregolya, ac mae rhan o'r ddinas yn gorwedd ar ddwy ynys fawr, a gysylltir a'i gilydd ac a'r tir mawr gan saith bont. Y cwestiwn i'w ddatrys oedd "a yw'n bosib cerdded ar daith sy'n croesi pob bont unwaith ac unwaith yn unig?".

Map o Königsberg yn amser Euler, gan ddangos lleoliad y saith bont a'r afon Pregolya.

Drwy ateb y broblem hon gosododd Leonhard y seilaiu ar gyfer theori (neu haniaeth) graffiau a thopoleg.

Datrysiad Euler

Ym 1736, profodd Leonhard Euler nad yw taith o'r fath yn bosib; lluniodd Euler y broblem yn nhermau haniaeth graffiau, drwy haniaethu achos Königsberg — yn gyntaf, trwy anwybyddu popeth ar wahân i ddarnau o dir a'r pontiau yn eu cysylltu. Yn lle darn o dir rhoddodd smotyn du a alwaodd yn 'fertig' ac yn hytrach na phont rhoddodd linell a alwodd yn 'ymyl'. Gelwir y strwythyr mathemategol canlynol yn graff (aml-graff, a bod yn fanwl gywir):

→ →

Cyn belled a bod y cysylltiadau rhwng y fertigau'n aros yr un peth, gellir newid siap ein darlun o'r graff a lleoliad y fertigau heb newid y graff ei hun.

Sylweddolodd Euler fod modd datrys y broblem yn nhermau graddau'r fertigau. Gradd fertig yw'r nifer o ymylon sy'n cyffwrdd ag ef; yn y graff dan sylw, mae gan dri fertig gradd 3, ac mae gan un fertig gradd 5. Profodd Euler fod cylchred o'r fath yr oeddem yn ceisio yn bodoli os yw dau neu'n lai o fertigau gyda gradd odrif. Gelwir cylchred o'r fath yn gylchlwybr Euler. Dyma oedd yn ei feddwl: pan fo person yn dod i bont, mae hefyd yn gadael y bont; mae 2 yn eilrif. Gan fod pedwar fertig â gradd odrif yn graff Königsberg, ni all fod gylchred Euler ganddo.

Cyflwr presennol y pontydd

Königsberg a'i phontydd heddiw

Dinistrwyd dwy o'r saith bont wreiddiol wrth i'r awyrlu Brydeinig fomio Kaliningrad yn ystod yr Ail Ryfel Byd. Dymchwelwyd dwy arall ar ôl y rhyfel, a chodwyd traffordd yn eu lle. Erys y tair arall, er i un ohonynt gael ei hail-adeiladu ym 1935. Roedd yma, felly, yn 2,000 5 pont.

Yn nhermau haniaeth graffiau, mae gan ddau o'r fertigau gradd 2, a'r ddau arall gradd tri. Mae llwybr Euleraidd yn bosib heddiw felly, ond rhaid iddo gychwyn ar un ynys a gorffen ar un arall. Mae cerdded y llwybr yma'n eithriadol o boblogaidd gan ymwelwyr.

Mae Prifysgol Canterbury yn Christchurch, Seland Newydd wedi codi model o'r pontydd a'r daith o'u cwmpas rhwng yr hen Lyfrgell Gwyddoniaeth ac Adeilad Erskine. Yn lle afon ceir llwyn bychan ac ar y prif ynys ceir tōrō o garreg. Ymgorfforwyd y broblem hefyd i'w system o bafinau gan Rochester Institute of Technology o flaen eu 'Canolfan Gene Polisseni', yn 2014.