Lliwio graffiau

Mewn theori graffiau, mae lliwio graffiau yn achos arbennig o labelu graffiau; mae'n aseiniad o labeli a elwir yn draddodiadol yn "lliwiau" i elfennau o graff yn amodol ar rai cyfyngiadau. Yn ei ffurf symlaf, mae'n ffordd o liwio fertigau graff fel nad oes unrhyw ddau fertig gyfagos o'r un lliw; gelwir hyn yn lliwio fertigau. Yn yr un modd, mae lliwio ymylon yn aseinio lliw i bob ymyl fel nad oes dwy ymyl gyfagos o'r un lliw, ac mae lliwio wynebau ar graff planar yn aseinio lliw i bob wyneb neu ranbarth fel nad oes gan unrhyw ddau wyneb sy'n rhannu ffin yr un lliw.

Lliwio graffiau

Enghraifft o'r canlynol	problem cyfrifiannu
Math	graph labeling
Ffeiliau perthnasol ar Gomin Wicimedia

Lliwio fertig cywir o graff Petersen gyda 3 lliw, y nifer lleiaf posib.

Lliwio fertig yw man cychwyn lliwio graffiau. Gellir trawsnewid problemau lliwio eraill i mewn i'r fersiwn fertig. Er enghraifft, lliwiad ymylon graff yw lliwiad vertigau ei graff llinell, a lliwiad wynebau graff planar yw lliwiad fertig ei ddeuol. Fodd bynnag, mae problemau lliwio nad ydynt yn lliwio fertig yn aml yn cael eu nodi a'u hastudio fel y mae. Mae hynny'n rhannol ar gyfer persbectif, ac yn rhannol oherwydd bod rhai problemau'n cael eu hastudio orau ar ffurf nad yw'n ffurf fertig, fel er enghraifft lliwio ymylon.

Mae'r confensiwn o ddefnyddio lliwiau yn tarddu o liwio gwledydd ar fap, lle mae pob wyneb wedi'i liwio'n llythrennol. Cafodd hyn ei gyffredinoli i liwio wynebau graff fewnblannedig yn yr plân. Erbyn deuoliaeth planar mae'n cywerth â lliwio'r fertigau, ac ar y ffurf hon mae'n cyffredinoli i bob graff. Mewn cynrychioliadau mathemategol a chyfrifiadurol, mae'n arferol i ddefnyddio'r gyfanrifau positif cyntaf fel y "lliwiau". Yn gyffredinol, gallwn ddefnyddio unrhyw set meidraidd fel y "set lliwiau". Mae natur y broblem lliwio yn dibynnu ar nifer y lliwiau ond nid ar beth ydyn nhw.

Mae lliwio graffiau yn mwynhau nifer o gymwysiadau ymarferol yn ogystal â heriau damcaniaethol. Heblaw am y mathau clasurol o broblemau, gellir gosod gwahanol gyfyngiadau ar y graff, neu ar y ffordd y mae lliw yn cael ei neilltuo, neu hyd yn oed ar y lliw ei hun. Mae hyd yn oed wedi cyrraedd poblogrwydd gyda'r cyhoedd ar ffurf y pos rhif poblogaidd Sudoku. Mae lliwio graffiau yn dal i fod yn faes ymchwil gweithredol iawn.

Hanes

Roedd y canlyniadau cyntaf am liwio graffiau yn delio bron yn gyfan gwbl â graffiau planar ar ffurf lliwio mapiau. Wrth geisio lliwio map o siroedd Lloegr, rhagdybiodd Francis Guthrie y rhagdybiaeth pedwar lliw, gan nodi bod pedwar lliw yn ddigonol i liwio'r map fel nad oedd unrhyw ranbarthau sy'n rhannu ffin gyffredin yn derbyn yr un lliw. Trosglwyddodd brawd Guthrie y cwestiwn i'w athro mathemateg Augustus de Morgan yng Ngholeg y Brifysgol, a soniodd amdano mewn llythyr at William Hamilton ym 1852. Cododd Arthur Cayley y broblem mewn cyfarfod o'r Gymdeithas Fathemategol Llundain ym 1879. Yr un flwyddyn, cyhoeddodd Alfred Kempe bapur a honnodd ei fod yn sefydlu'r canlyniad, ac am ddegawd ystyriwyd bod y broblem pedair lliw fel wedi'i datrys. Oherwydd ei gyflawniad, etholwyd Kempe yn Gymrawd y Gymdeithas Frenhinol ac yn ddiweddarach yn Arlywydd y Gymdeithas Fathemategol Llundain.

