Lau koloreen teorema

Grafo teorian, lau koloreen teorema grafoen koloreztatzeari buruzko teorema da. Ondorengoa esaten du:

Edozein mapa geografiko harturik, non eskualde jarraituak dituen (hau da, eskualdeko edozein bi puntu eskualdetik irteten ez den kurba baten bidez lotu daitezke), mapa koloreztatua izan daiteke gehienez lau kolore erabilita, ondoz ondoko eskualdeetan kolore bera erabili gabe.

Onartuko dugu ondoz ondoko eskualdeen mugek, mugaren segmentu bat dutela amankomunean, ez puntu bat soilik.^[1]^[2]

Egia esan, hiru kolore nahiko dira mapa sinpleentzat. Hala ere, mapa konplexuagoa izanez gero, zaila suertatzen da lau kolorerekin margotzea ere. Horregatik, frogatu zen lehen teorema bost koloreen teorema izan zen. Bost koloreen teoremak, bere froga motza eta oinarrizkoa izanik, finkatzen du bost kolore nahiko direla mapa bat koloreztatzeko eta XIX. mendean Heawoodek frogatu zuen.

Lau koloreen teoremari dagokionez, lehen aldiz Francis Guthrie ikasleak proposatu zuen 1852. urtean, eta Augustus de Morgan matematikariari komunikatu. Aierua Arthur Cayleyren deklarazioari esker egin zen famatu 1878an. Urteetan zehar aierua frogatzeko hainbat saiakera egin ziren, 1976. urtean Kenneth Apple eta Wolfgang Hakenek frogatu zuten arte ordenagailu baten laguntzaz. Froga aurkitzeko bide horretan, zenbait ebidentzia eta kontradibide faltsu agertu izan dira lau koloreen teoremaren lehen enuntziatua 1852an argitaratu zenetik. Eta oraindik ez da ordenagailurik gabeko frogarik aurkitu.

Teoremaren adierazpen zehatza

Lehenik, aldi berean hiru eskualde edo gehiagoren parte diren ertz eta puntuak ez ditugu kontuan hartuko. Azken murrizketa hau egin gabe, mapa arraroek lau kolore baino gehiago beharko dituzte.

Bigarrenik, teoremaren helbururako, “herrialde” bakoitza eskualde jarraitua edo sinpleki konexua izan behar da. Praktikan, hau ez da egia (Estatu Batuak, Alaska kontuan hartuta, edo Errusia, Kaliningrad kontuan hartuta, ez dira eskualde jarraituak). Herrialde bakoitzaren eskualdea kolore berekoa izan behar denez, “herrialde” ez jarraituak onartuko balira, posible litzateke lau kolore nahikoak ez izatea. Adibidez, kontsidera dezagun ondoko mapa sinplifikatua:

Mapa honetan, A-z markatutako bi eremuak herrialde beraren parte dira; beraz, kolore bera izan behar dute. Hori dela eta, mapa honek bost kolore beharko ditu. Izan ere, A-z markatutako eremu biak gainontzeko lau eremuen auzokideak dira, eta lau eremu horiek elkarren auzokideak dira. Are gehiago, A-z markatutako hiru eskualde egongo balira, orduan sei kolore edo gehiago beharko lirateke. Antzeko zerbait gertatzen da kolore urdina ura irudikatzeko erabiltzen baldin badugu, irudiaren inguruan itsasoa izango bagenu.

Teoremaren bertsio sinpleago bat eman daiteke, grafoen teoria erabiliz. Mapa baten eskualde multzoa modu abstraktuago batean irudika daiteke, grafo sinple ez-orientatuak erabilita. Horretarako, grafoaren erpin bakoitza maparen eskualde batekin erlazionatzen da; eta ertz bakoitza muga segmentu bat partekatzen duten eskualde pareekin. Erpinekin eta ertzekin egindako maparen irudi hau grafo dual bat da, eta horrela herrialdeak koloreztatze problema grafo koloreztatze problema bilakatzen da. Grafo hau laua da, alegia, plano batean irudika daiteke planoan ertzak elkar ebaki gabe. Irudikapen horretan, erpinen kokapena modu arbitrarioan egiten da, betiere dagokion eremuaren barruan. Grafo teoriaren terminologiarekin, lau koloreen teoremak hurrengoa ezartzen du:

Lau koloreen teorema. ${\textstyle G}$ grafo laua bada, orduan ${\textstyle \chi (G)\leq 4}$ ^[3]

Hau da, grafo lau bakoitzaren erpinak gehien jota lau kolore erabiliz koloreztatu daitezke, auzokideak diren erpinetan kolore bera erabili gabe. x(G)-ri zenbaki kromatiko deritzo.

Historia

Lau koloreen teorema hasiera batean aieru bat besterik ez zen. 1852an, hain zuzen, Francis Guthriek, Augustus De Morganen ikasleak, aieru hura proposatu zuen. Hainbat matematikari saiatu arren, ezin izan zuten aierua frogatu.

