Lankide:Unax Cañaveras/Proba orria

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

“Edozein mapa geografiko harturik, non eskualde jarraituak (hau da, eskualdeko edozein bi puntu eskualdetik irteten ez den kurba baten bidez lotu daitezke) dituen, 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 koloreekin 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. Appel eta Hakenek froga 1997an hobetu zuten, eta frogapena 663 kasutara murriztu. 2005ean teoremak frogatzeko erabiltzen den programa informatiko batekin frogatu zen. Zenbait ebidentzia eta kontradibide faltsu agertu izan dira lau koloreen teoremaren lehen enuntziatua 1852an argitaratu zenetik.

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 bat 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, Francis Guthriek, Augustus De Morganen ikasleak, aieru hura proposatu zuen; hainbat matematikari saiatu arren, ezin izan zuten aieru frogatu.

1879an Alfred Bray Kempek aieruaren frogapena zeukala publikatu zuen Nature aldizkarian. 1890ean, Percy John Heawoodek akats bat aurkitu zuen Kemperen frogapenean. Hala ere, Heawoodek ezin izan zuen aierua errefusatu; baina mapak koloreztatzeko lanean jarraitu zuen eta bost kolorerekin edozein mapa kolorezta daitekela frogatu.

1976an aierua frogatu zuten Kenneth Apple eta Wolfgang Hakenek, ordenagailua erabili zuten horretarako. Eta horrek hainbat eztabaida sortu zituen matematikarien artean.^[4]

Frogapen eztabaidatua

Lau koloreen teorema ordenagailu baten laguntzaz frogatu zen. Eskuz egitea ezinezkotzat jotzen denez; matematikari askok ez dute froga onartzen programa informatikoa ongi egina dagoela onartu behar baita.

Simplifikazioa eta egiaztapena

Teorema frogatu zutenetik orainerarte froga laburragoak eman dira, eta algoritmo eraginkorragoak sortu. 1996an exekuzio denbora orden karratura murriztu zuten. 663 kasu berezi soilik aztertu behar izan zituzten.

Frogapenaren ideiak^[5]

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 eskualde) baino gutxiago baditu; lau kolore baino gutxiagorekin kolorezta daiteke (hartu erabili ez duzun baten bat).

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

Orain A kontuan hartu gabe gure mapa koloreztatzen dakigula suposatuko dugu. Ondoren, saiatuko gara A kontuan hartuta mapa berriro koloreztatzen lau koloreen teorema bete dadin.

Lehenik eta behin, ez baditugu lau koloreak erabili, soberan daukagun bat erabili dezakegu A nodoarekin muga duten erpinak koloreztatzeko (ikusi 1. irudia). Bestela, lau koloreak erabilita daudelarik, hasierako koloreztaketa aldatu beharko dugu kolore bat libratzeko asmoz.

Ohartu lau kolore erabili ditugunez, gutxienez lau herrialderekin duela muga A herrialdeak. Momentuz demagun laurekin duela muga. Horrela baldin bada nodoak zenbakitu ditzakegu erlojuaren noranzkoan batetik laura. Guztiek kolore ezberdinak izango dituzte. Hartu gure grafoa eta geratu morez eta mostazaz koloreztatuta dauden nodoekin. Demagun morez koloreztatua dagoen erpina hartzen dugula. Hortik abiatuta demagun nodo sekuentzia bat hasten dela, mostazaz koloreztatua dagoen erpinean bukatzen dena. Esango dugu bi nodoren artean more-mostaza Kemperen bidea dagoela baldin eta konektatutako nodo batetik bestera mugituta nodo batetik bestera joateko gai bagara grafo berrian. Bi aukera ditugu grafoa berriro koloreztatzeko kolore bat libratzeko helburuarekin:

1. “1” nodotik “3” nodora more-mostaza Kemperen bidea ez badago. “1” ekin more-mostaza bidea duten nodo guztien koloreak truka ditzakegu (moreak mostazaz eta alderantziz); eta morea libratu (begiratu 2. irudia). Honela kolore bat libratuko dugu eta hori izango da A herrialdearena.

2. Bidea existituko balitz beheko irudian gorriz marraztutakoa bezalakoa litzateke. Beraz, “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 den berde-urdin bidea duten nodoen koloreak truka ditzakegu (berdeak urdin eta urdinak berde). Hori eginez gero, berdea libratuko dugu A herrialdearentzat eta bukatu dugu.

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

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

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

Bibliografia

↑ 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. (Noiz kontsultatua: 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. (Noiz kontsultatua: 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. (Noiz kontsultatua: 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. (Noiz kontsultatua: 2024-11-28).

[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. (Noiz kontsultatua: 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. (Noiz kontsultatua: 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. (Noiz kontsultatua: 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. (Noiz kontsultatua: 2024-11-28).

[1]

[2]

[3]

[4]

[5]