Grafo koloreztaketa

Grafo teorian, grafo baten koloreztaketa grafoko elementuak (erpinak edo ertzak) hainbat baldintzapean koloreztatu edo bereizteko erabiltzen da. Erpinen koloreztaketan ondokoak diren erpinak kolore ezberdinez margotu behar dira. Ertzen koloreztaketan berriz ondokoak diren ertzak dira kolore ezberdinez margotu beharrekoak. Grafo bateko aldeei buruz ere koloreztaketa ebazkizunak planteatzen dira. Erpinen koloreztaketa da ordea ebazkizun nagusia, beste koloreztaketa guztiak erpinen koloreztaketaz ebatzi ahal izaten baitira. Grafo koloreztaketak aplikazio zabalak ditu plangintza arloan. Koloreen ordez, zenbakiak edo bestelako ikurrak ere jarri daitezke, baina koloreak erabili ohi dira, historian zehar grafo koloreztaketak mapak koloreztatzeko lau koloreen teoremarekin lotu zirelako.

Erpinen koloreztaketa

Eskuarki, erpinen koloreztaketan ondokoak diren puntu edo erpinak kolore ezberdinez margotu behar dira. Bukleak dituzten grafoak baldintza hori betez koloreztatu ezin daitezkeenez, buklerik gabeko grafoetarako egiten da koloreztaketaren azterketa. Baldintza beteaz k kolore erabiltzen direnean, k-koloreztaketa burutu dela esaten da eta grafoa k-koloreztagarria dela esaten da. Ondoko erpinak kolore ezberdinez margotuz betiere, G grafoko erpinak koloreztatzeko behar den kolore kopuru minimoari χ(G) zenbaki kromatikoa deritzo.

**Handiena lehenengo algoritmoa**ren bitartez, eta erpinen bi orden ezberdin erabiliz, grafo baterako bi koloreztaketa ezberdin. Ezkerrekoak zenbaki kromatikoa ematen du: 2. Eskubikoak 4 kolore erabiltzen ditu.

Erpinak koloreztatzeko metodo ezberdinak daude. Ohizko metodo bat algoritmo irenskorra den handiena lehenengo algoritmoa da. Algoritmo honetan, erpinak mailari buruz sailkatu eta ordena horretan ondokoak ez diren erpinak lehenengo koloreaz margotzen dira, gainerako erpinak, ondokoak ez badira, ordena berean bigarren kolore batez margotzen dira, eta abar, erpin guztiak margotu arte. Algoritmoak zenbaki kromatikoa edo handiagoa den kolore kopuru bat ematen du, baina bada erpinen ordenaren bat, algoritmoa erabiliz grafoaren zenbaki kromatikoa ematen duena. Beste erpin ordenetarako ordea, handiena lehenengo algoritmoak zenbaki kromatikoa gainditzen duen kolore kopurua ematen du.

Erpinen koloreztaketa lan plangintzarako erabil daiteke. Adibidez, egin beharreko lan batzuk aldi ezberdinetan kokatu behar badira, lanak edozein ordenetan buru daitezkeela, bateraezintasunak sor daitezke aldi berean egin daitezkeen lanei buruz, bi lanek baliabide bera behar dutelako esaterako. Lanak burutzeko denbora laburrena jakiteko, egin beharreko lan bakoitzeko erpin bat sortzen da, bi lan batera burutu ezin badirenean dagozkien bi erpinak ertz batez lotuz. Horrela sortzen den grafoaren zenbaki kromatikoa da lanak burutzeko denbora laburrena, kolore bereko erpinak izanik aldi berean egin daitezkeen lanak.

Ertzen koloreztaketa

Ebazkizun batzuetarako planteamendua erosoagoa da ondokoak diren ertzak kolore ezberdinez margotu behar direla ezarriz. Ertzak horrela koloreztatzeko behar den kolore kopuru minimoari indize kromatiko deritzo eta honela adierazten da: χ'(G).

Indize kromatikoa grafoko puntuetako maila handienarekin edo maila handiena gehi bat zenbakiarekin dator bat, Vizing-en teoremaren arabera.

Ertzen koloreztaketak enparejamendu ebazkizunetan erabiltzen dira, puntu edo erpin ezberdinen artean grafoak ahalbideratzen dituen enparejamendu edo ertzak kokatzeko era kopurua zenbatzeko, alde biko grafoetan askotan. Adibidez, grafo batean puntuak jokalariak izanik eta ertzek jokalarien artean jokatu beharreko partiduak adierazten badituzte, indize kromatikoak partiduak jokatzeko egun kopurua adierazten du, jokalari batek egun batean partidu bakarra jokatzen badu.

Kanpo estekak

Datuak: Q504843
Multimedia: Graph coloring / Q504843