Girig färgning - Greedy coloring

Två giriga färgningar av samma krondiagram med olika toppunktsordningar. Rätt exempel generaliserar till tvåfärgbara grafer med n hörn, där den giriga algoritmen expanderar n /2 färger.

I studien av graffärgproblem i matematik och datavetenskap är en girig färgning eller sekventiell färgning en färgning av hörn på en graf som bildas av en girig algoritm som betraktar kurvens hörn i följd och tilldelar varje toppunkt sin första tillgängliga färg . Giriga färgningar kan hittas i linjär tid, men de använder i allmänhet inte det minsta möjliga antalet färger.

Olika val av hörnföljden kommer vanligtvis att ge olika färgningar av den givna grafen, så mycket av studien av giriga färgningar har rört hur man hittar en bra beställning. Det finns alltid en ordning som ger en optimal färgning, men även om sådana ordningar kan hittas för många speciella klasser av grafer, är de svåra att hitta i allmänhet. Vanligt använda strategier för toppunktsbeställning innebär att du placerar högre graders hörn tidigare än lägre graders hörn, eller att välja hörn med färre tillgängliga färger i stället för hörn som är mindre begränsade.

Varianter av giriga färger väljer färgerna på nätet , utan någon kunskap om strukturen på den ofärgade delen av grafen, eller väljer andra färger än de första tillgängliga för att minska det totala antalet färger. Giriga färgalgoritmer har tillämpats för schemaläggning och registerallokeringsproblem , analys av kombinatoriska spel och bevis på andra matematiska resultat inklusive Brooks sats om sambandet mellan färgning och grad. Andra begrepp inom grafteorin som härrör från giriga färgningar inkluderar Grundy-antalet i en graf (det största antalet färger som kan hittas av en girig färgning) och de välfärgade graferna , grafer för vilka alla giriga färgämnen använder samma antal färger.

Algoritm och komplexitet

En girig färgning för en given toppunktsordning kan beräknas av en algoritm som löper i linjär tid med avseende på antalet hörn och kanter i grafen. Algoritmen bearbetar hörnen i den angivna ordningen och tilldelar var och en en färg i tur och ordning. Färgerna kan representeras av siffrorna , och varje hörnpunkt får den färg med det minsta antalet som inte redan används av en av dess grannar. ${\ displaystyle 0,1,2, \ dots}$

Ett effektivt sätt att bestämma den minsta tillgängliga färgen för en toppunkt är att använda en uppsättning booleska variabler som kallas . Inledningsvis är alla element i inställda på False. Med tanke på en ofärgad topp , betraktar vi nu alla grannar till och, om den redan har tilldelats en färg , är den inställd på True. I nästa steg skannar vi sedan för att identifiera det första falska elementet. Indexet för detta element motsvarar den lägsta möjliga färgen för . Slutligen måste alla element i återställas till False. ${\ displaystyle used}$${\ displaystyle used}$${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle j}$${\ displaystyle used [j]}$${\ displaystyle used}$${\ displaystyle v}$${\ displaystyle used}$

I Python kan denna algoritm uttryckas enligt följande. Ett exempelkörning med en liten graf ingår längst ner i koden:

def get_first_feasible_color(v, G, used, c):
	for u in G[v]:
		if c[u] != -1:
			used[c[u]] = True
	for j in range(len(used)):
		if used[j] == False:
			break
	for u in G[v]:
		if c[u] != -1:
			used[c[u]] = False
	return j
	
def greedy_color(G, order):
	#Determines a greedy coloring of the graph G in the order given by the list "order"
	c = [-1 for i in range(len(G))]
	used = [False for i in range(len(G))]
	for v in order:
		c[v] = get_first_feasible_color(v, G, used, c)
	return c

"""
An example run of the greedy algorithm for graph coloring. Here, the vertices of the graph
assume the labels 0, 1, 2, .... The graph G is then represented by an adjacency list.
This means that G[v] defines a list containing the neighbors of vertex v. 
	
In the following example, G is a cycle graph on five vertices. The vertex order is simply
[0, 1, 2, 3, 4]. The return value of the greedy_color procedure is a list where c[v]
gives the color of vertex v. Colors use the labels 0, 1, 2, upwards.
"""
G = [[1, 4], [0, 2], [1, 3], [2, 4], [0, 3]]
order = [0, 1, 2, 3, 4]
c = greedy_color(G, order)
print(c)

