Saith Pont Königsberg

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

Problem a datryswyd gan haniaeth graffiau yw Saith Bont Königsberg, a ysbrydolwyd gan y ddinas yn Rwsia a elwir yn Kaliningrad erbyn hyn. Lleolir y ddinas 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?".

Datrysiad Euler

Ym 1736, profodd Leonhard Euler nad yw taith o'r fath yn bosib. I brofi hyn, lluniodd Euler y broblem yn nhermau haniaeth graffiau, trwy haniaethu achos Königsberg — yn gyntaf, trwy anwybyddu popeth ar wahan i darnau o dir a'r pontiau yn eu cysylltu; a'n ail, trwy rhoi smotyn (a gelwir yn fertig) yn lle pob darn o dir, a llinell (a gelwir yn ymyl) yn lle bob bont. Gelwir y strwythyr mathemategol sy'n ganlyn 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, a dim ond os y mae dau neu'n llai o fertigau gyda gradd odrif. (Fe gelwir cylchred o'r fath yn gylchred Euler). Gan fod pedwar fertig â gradd odrif yn graff Königsberg, ni all fod gylchred Euler ganddo.

Cyflwr presennol y pontydd

Dinistrwyd ddwy o'r saith bont wreiddiol wrth i'r awyrlu brydeinig fomio Kaliningrad yn ystod yr Ail Ryfel Byd. Dymchwelwyd dwy arall ar ol y rhyfel, a codwyd traffordd yn eu lle. Erys y tair arall, er i un ohonynt gael ei hail-adeiladu ym 1935.

Yn nhermau haniaeth graffiau, mae gan ddau o'r fertigau gradd 2, a'r ddau arall gradd tri. Mae llwybr Euleraidd yn bosib rŵan felly, ond rhaid iddo gychwyn ar un ynys a gorffen ar un arall