Damcaniaeth graffiau

Oddi ar Wicipedia
Neidio i: llywio, chwilio

Mewn mathemateg a gwyddoniaeth gyfrifiadurol, astudiaeth o graffiau yw damcaniaeth graffiau. Set o fertigau ynghyd â chasgliad ymylon yn cysylltu parau o fertigau yw "graff" yn y cyd-destyn hwn, ac ni dylid eu drysu gyda'r "graff" sy'n perthyn i ffwythiant.

Hanes[golygu]

Mae'n debyg mae'r papur a sgrifennwyd gan Leonhard Euler am Saith Pont Königsberg ym 1736 oedd y cyntaf a gyhoeddwyd ynglŷn â damcaniaeth graffiau. Roedd y cyhoeddiad hwn, a phapur Vandermonde am broblem y marchog yn datblygu ymhellach yr analysis situs a gychwynwyd gan Leibniz.

Ymysg y mathemategwyr enwog oedd yn weithgar ar broblemau damcaniaeth graffiau yn y canrifoedd canlynol oedd Cauchy, L'Huillier, Cayley, Pólya, a De Bruijn. Bathwyd y term graph (yn ein ystyr ni) ym 1878 gan Sylvester.

Un o'r problemau enwocaf yn hanes damcaniaeth graffiau yw'r problem pedwar lliw. Lluniwyd y broblem gan Francis Guthrie ym 1852 hyd a wyddys. Ni lwyddodd neb i brofi'r ddamcaniaeth am dros ganrif, er i Cayley, Kempe ac eraill cynhyrchu profion gwallus . Fe gyhoeddodd Kenneth Appel a Wolfgang Haken prawf ohonni ym 1976, ond ni argyhoeddwyd pawb yn y gymuned fathemategol ohonno, am ei fod yn ddibynnol ar defnydd o gyfrifiadur i wirio 1936 o achosion arbennig. Rhoddwyd prwawf symlach, a ystyrir yn ddilys gan bawb mwy neu lai, gan Robertson, Seymour, Sanders and Thomas ym 1997.

Roedd y broblem pedwar lliw yn ysbrydolaeth astudiaeth o lliwio graffiau ar wynebau o wahanol genws gan Tait, Heawood, Ramsey, Hadwiger, Petersen, Turán ac eraill.

Bu datblygiad annibynnol topoleg rhwng 1860 a 1930 cyfranu'n ffrwythlon iawn i damcaniaeth graffiau trwy weithiau Jordan, Kuratowski a Whitney. Bu datblygiad algebra haniaethol yn ddefnyddiol hefyd, ac roedd profi rheolau cylchred Kirchhoff yn enghraifft cynnar o hynny.

Cyflwynwyd dulliau tebygolrwydd mewn damcaniaeth graffiau gan Erdős ac Rényi, bu arwain at astudiaeth o hap-graffiau.