Med hjälp av det givna exemplet producerar denna kod utmatningen . Detta tolkas som att toppunkt 0 tilldelas färg 0; toppunkt 1 tilldelas färg 1; toppunkt 2 tilldelas färg 0; toppunkt 3 tilldelas färg 1; och toppunkt 4 tilldelas färg 2. Lösningen använder därför totalt tre färger. ${\ displaystyle [0,1,0,1,2]}$

I denna kod get_first_feasible_colortar proceduren tid i proportion till antalet grannar till . Detta beror på att den utför två slingor över uppsättningen av grannar och en slinga för att identifiera en lämplig färg (den senare tar maximalt steg, var är antalet hörn som granne ). Dessutom måste först ställa in alla hörn som ofärgade (med färgetiketten -1 här) och alla element av till False. Den övergripande algoritmen har därför en komplexitet var var antalet hörn i grafen och är antalet kanter i grafen. ${\ displaystyle v}$${\ displaystyle x+1}$${\ displaystyle x}$${\ displaystyle v}$greedy_color${\ displaystyle used}$${\ displaystyle O (n+m)}$${\ displaystyle n}$${\ displaystyle m}$

Val av beställning

Olika ordningar av hörn i en graf kan få den giriga färgen att använda olika antal färger, allt från det optimala antalet färger till, i vissa fall, ett antal färger som är proportionellt mot antalet hörn i grafen. Till exempel ett krondiagram (en graf som bildas av två olika uppsättningar av n /2 hörn { a ₁ , a ₂ , ... } och { b ₁ , b ₂ , ... } genom att ansluta en _i till b _j när som helst i ≠ j ) kan vara ett särskilt dåligt fall för girig färgning. När toppunkten beställer a ₁ , b ₁ , a ₂ , b ₂ , ... kommer en girig färgning att använda n /2 färger, en färg för varje par ( a _i , b _i ) . Det optimala antalet färger för denna graf är dock två, en färg för hörnen a _i och en annan för hörnen b _i . Det finns också grafer så att med hög sannolikhet leder en slumpmässigt vald toppunktsordning till ett antal färger som är mycket större än minimumet. Därför är det av viss vikt vid giriga färger att välja toppunkten ordentligt.

Bra beställningar

Hörnen i valfri graf kan alltid ordnas på ett sådant sätt att den giriga algoritmen ger en optimal färgning. Med tanke på vilken optimal färg som helst kan man ordna hörnen efter deras färger. När man sedan använder en girig algoritm med denna ordning är den resulterande färgen automatiskt optimal. Eftersom optimal graffärgning är NP-komplett , är dock alla delproblem som skulle göra det möjligt att lösa detta problem snabbt, inklusive att hitta en optimal beställning för girig färgning, NP-hårda .

I intervalldiagram och ackordgrafer , om hörnen är ordnade i motsats till en perfekt elimineringsordning , kommer de tidigare grannarna till varje hörn att bilda en klick . Denna egenskap gör att den giriga färgen ger en optimal färgning, eftersom den aldrig använder fler färger än vad som krävs för var och en av dessa klickningar. En eliminationsordning kan hittas i linjär tid, när den existerar.

Mer starkt är att varje perfekt eliminationsordning är ärftligt optimal , vilket betyder att den är optimal både för grafen själv och för alla dess inducerade subgrafer . De perfekt ordningsbara graferna (som inkluderar ackordgrafer , jämförbarhetsgrafer och avståndsärftliga grafer ) definieras som graferna som har en ärftligt optimal ordning. Att känna igen perfekt beställbara grafer är också NP-komplett.

Dåliga order

Antalet färger som produceras av den giriga färgen för den sämsta ordningen av en given graf kallas dess Grundy -nummer . Precis som det är svårt att hitta en bra hörnbeställning för girig färgning, så är det också att hitta en dålig hörnordning. Det är NP-komplett för att bestämma, för en given graf G och tal k , om det finns en ordning av hörn för G som får den giriga algoritmen att använda k eller fler färger. I synnerhet innebär detta att det är svårt att hitta den värsta beställning för G .

Diagram för vilka ordningen är irrelevant

