Damcaniaeth graffiau - Wicipedia

# Damcaniaeth graffiau

### Oddi ar Wicipedia

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.

## [golygu] Hanes

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.

Categori: Haniaeth graffiau

##### Views

- Erthygl
- Sgwrs
- Diwygiad cyfoes

##### Chwilio

##### Ieithoedd eraill

- Aragonés
- العربية
- Български
- বাংলা
- Bosanski
- Česky
- Dansk
- Deutsch
- English
- Esperanto
- Español
- Euskara
- فارسی
- Suomi
- Français
- עברית
- Magyar
- Bahasa Indonesia
- Italiano
- 日本語
- 한국어
- Lietuvių
- Монгол
- Nederlands
- ‪Norsk (nynorsk)‬
- ‪Norsk (bokmål)‬
- Polski
- Português
- Русский
- Simple English
- Slovenčina
- Slovenščina
- Српски / Srpski
- Svenska
- ไทย
- Türkçe
- Українська
- Tiếng Việt
- 中文