Algoritm för färgförfining

Inom grafteori och teoretisk datavetenskap är färgförfiningsalgoritmen även känd som den naiva vertexklassificeringen , eller den 1-dimensionella versionen av Weisfeiler-Leman-algoritmen, en rutin som används för att testa om två grafer är isomorfa eller inte.

Beskrivning

Vi definierar en sekvens av vertexfärgningar $cr^{t}$ definierade enligt följande:

• $cr^{0}$ är den ursprungliga färgen. Om grafen är omärkt tilldelar den initiala färgningen en trivial färg $cr^{0}(v)$ till varje vertex $v$ . Om grafen är märkt $cr^{0}(v)$ etiketten för vertex $v$ .
• För alla hörn $v$ sätter vi $cr^{t+1}(v)=\left(cr^{t}(v),\{\{cr^{t}(w)\mid w{\text{ är en granne till }}v\ }\}\right)$ . Med andra ord, den nya färgen på vertex $v$ är paret som bildas av den tidigare färgen och multiuppsättningen av färgerna för dess grannar.

Denna algoritm fortsätter att förfina den aktuella färgen. Vid någon tidpunkt, före n steg, där n är antalet hörn, stabiliseras det: $cr^{t}$ ändras inte längre när t ökar. Denna slutliga färgning kallas den stabila färgen .

Expressivitet

Denna algoritm skiljer inte en cykel med längd 6 från ett par trianglar (exempel V.1 in ).

Komplexitet

Den stabila färgen kan beräknas i O((n+m)log n) där n är antalet hörn och m antalet kanter. Denna komplexitet har visat sig vara optimal för vissa klasser av grafer.