Pôs y pedwar lliw

Mewn mathemateg, dywed y ddamcaniaeth pedwar lliw (neu theori'r map pedwar lliw): "Mewn map, nid oes angen mwy na phedwar lliw gwahanol i liwio rhanbarthau'r map, fel nad oes dwy ranbarth cyfagos o'r un lliw." Roedd y pôs pedwar lliw, a'r pôs y pum lliw o'i flaen, yn sialens i fathemategwyr, cyn i'r theori gael ei brofi yn 1976 gan Kenneth Appel a Wolfgang Haken.^[1]

Termau:

Mae "map" yn cyfeirio at blân dau-ddimensiwn, wedi'i rannu gan linellau yn nifer o ranbarthau (neu "wledydd").
Mae "cyfagos" yn golygu bod dwy ranbarth yn rhannu ffin (llinell; cromlin) cyffredin, ond nid mewn cornel, lle mae tair neu fwy o ranbarthau yn cwrdd.^[2]

Canlyniad y ddamcaniaeth yw'r datganiad canlynol, syml: "Nid oes fyth angen mwy na 4 lliw i liwio unrhyw fap".^[2]

Hanes

Y cofnod cyntaf o bôs y pedwar lliw oedd ar 23 Hydref 1852 pan oedd Francis Guthrie yn ceisio canfod y nifer lleiaf o liwiau oedd eu hangen i liwio map o Loegr. Aeth at ei frawd Frederick, a oedd yn un o fyfyrwyr Augustus De Morgan yn Ngholeg Prifysgol Llundain, ac aethant ati i ganfod ateb.^[3]

Yn wahanol i'r theori pum lliw, theori sy'n datgan bod pum lliw yn ddigon i liwio map, a brofwyd yn yr 1800au, profwyd pôs y pedwar lliw ym 1976 gan Kenneth Appel a Wolfgang Haken. Hon oedd y ddamcaniaeth fawr gyntaf i'w phrofi gan ddefnyddio cyfrifiadur. Ar y cychwyn, nid oedd pob mathemategydd yn derbyn eu diffiniad fel prawf cadarn, gan fod prawf cyfrifiadurol bron yn amhosibl i rywun ei wirio â llaw. Ers hynny, mae'r prawf wedi ennill ei blwyf, er bod rhai amheuon yn parhau.

Ymhellach i'r gwaith gan Appel–Haken a gyhoeddwyd yn 1976, cyhoeddwyd prawf symlach o'r gosodiad yn 2005 gan Robertson, Sanders, Seymour, a Thomas ac eto yn 2005 gan Georges Gonthier, eto'n ddibynnol ar feddalwedd.

Y ddamcaniaeth

Gwendid y ddamcaniaeth, yn ôl rhai, yw ei bod gam y tu hwnt i'r broblem wreiddiol, real. Hynny yw, os oes gan wlad ddau leoliad nad ydynt wedi eu cysylltu, yna mae'n rhaid iddynt fod o'r un lliw - glas (A) yn y diagram.

Esiamplau real o hyn fyddai Oblast Kaliningrad, sy'n rhan o Rwsia, neu Nakhchivan, sy'n rhan o Weriniaeth Aserbaijan. Yma, byddai angen o leiaf 5 lliw.

Cyfeiriadau

↑ Thomas (1998, p. 849); Wilson (2014)).
↑ ^2.0 ^2.1 From Gonthier (2008): "Definitions: A planar map is a set of pairwise disjoint subsets of the plane, called regions. A simple map is one whose regions are connected open sets. Two regions of a map are adjacent if their respective closures have a common point that is not a corner of the map. A point is a corner of a map if and only if it belongs to the closures of at least three regions. Theorem: The regions of any simple planar map can be colored with only four colors, in such a way that any two adjacent regions have different colors."
↑ Donald MacKenzie, Mechanizing Proof: Computing, Risk, and Trust (MIT Press, 2004) t. 103

[1] Thomas (1998, p. 849); Wilson (2014)).

[Gonthier_2008-2] 2.0 ^2.1 From Gonthier (2008): "Definitions: A planar map is a set of pairwise disjoint subsets of the plane, called regions. A simple map is one whose regions are connected open sets. Two regions of a map are adjacent if their respective closures have a common point that is not a corner of the map. A point is a corner of a map if and only if it belongs to the closures of at least three regions. Theorem: The regions of any simple planar map can be colored with only four colors, in such a way that any two adjacent regions have different colors."

[MacKenzie-3] Donald MacKenzie, Mechanizing Proof: Computing, Risk, and Trust (MIT Press, 2004) t. 103

[1]

[2]

[3]