1879. urtean, Alfred Bray Kempek aieruaren frogapena bazeukala publikatu zuen Nature aldizkarian. 1890ean, Percy John Heawoodek akats bat aurkitu zuen Kemperen frogapenean. Hala ere, Heawoodek ezin izan zuen aierua errefusatu; baina mapen koloreztatzearen lanean jarraitu zuen eta bost kolorerekin edozein mapa kolorezta daitekeela frogatu.

1976an, azkenean, lau koloreen aierua frogatzea lortu zuten Kenneth Apple eta Wolfgang Hakenek. Kontua da ordenagailua erabili zutela horretarako. Ondorioz, horrek hainbat eztabaida sortu zituen matematikarien artean.^[4]

Frogapen eztabaidatua

Arestian esan bezala, lau koloreen teorema ordenagailu baten laguntzaz frogatu zen. Izan ere, eskuz egitea ezinezkotzat jotzen da. Alabaina, matematikari askok ez dute froga onartzen programa informatikoa ongi egina dagoela onartu behar baita.

Sinplifikazioa eta egiaztapena

Teorema frogatu zutenetik, froga laburragoak eman izan dira, eta algoritmo eraginkorragoak sortu. 1996an exekuzio denbora ordena karratura murriztu zuten: 663 kasu berezi soilik aztertu behar izan zituzten. 2005ean teoremak frogatzeko erabiltzen den programa informatiko batekin frogatu zen.

Frogarekin aurrerapausoak egon badira ere, gaur egun, oraindik ez da lortu froga ordenagailuaren laguntzarik gabe egitea.

Frogapenaren ideiak^[5]

Jarraian lau koloreen teoremaren frogapenaren ideia orokor bat erakutsiko da. Froga honek akats bat badu ere, argi uzten ditu lau koloreen teorema frogatzeko erabiltzen diren ideia garrantzitsuenak. Froga indukzio bidezkoa da, hau da, mapa txikiak koloreztatuko ditugu eta hori erabiliz mapa handiagoak nola koloreztatu azalduko.

Oinarrizko kasu moduan, mapa batek lau nodo (edo lau eskualde) baino gutxiago baditu, argi dago lau kolore baino gutxiagorekin kolorezta daitekeela.

Bestelako kasuan hurrengo lema erabiliko dugu: “grafo lau batek bost edo gutxiagoko gradua duen nodo bat izango du gutxienez”. Honek esan nahi du existitzen dela bost herrialde edo gutxiagorekin muga duen herrialderen bat. Deitu diezaiogun “A” herrialde horri.

Orain, A erpina kontuan hartu gabe, gure mapa koloreztatuko dugu indukzioa erabilita. Ondoren, saiatuko gara A kontuan hartuta mapa berriro koloreztatzen lau koloreen teorema bete dadin.

Lehenik eta behin, ez baditugu lau koloreak erabili A nodoarekin muga duten erpinak koloreztatzeko, soberan daukagun bat erabil dezakegu A-rentzako.

A-ren alboko erpinetan hiru kolore erabili dira: berdea, mostaza eta arrosa. Ondorioz, A soberan dagoen kolorearekin koloreztatu da, urdinarekin, hain zuzen ere.

Bestela, lau koloreak erabili baditugu, hasierako koloreztaketa aldatu beharko dugu kolore bat libratzeko asmoz.

A-ren alboko erpinetan lau koloreak erabili dira: arrosa, berdea, mostaza eta urdina.

Ohartu lau kolore erabili ditugunez, gutxienez lau herrialderekin duela muga A herrialdeak.

Momentuz demagun laurekin duela muga, hau da, A erpinaren gradua lau dela. Horrela baldin bada nodoak zenbakitu ditzakegu erlojuaren noranzkoan batetik laura. Guztiek kolore ezberdinak izango dituzte.

Hartu gure grafoa eta geratu arrosez eta mostazaz koloreztatuta dauden nodoekin. Demagun arrosez koloreztatua dagoen “1” erpina hartzen dugula. Hortik abiatuta demagun nodo sekuentzia bat hasten dela, mostazaz koloreztatua dagoen “3” erpinean bukatzen dena. Esango dugu bi nodoren artean arrosa-mostaza Kemperen bidea dagoela baldin eta konektatutako nodo batetik bestera mugituta, “1” nodotik “3” nodora joateko gai bagara. Bi aukera ditugu grafoa berriro koloreztatzeko kolore bat libratzeko helburuarekin:

1. “1” nodotik “3” nodora arrosa-mostaza Kemperen bidea ez badago. "1”-etik abiatzen diren arrosa-mostaza bide guztietako nodo guztien koloreak truka ditzakegu (arrosak mostazaz eta alderantziz); eta arrosa libratu. Honela kolore bat libratuko dugu eta hori izango da A herrialdearena.

“1” erpinaren kolorea aldatu dugunez (arrosa → mostaza), kolore arrosa libratu dugu eta A erpinari eslei diezaiokegu.