De välfärgade graferna är graferna för vilka alla vertexfärgningar ger samma antal färger. Detta antal färger, i dessa grafer, är lika med både det kromatiska talet och Grundy -talet. De inkluderar cographs , som är exakt de grafer där alla inducerade subgrafer är välfärgade. Det är dock co-NP-komplett för att avgöra om en graf är välfärgad.

Om en slumpmässig graf ritas från Erdős – Rényi -modellen med konstant sannolikhet att inkludera varje kant, leder varje toppunktsordning som väljs oberoende av grafkanterna till en färgning vars antal färger är nära två gånger det optimala värdet, med hög sannolikhet . Det är fortfarande okänt om det finns någon polynomisk tidsmetod för att hitta signifikant bättre färgningar av dessa grafer.

Degeneration

Det triangulära prisma och kvadratiska antiprismen, grafer vars giriga färgningar med hjälp av degenerationsordningen ger större än optimalt antal färger

Eftersom optimala toppunktsbeställningar är svåra att hitta har heuristik använts som försöker minska antalet färger samtidigt som det inte garanterar ett optimalt antal färger. En vanligt förekommande beställning för girig färgning är att välja en toppunkt v av minsta grad , beställa subgrafen med v borttagen rekursivt och sedan placera v sist i beställningen. Den största graden av en borttagen toppunkt som denna algoritm stöter på kallas grafens degeneration , betecknad d . I samband med girig färgning kallas samma beställningsstrategi också för den minsta sista beställningen. Denna toppunktsordning och degenerationen kan beräknas i linjär tid. Det kan ses som en förbättrad version av en tidigare toppunktsbeställningsmetod, den största första ordningen, som sorterar hörnen i fallande ordning efter deras grader.

Med degenerationens ordning kommer den giriga färgen att använda högst d  + 1 färger. Detta beror på att varje hörn, när den är färgad, har högst d redan grannfärgade grannar, så en av de första d  + 1- färgerna är gratis att använda. Girig färgning med degenerationsordningen kan hitta optimala färgämnen för vissa klasser av grafer, inklusive träd, pseudoforest och krongrafer. Markossian, Gasparian & Reed (1996) definierar en graf för att vara perfekt om, för och varje inducerad subgraf av , det kromatiska talet är lika med degenerationen plus en. För dessa grafer är den giriga algoritmen med degenerationsordningen alltid optimal. Varje -perfekt graf måste vara en jämn -hål -fri graf , eftersom även cykler har kromatisk nummer två och degeneration två, inte matchar jämlikheten i definitionen av -perfekt diagram. Om en graf och dess komplementgraf är båda jämna hålfria är de båda perfekta. Graferna som är både perfekta grafer och perfekta grafer är exakt ackordgraferna . På jämna hålfria grafer mer allmänt, approximerar degenereringen som ordnar den optimala färgen till högst två gånger det optimala antalet färger; det vill säga dess approximationsförhållande är 2. På enhetsdiskgrafer är dess approximationsförhållande 3. Det triangulära prisma är det minsta diagram för vilket en av dess degenerationsordningar leder till en icke-optimal färgning, och den kvadratiska antiprismen är den minsta grafen som kan inte färgas optimalt med någon av dess degenerationsbeställningar. ${\ displaystyle G}$${\ displaystyle \ beta}$${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle \ beta}$${\ displaystyle \ beta}$${\ displaystyle \ beta}$${\ displaystyle \ beta}$

Adaptiva beställningar

Brélaz (1979) har föreslagit en strategi, kallad DSatur , för toppunktsordning i girig färgning som blandar ihop ordningens konstruktion med färgprocessen. I den här versionen av den giriga färgalgoritmen väljs nästa toppunkt för att färga i varje steg som den med det största antalet distinkta färger i sitt grannskap . Vid bindningar väljs en toppunkt med maximal grad i subgrafen för ofärgade hörn från de knutna hörnen. Den övergripande komplexiteten i detta tillvägagångssätt är , även om bättre prestanda för glesa grafer kan uppnås med hjälp av en implementering, där är antalet hörn i grafen och antalet kanter. ${\ displaystyle O (n^{2})}$${\ displaystyle O ((n+m) \ log n)}$${\ displaystyle n}$${\ displaystyle m}$

Denna metod kan hitta de optimala färgämnena för bipartitgrafer ,, kaktusgrafer , hjulgrafer , cykeldiagram , alla grafer på högst sex hörn. Även om Lévêque & Maffray (2005) ursprungligen hävdade att denna metod hittar optimala färgämnen för Meyniel -graferna , hittade de senare ett motexempel på detta påstående.