Ym 1890, tynnodd Heawood sylw at y ffaith bod dadl Kempe yn anghywir. Fodd bynnag, yn y papur hwnnw profodd y theorem pum lliw, gan ddweud y gellir lliwio pob map planar heb ddim mwy na phum lliw, gan ddefnyddio syniadau Kempe. Yn y ganrif ganlynol, datblygwyd llawer iawn o waith a damcaniaethau i leihau nifer y lliwiau i bedwar, nes i'r theorem pedwar lliw gael ei phrofi o'r diwedd ym 1976 gan Kenneth Appel a Wolfgang Haken. Aeth y prawf yn ôl at syniadau Heawood a Kempe gan i raddau helaeth ddiystyru datblygiadau diweddarach. Mae prawf y theorem pedwar lliw hefyd yn nodedig am fod y prawf mawr cyntaf a phrofwyd gyda chymorth cyfrifiadur.

Ym 1912, cyflwynodd George David Birkhoff y polynomial cromatig i astudio’r problemau lliwio, a gafodd ei gyffredinoli i’r polynomial Tutte gan Tutte, strwythurau pwysig mewn theori graffiau algebraidd. Roedd Kempe eisoes wedi tynnu sylw at yr achos cyffredinol, di-planar ym 1879, a dilynwyd llawer o ganlyniadau ar gyffredinoliadau o liwio graffiau planar i arwynebau o radd uwch yn gynnar yn yr 20fed ganrif.

Ym 1960, lluniodd Claude Berge ragdybiaeth arall ynglŷn â lliwio graffiau, y rhagdybiaeth graff perffaith gref, a ysgogwyd yn wreiddiol gan gysyniad o damcaniaeth gwybodaeth o'r enw cynhwysedd sero-gwall graff, a gyflwynwyd gan Shannon. Parhaodd y rhagdybiaeth i fod heb ei datrys am 40 mlynedd, nes iddo gael ei sefydlu fel y theorem graff perffaith gref gan Chudnovsky, Robertson, Seymour, a Thomas yn 2002.

Astudiwyd lliwio graffiau fel problem algorithmig ers dechrau'r 1970au: mae'r broblem rhif cromatig yn un o 21 o broblemau NP-cyflawn Karp o 1972, ac ar yr un pryd datblygwyd amryw o algorithmau amser esbonyddol yn seiliedig ar ôl-dracio ac dileu-cyfangu-dychweliad Zykov (1949). Cyflwynwyd un o brif gymwysiadau lliwio graffiau, dyraniad cofrestr mewn crynhowyr, ym 1981.

Diffiniad a therminoleg

Gall y graff hwn fod yn 3-lliw mewn 12 ffordd wahanol.

Lliwio fertigau

Pan gaiff ei ddefnyddio heb unrhyw gymhwyster, mae lliwiad graff bron bob amser yn lliwiad fertig cywir, sef labelu fertigau'r graff gyda lliwiau fel nad oes gan unrhyw ddau fertig sy'n rhannu'r un ymyl yr un lliw. Gan na ellid byth lliwio fertig â dolen (hy cysylltiad yn uniongyrchol yn ôl iddo'i hun), deallir bod graffiau yn y cyd-destun hwn yn ddi-ddolen.