2. “1” nodotik “3” nodora arrosa-mostaza Kemperen bidea baldin badago. Hurrengo irudian gorriz ageri den bezalako bidea izango da. Kasu honetan, lehen bezala arrosa eta mostaza koloreak trukatzen baditugu ohartu ez dela kolorerik libratzen, "1" eta "3" erpinen koloreak trukatzea ez baitugu lortuko. Beste era batera egingo dugu.

"1" eta "3" erpinen koloreak trukatu ditugu (arrosa ↔ mostaza), beraz, ez dugu kolorerik libratu. A-ren ingurunean lau kolore ditugu hasieran bezala.

Aipatutakoa egin beharrean, beste erpinak hartuko ditugu kontuan; hau da, “2” eta “4” erpinekin saiatuko gara prozesu bera errepikatzen. Kasu horretan, grafoa laua denez “2” nodoa isolatuta geratzen da (ezin dira bideak gurutzatu definizioaren arabera). Beraz, ezin da egon berde-urdin biderik “2”-tik “4” nodora; eta “2”-tik hasten diren berde-urdin bideetako nodoen koloreak truka ditzakegu (berdeak urdin eta urdinak berde). Hori eginez gero, berdea libratuko dugu A herrialdearentzat eta bukatu dugu.

“2” erpinaren kolorea aldatu dugunez (berdea → urdina), kolore berdea libratu dugu eta A erpinari eslei diezaiokegu.

A nodoa bost gradukoa bada, aldiz, koloreak errepikatzen dira eta erlojuaren zentzuan nodoak zenbakituz gero, bi kasu ikusten ditugu:

Errepikatuta eta segidan dauden koloreekin aplikatu aurreko estrategia, bidea osatuz. Hori bai, koloreak trukatzerako orduan hautatu beti errepikatuta ez dagoen kolore bat.

Mostaza kolorea errepikatuta dago jarraian, “3” eta “4” erpinetan.

Errepikatuta daudenen artean beste nodo bat dago, kasu honetan dago hasieran aipatutako Kemperen akatsa. Kempek teknika berdina erabiltzen du, baina kasu honetan ez du funtzionatzen; hala ere, aurreko atalekin frogaren ideia nagusiak aurkeztuta geratzen dira.

Erreferentziak

↑ Tierz, Alicia. (2024-07-17). «Alicia Tierz - Redes neuronales de grafos informadas localmente por la termodinámica» Jornada de Jóvenes Investigadores del I3A 12 doi:10.26754/jjii3a.202410884. ISSN 2341-4790. (kontsulta data: 2024-11-28).
↑ Bárcena Petisco, Jon Asier; Merino Maestre, María. (2023). Matematika Diskretua. Servicio Editorial de la Universidad del País Vasco ISBN 978-84-1319-575-9..
↑ Cioabă, Sebastian M.; Murty, M. Ram. (2009). «Basic Notions of Graph Theory» A First Course in Graph Theory and Combinatorics (Hindustan Book Agency): 1–9. ISBN 978-81-85931-98-2. (kontsulta data: 2024-11-28).
↑ Crilly, Tony. (2005-09-22). «Arthur Cayley FRS and the four-colour map problem» Notes and Records of the Royal Society 59 (3): 285–304. doi:10.1098/rsnr.2005.0097. ISSN 0035-9149. (kontsulta data: 2024-11-28).
↑ (Ingelesez) Sipka, Timothy. (2002-11). «Alfred Bray Kempe's “Proof” of the Four-Color Theorem» Math Horizons 10 (2): 21–26. doi:10.1080/10724117.2002.11974616. ISSN 1072-4117. (kontsulta data: 2024-11-28).

Kanpo estekak

Datuak: Q184410
Multimedia: Four-color theorem / Q184410

[1] Tierz, Alicia. (2024-07-17). «Alicia Tierz - Redes neuronales de grafos informadas localmente por la termodinámica» Jornada de Jóvenes Investigadores del I3A 12 doi:10.26754/jjii3a.202410884. ISSN 2341-4790. (kontsulta data: 2024-11-28).

[2] Bárcena Petisco, Jon Asier; Merino Maestre, María. (2023). Matematika Diskretua. Servicio Editorial de la Universidad del País Vasco ISBN 978-84-1319-575-9..

[3] Cioabă, Sebastian M.; Murty, M. Ram. (2009). «Basic Notions of Graph Theory» A First Course in Graph Theory and Combinatorics (Hindustan Book Agency): 1–9. ISBN 978-81-85931-98-2. (kontsulta data: 2024-11-28).

[4] Crilly, Tony. (2005-09-22). «Arthur Cayley FRS and the four-colour map problem» Notes and Records of the Royal Society 59 (3): 285–304. doi:10.1098/rsnr.2005.0097. ISSN 0035-9149. (kontsulta data: 2024-11-28).

[5] (Ingelesez) Sipka, Timothy. (2002-11). «Alfred Bray Kempe's “Proof” of the Four-Color Theorem» Math Horizons 10 (2): 21–26. doi:10.1080/10724117.2002.11974616. ISSN 1072-4117. (kontsulta data: 2024-11-28).

[1]

[2]

[3]

[4]

[5]