Alternativa färgval

Det är möjligt att definiera variationer av den giriga färgalgoritmen där hörnen på den givna grafen är färgade i en given sekvens men där den färg som valts för varje hörn inte nödvändigtvis är den första tillgängliga färgen. Dessa inkluderar metoder där den ofärgade delen av grafen är okänd för algoritmen, eller där algoritmen ges viss frihet att göra bättre färgval än den grundläggande giriga algoritmen skulle.

Urval online

Alternativa färgvalstrategier har studerats inom ramen för onlinealgoritmer . I onlinegraffärgningsproblemet presenteras hörn i en graf ett i taget i godtycklig ordning till en färgalgoritm; algoritmen måste välja en färg för varje hörn, baserat enbart på färgerna på och adjacenser bland redan bearbetade hörn. I detta sammanhang mäter man kvaliteten på en färgvalsstrategi utifrån dess konkurrensförhållande , förhållandet mellan antalet färger den använder och det optimala antalet färger för det givna diagrammet.

Om inga ytterligare restriktioner för grafen ges är det optimala konkurrensförhållandet endast något underlinjärt. För intervalldiagram är emellertid ett konstant konkurrensförhållande möjligt, medan för tvåpartsdiagram och glesa diagram kan ett logaritmiskt förhållande uppnås. Faktum är att för glesa grafer uppnår den standardiserade giriga färgstrategin att välja den första tillgängliga färgen detta konkurrenskraftiga förhållande, och det är möjligt att bevisa en matchande nedre gräns för konkurrensförhållandet för valfri online -färgalgoritm.

Parsimonous färgning

En parsimonisk färgning , för en given graf och toppunktsordning, har definierats som en färgning som produceras av en girig algoritm som färgar hörnen i den givna ordningen och introducerar bara en ny färg när alla tidigare färger ligger intill den givna hörnpunkten, men kan välja vilken färg som ska användas (istället för att alltid välja den minsta) när den kan återanvända en befintlig färg. Det beställda kromatiska talet är det minsta antalet färger som kan erhållas för den angivna ordningen på detta sätt, och det okromatiska talet är det största ordnade kromatiska talet bland alla hörnfärgningar i en given graf. Trots dess olika definition är ockromatiska talet alltid lika med Grundy -talet.

Ansökningar

Eftersom det är snabbt och i många fall kan använda få färger, kan giriga färgningar användas i applikationer där en bra men inte optimal graffärgning behövs. En av de tidiga tillämpningarna av den giriga algoritmen var problem som kursschemaläggning, där en samling uppgifter måste tilldelas en viss uppsättning tidsluckor, så att inkompatibla uppgifter inte tilldelas samma tidslucka. Den kan också användas i kompilatorer för registerallokering genom att tillämpa den på en graf vars hörn representerar värden som ska tilldelas register och vars kanter representerar konflikter mellan två värden som inte kan tilldelas samma register. I många fall är dessa störningsgrafer ackordgrafer , vilket gör att giriga färger kan ge en optimal registertilldelning.

I kombinatorisk spelteori , för ett opartiskt spel som ges i uttrycklig form som ett riktat acykliskt diagram vars hörn representerar spelpositioner och vars kanter representerar giltiga rörelser från en position till en annan, den giriga färgalgoritmen (med omvänd av en topologisk ordning av grafen ) beräknar nim-värdet för varje position. Dessa värden kan användas för att bestämma optimalt spel i varje enskilt spel eller någon disjunktiv summa av spel.

För en graf med maximal grad Δ , kommer varje girig färgning att använda högst Δ + 1 färger. Brooks sats säger att med två undantag ( klickningar och udda cykler ) krävs högst Δ färger. Ett bevis på Brooks sats innefattar att hitta en toppunktsordning där de två första hörnen ligger intill slutpunkten men inte intill varandra, och varje annan topppunkt än den sista har minst en senare granne. För en beställning med den här egenskapen använder den giriga färgalgoritmen högst Δ färger.

Anteckningar

externa länkar

• Högpresterande graffärgningsalgoritmer Svit med graffärgningsalgoritmer (implementerade i C ++) som används i boken A Guide to Graph Coloring: Algorithms and Applications (Springer International Publishers, 2021).

Referenser