Mae'r derminoleg o ddefnyddio lliwiau ar gyfer labeli fertig yn mynd yn ôl i liwio mapiau. Dim ond pan fydd nifer y lliwiau'n fach y defnyddir labeli fel coch a glas, ac fel rheol deallir bod y labeli wedi'u tynnu o'r cyfanrifau {1, 2, 3, ...}.

Gelwir lliwiad sy'n defnyddio k lliw ar y fwyaf yn k-liwiad (cywir). Yr enw ar y nifer lleiaf o liwiau sydd eu hangen i liwio graff G yw ei rif cromatig, ac fe'i dynodir yn aml χ( ). Weithiau defnyddir γ(G), gan fod χ(G) hefyd yn cael ei ddefnyddio i ddynodi nodwedd Euler graff. Mae graff y gellir eu neilltuo k-liwiad (cywir) yn k-liwiadwy, ac mae'n k-cromatig os ei rhif cromatig yw k yn union. Gelwir is-set o fertigau a roddir i'r un lliw yn ddosbarth lliw, mae pob dosbarth o'r fath yn ffurfio set annibynnol. Felly, mae k-liwiad yr un peth â rhaniad y set fertigau i mewn i k setiau annibynnol, ac mae gan y termau k-rhannol a k-liwiadwy yr un ystyr.

Polynomial cromatig

Pob graff nad yw'n isomorffig ar 3 fertig a'u polynomialau cromatig. Mae'r graff gwag E₃ (coch) yn dangos 1-lliwiad, nid yw'r lleill yn dangos unrhyw liwiadau o'r fath. Mae'r graff gwyrdd yn dangos 12 lliwiad gyda 3 lliw.

Mae'r polynomial cromatig yn cyfri'r nifer y ffyrdd y gellir lliwio graff gan ddefnyddio dim mwy na nifer benodol o liwiau. Er enghraifft, gan ddefnyddio tri lliw, gellir lliwio'r graff yn y ddelwedd gyfagos mewn 12 ffordd. Gyda dim ond dau liw, ni ellir ei liwio o gwbl. Gyda phedwar lliw, gellir ei liwio mewn 24 + 4⋅12 = 72 ffordd: gan ddefnyddio'r pedwar lliw, mae yna 4! = 24 lliwiad dilys (mae pob aseiniad o bedwar lliw i unrhyw graff 4-fertig yn lliwiad cywir); ac ar gyfer pob dewis o dri o'r pedwar lliw, mae 12 3-lliwiad dilys. Felly, ar gyfer y graff yn yr enghraifft, byddai tabl o nifer y lliwiau dilys yn dechrau fel hyn:

Lliwiau sydd ar gael	1	2	3	4	…
Nifer o liwiadau	0	0	12	72	…

Mae'r polynomial cromatig yn ffwythiant P(G, t) sy'n cyfri nifer y t-lliwiadau o G. Fel y mae'r enw'n nodi, ar gyfer G penodol, mae'r ffwythiant yn wir yn polynomial yn t. Ar gyfer y graff enghreifftiol, P(G, t) = t(t − 1)²(t − 2), ac yn wir P(G, 4) = 72.

Mae'r polynomial cromatig yn cynnwys o leiaf cymaint o wybodaeth am lliwadwyedd G ag y mae'r rhif cromatig. Yn wir, χ yw'r cyfanrif positif lleiaf nad yw'n wraidd y polynomial cromatig

$\chi (G)=\min\{k\,\colon \,P(G,k)>0\}.$

Polynomialau cromatig ar gyfer rhai graffiau

Triongl K3	$t(t-1)(t-2)$
Graff cyflawn Kn	$t(t-1)(t-2)\cdots (t-(n-1))$
Coed gyda n fertig	$t(t-1)^{n-1}$
Cylch Cn	$(t-1)^{n}+(-1)^{n}(t-1)$
Graff Petersen	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$

Lliwio ymylon

