Saith Bont Königsberg
Oddi wrth Wicipedia, y gwyddoniadur rhydd.
Problem a datryswyd gan haniaeth graffiau yw Seven Bont Königsberg, a ysbrydolwyd gan y ddinas yn Rwsia a gelwir yn Kaliningrad erbyn hyn. Lleolwyd y ddinas ar yr afon Pregolya, ac mae rhan o'r ddinas ar ddau ynys mawr, a gysylltwyd i'w gilydd ac i'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.
[golygu] 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.
[golygu] 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