Mae lliwiad ymylon graff yn lliwio'r ymylon yn gywir, sy'n golygu aseinio lliwiau i ymylon fel nad oes fertig yn trawio dwy ymyl o'r un lliw. Gelwir lliwiad ymylon gyda k lliw yn k-lliwiad-ymyl ac mae'n cyfateb i'r broblem rannu'r set ymyl i mewn k-parau. Y nifer lleiaf o liwiau sydd eu hangen er mwyn lliwio ymylon graff G yw'r inedcs cromatig, neu'r rhif cromatig ymylon, χ′(G). Lliwiad Tait yw 3-lliwiad-ymyl graff ciwbig. Mae'r theorem pedwar lliw yn cyfateb i'r honiad bod gan pob graff ciwbig di-bont planar lliwiad Tait.

Lliwio Llwyr

Lliwio llwyr yw fath o liwio ar fertigau ac ymylon graff. Pan gaiff ei ddefnyddio heb unrhyw gymhwyster, tybir bod lliwiad llwyr pob amser yn gywir yn yr ystyr nad oes gan unrhyw fertigau cyfagos, ymylon cyfagos, na unrhyw ymyl a'i fertigau-pen yr un lliw. Rhif cromatig llwyr χ″(G) graff G yw'r nifer lleiaf o liwiau sydd eu hangen mewn unrhyw liwiad llwyr o G.

Cymhwysiadau

Amserlennu

Mae lliwio fertigau yn modelu nifer o broblemau amserlennu. Yn y ffurf glanaf, mae angen neilltuo set benodol o swyddi i slotiau amser, a mae angen un slot ar gyfer pob swydd. Gellir trefnu swyddi mewn unrhyw drefn, ond gall parau o swyddi cael gwrthdariad, hynny yw efallai ni allant cael eu aseinio i'r un slot amser, er enghraifft oherwydd bod y ddau ohonyn nhw'n dibynnu yr un adnodd. Mae'r graff cyfatebol yn cynnwys fertig ar gyfer pob swydd ac ymyl ar gyfer pob pâr o swyddi sy'n gwrthdaro. Rhif cromatig y graff yw'r union gyfnod lleiaf, yr amser gorau posibl i orffen pob swydd heb wrthdaro.

Mae manylion y broblem amserlennu yn diffinio strwythur y graff. Er enghraifft, wrth aseinio awyrennau i hediadau, cawn 'interval graph' fel y graff gwrthdaro, felly gellir datrys y broblem lliwio yn effeithlon. Wrth aseinio lled-band i orsafoedd radio, cawn 'unit disk graph' fel y graff gwrthdaro, felly mae'r broblem lliwio yn 3-frasamcanol.

Aseinio cofrestrau

Rhaglen gyfrifiadurol yw 'compiler' sy'n cyfieithu un iaith gyfrifiadurol i un arall. Er mwyn gwella amser gweithredu'r cod sy'n deillio o hyn, un o dechnegau optimeiddio compiler yw aseinio cofrestrau, lle cedwir gwerthoedd a ddefnyddir amlaf y rhaglen a luniwyd yn cofrestr prosesyddion cyflym. Yn ddelfrydol, rhoddir gwerthoedd i'r gofrestrau fel y gallant i gyd fyw yn yr un cofrestrau lle mae'n nhw'n cael eu defnyddio.

Y dull arferol i datrys y broblem hon yw ei fodelu fel problem lliwiad graff. Mae'r compiler yn llunio graff ymyrraeth, lle mae fertigau yn newidynnau ac mae ymyl yn cysylltu dau fertig os oes eu hangen ar yr un pryd. Os gellir lliwio'r graff â k liw yna gellir storio unrhyw set o newidynnau sydd eu hangen ar yr un pryd yn y mwyafrif o k cofrestr.

Cymhwysiadau eraill

Mae'r broblem o liwio graffio yn codi mewn sawl maes ymarferol fel paru patrymau, amserlennu chwaraeon, dylunio cynlluniau eistedd, amserlennu arholiadau, amserlennu tacsis, a datrys posau Sudoku.