Colorarea cografurilor folosinddescompunerea modulara

Cristian Frasinaru

acf@infoiasi.ro

Facultatea de Informatica

Universitatea Al. I. Cuza Iasi

1

Cuprins

1 Descompunerea modulara 31.1 Definitii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Algoritmul brut . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Algoritmi liniari . . . . . . . . . . . . . . . . . . . . . . . . . . 91.4 Recunoasterea cografurilor . . . . . . . . . . . . . . . . . . . . 9

2 Colorarea cografurilor 112.1 Ideea algoritmului . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 Algoritmul de colorare a cografurilor . . . . . . . . . . . . . . 112.3 Corectitudinea . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.4 Complexitatea . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2

1 Descompunerea modulara

1.1 Definitii

Numim modul al unui graf neorientat G = (V,E) o multime de varfuri Mpentru care orice varf din V M fie este adiacent cu toate varfurile din M ,fie nu este adiacent cu nici unul.

V , si {v},v V se numesc module triviale.Un graf care nu are decat module triviale se numeste graf prim.Un modul care nu intersecteaza strict un alt modul (dar poate contine sau ficontinut n altul) se numeste modul tare. Un modul slab este un modul carenu este tare.Notam M(G) familia tuturor modulelor unui graf G.

Doua multimi se suprapun daca ele se intersecteaza dar nici una nu estecontinuta n cealalta. Spunem ca un nod v distinge doua alte varfuri u,wdaca este adiacent cu unul dintre ele dar nu cu amandoua. Varfurile u,wsunt n acord asupra lui v daca v nu distinge ntre u si w.O definitie echivalenta a unui modul este: M este modul al unul graf G dacanici un varf v V (G)M nu distinge ntre oricare doua varfuri m,m M .

Teorema 1 ([12]) FamiliaM(G) a modulelor unui graf neorientat are urmatoareaproprietati:

trivial V M(G), M(G) si v V {v} M(G) intersectie M N M(G),N,M M(G). reuniune M N M(G),N,M M(G), cu N M 6= . diferenta M N M(G),M N M(G)N,M M(G), cu pro-prietatea ca M si N se suprapun.

Descompunerea modulara a unui graf este un proces recursiv de construirea modulelor tari ale lui G, care porneste de la modulul trivial V si se vatermina cu obtinerea tuturor modulelor triviale corespunzatoare varfurilorgrafului. La pasul recursiv, pentru fiecare modulM deja construit, se executaurmatoarea operatie:

1. Daca G[M ] nu este conex, M va fi descompus n componentele conexeale lui G[M ];

3

2. Daca G[M ] nu este conex, S va fi descompus n componentele conexeale lui G[M ];

3. Daca M nu se ncadreaza n primele doua cazuri, atunci l vom numimodul prim. In aceasta situatie, vom descompune M n submoduleproprii maximale. Se poate demonstra ca orice varf al unui modulprim nu poate apartine decat unui singur submodul propriu maximal,deci descompunerea este unica.

Algoritmul de mai sus permite construirea unui arbore, numit si arborelede descompunere modulara, n care fiecare nod corespunde unui modul tare allui G, frunzele arborelui fiind multimile singleton date de varfurile grafului.In functie de cele trei situatii descrise mai sus, nodurile interne ale arboreluivor fi etichetate astfel:

1. paralel

2. serie

3. prim

Primele doua tipuri de noduri se mai numesc si degenerate.

Teorema 2 ([12]) Orice modul al unui graf G este fie modul tare, fie reuni-unea varfurilor corespunzatoare unei submultimi a fiilor unui nod degenerat.

Arborele de descompunere modulara este unic pentru un graf dat si oferao reprezentare n O(|V |) spatiu pentru modulele unui graf.

1.2 Algoritmul brut

Fie G = (V,E) graful pe care dorim sa-l descompunem.Cazul 1.

Daca G nu este conex, descompunem graful n componentele sale conexe,altfelDaca G nu este conex, descompunem graful n componentele conexe ale lui G.

Cazul 2.Suntem n situatia candG si G sunt conexe.

4

Pentru fiecare pereche de varfuri x, y se poate gasi usor, n O(n+m), mod-ulul minimal M care le contine. Descompunem apoi graful (G M) x sinlocuim pe x cu descompunerea recursiva a lui M .

Analizand complexitatea algoritmului observam ca, n cazul 2, avem nevoiede O(n2m) operatii pentru a descompune graful. Complexitatea totala a al-goritmului este deci O(n3m).

Listing 1: Algoritmul brut de descompunere modulara

import graph .*;import graph.algorithms .*;import graph.layout .*;import java.util .*;

public class ModularDecomposition extends Algorithm {Graph tree = null;Node root = null;public Tree getTree () {

execute ();return new Tree(tree , root);

}

public int execute () {Graph g = getGraph ();tree = new Graph();

decompose(g, null);

if (isVisual ()) {getWorkspace ().setGraph(tree , "");TreeLayout tl = new TreeLayout ();tl.setGraph(tree);tl.execute ();

}return 0;

}

public Node addNode(Node parent) {Node node = new Node();tree.add(node);

if (parent != null)tree.add(new Edge(parent , node));

5

return node;}

public void decompose(Graph g, Node parent) {// Descompune V(G) si adauga arborele rezultat

//ca subarbore al lui parent

if (isStopped ())return;

Node node=null;

if (g.N() == 1) {Node v = g.node (0);node = addNode(parent);node.setLabel(v.getLabel ());node.setData(new Integer(v.getId ()));node.setFillColor(v.getFillColor ());return;

}

ConnectedComponents alg = new ConnectedComponents ();alg.setGraph(g);

if (!alg.isConnected ()) {node = addNode(parent);if (root == null)

root = node;node.setLabel("Paralel");node.setData("Paralel");node.setWidth (60);Set blocks = alg.components ();for(Iterator it=blocks.iterator (); it.hasNext ();) {

NodeSet cc = (NodeSet) it.next();decompose(g.subgraph(cc), node);

}

return;}

alg.setGraph(g.complement ());if (!alg.isConnected ()) {

node = addNode(parent);if (root == null)

root = node;

6

node.setLabel("Serie");node.setData("Serie");node.setWidth (60);Set blocks = alg.components ();for(Iterator it=blocks.iterator (); it.hasNext ();) {

NodeSet cc = (NodeSet) it.next();decompose(g.subgraph(cc), node);

}return;

}

NodeSet M = null;Node x=null , y=null;boolean found = false;

for(int i=0; i

node.setWidth (60);

for(int i=0; i 0 && q < M.size()) {

M.add(u);nodes.remove(u);nodes.iterate ();

}}

nodes = g.nodes();nodes.iterate ();while (nodes.hasNext ()) {

Node u = nodes.next();if (M.contains(u))

continue;NodeSet M1 = M.adjacentNodes ();M1.remove(u);

NodeSet M2 = u.adjacentNodes ();M2.removeAll(M);

if (M1.equals(M2))M.add(u);

8

}return M;}

}

1.3 Algoritmi liniari

In [5], [8], [9] sunt prezentati algoritmi pentru descompunerea modulara aunui graf avand complexitatea O(n+m).

1.4 Recunoasterea cografurilor

Un cograf este un graf care nu contine nici un P4 indus. Clasa cografurilorpoate fi caracterizata ca fiind cea mai mica clasa de grafuri ce contine gra-ful cu un singur varf si este nchisa la operatiile de reuniune disjuncta sicomplement. Pornind de la aceasta caracterizare avem urmatorul rezultat:

Teorema 3 ([4]) Un graf G este cograf daca si numai daca arborele de de-scompunere modulara al lui G nu contine nici un nod prim (contine doarnoduri serie si paralele).

Listing 2: Recunoasterea cografurilor

import graph .*;import graph.algorithms .*;import graph.layout .*;import java.util .*;

public class CographRecognition extends Algorithm {

public int execute () {

ModularDecomposition md = new ModularDecomposition ();md.setGraph(getGraph ());Tree tree = md.getTree ();

if (tree.findNode("Prim") != null)println("NOT COGRAPH");

else

9

println("COGRAPH");

return 0;}

}

10

2 Colorarea cografurilor

2.1 Ideea algoritmului

Dupa cum am vazut, arborele de descompunere modulara al unui cograf nucontine decat noduri serie sau paralele. Pe baza acestei proprietati putemcontrui un algoritm de colorare pentru un cograf care sa ruleze n timp liniar.

Fie G un cograf si T arborele de descompunere modulara asociat. Fiecarenod M T corespunde unui modul tare al grafului G. Sa notam M1, ...,Mkfii nodului M din arborele T , presupunand ca M nu este nod frunza. Deasemenea, vom nota G[M ] subgraful indus n G de nodurile frunza ale sub-arborelui lui T cu radacina M . Ideea algoritmului se bazeaza pe urmatoarelerelatii:

1. Daca M este nod paralel atunci:

(G[M ]) = maxi=1..k((G[Mi]))

2. Daca M este nod serie atunci:

(G[M ]) = sumi=1..k((G[Mi]))

2.2 Algoritmul de colorare a cografurilor

Algoritmul de colorare a cografurilor se va desfasura n doua etape.

Etapa 1: Construirea arborelui de descompunere modulara T core-spunzator grafului de intrare G . In cazul n care T contine un nodetichetate Prim atunci algoritmul se va opri, G nefiind cograf.

Etapa 2: Parcurgerea arborelui ncepand cu radacina, colorarea nodurilorfrunza si determinarea lui (G).

Modul de realizare al primei etape a fost analizat n sectiunea anterioara.Sa vedem n continuare cum putem parcurge eficient arborele T pentru aobtine o colorare a nodurilor frunza din arbore care sa induca o colorareoptima a grafului G.

Invariantul algoritmului va fi:Fie M nodul din arborele T de la pasul curent. Atunci toate nodurile an-terioare lui M dintr-o parcurgere preordine a arborlui T au fost analizate

11

iar nodurile frunza corespunzatoare acestora colorate. Mai mult, colorareacurenta reprezinta o colorare optima a subgrafului lui G indus de nodurilecolorate deja.

Listing 3: Algoritm pentru colorarea unui cograf

import graph .*;import graph.algorithms .*;import java.util .*;import java.awt .*;

public class CographColoring extends Algorithm {Graph g;private static Color colors [];

public int execute () {

g = getGraph ();int n = g.N();

// Apelam algoritmul de descompunere modulara

ModularDecomposition md = new ModularDecomposition ();md.setGraph(g);Tree tree = md.getTree ();

if (tree.findNode("Prim") != null) {println("Nu este cograf!");return -1;

}

/* Pregatim un set de culori pe care le vom

folosi pentru colorarea efectiva a nodurilor */

colors = new Color[n];for(int i=0; i

/* Metoda coloreaza subarborele cu radacina ,

folosind culori incepand cu numarul si

returneaza numarul minim de culori necesare */

public int color(Node node , int k) {

int nc = 0;NodeSet kids = node.children ();

// Nod paralel

if (node.getData ().equals("Paralel")) {int max = 0;for(int i=0; i < kids.size(); i++) {

nc = color(kids.node(i), k);if (nc > max)

max = nc;}return max;

}

// Nod serie

if (node.getData ().equals("Serie")) {int suma = 0;for(int i=0; i < kids.size(); i++) {

Node kid = kids.node(i);nc = color(kid , k + suma);suma += nc;

}return suma;

}

// Frunza

// Aflam nodul corespondent din graful g

Node gnode = g.node ((( Integer)node.getData ()).intValue ());

// Coloram efectiv nodul

gnode.setFillColor(colors[k]);return 1;

}}

13

2.3 Corectitudinea

In urma rularii algoritmului prezentat, nodurile frunza sunt colorate dupaurmatorul principiu. Oricare ar fi doua noduri frunza:

Daca cel mai recent stramos comun este de tip paralel, atunci au aceeasiculoare.

Daca cel mai recent stramos comun este de tip serie, atunci au culoridiferite.

Sa presupunem ca solutia gasita de algoritm nu este optima. Aceastanseamna ca exista doua noduri frunza cu culori diferite dar care ar puteafi colorate cu aceeasi culoare. Fie v1, v2 aceste noduri si M cel mai recentstramos comun al lor. Deoarec M este de tip serie, atunci modulele tari M1si M2 corespunzatoare fiilor lui M n arbore cu v1 M1, respectiv v2 M2vor fi total adiacente, deci v1 este adiacent cu v2 n G si prin urmare nu potfi colorate la fel, contradictie.

2.4 Complexitatea

Fie G un cograf cu n noduri si m muchii. Dupa cum am mentionat deja, n[5], [8], [9] sunt prezentati algoritmi pentru descompunerea modulara a unuigraf avand complexitatea O(n +m). Asadar prima etapa a algoritmului sedesfasoara n timp liniar.

Avand n vedere ca arborele de de descompunere modulara are dreptfrunze nodurile lui G, numarul total al nodurilor sale este cel mult 2n 1.Etapa a doua a algoritmului efectueaza o parcurgere a arborelui ce trece prinfiecare nod exact o singura data, deci complexitatea sa este O(n).

Complexitatea totala a algoritmului este asadar O(n+m).

14

References

[1] M.C.Golumbic, Algorithmic Graph Theory and Perfect Graphs

[2] J. Spinrad, Efficient Graph Representation

[3] M.Habib, C.Paul, L.Viennot, Partiton refinment techniques: an inter-esting algorithmic toolkit

[4] M.Habib, C.Paul A new vertex splitting algorithm for cograph recognition

[5] R. McConnel, Jeremy Spinrad, Modular Decomposition and TransitiveOrientation

[6] R.McConnel, J. Spinrad Linear time transitive orientation

[7] R. McConnel, F.Montgolfier, PQ Trees and Modular Decomposition

[8] A.Counier, M.Habib, A new linear algorithm for modular decomposition

[9] M.Habib. F.Montgolfier, C.Paul, A simple linear-time modular decom-position algorithm for graphs, using order extending

[10] C.Capelle, Decomposition de graphes et permutations factorisantes, PhDthesis, Univ. Montpellier, 1997

[11] F.Montgolfier, Trouver larbre de decomposition modulaire dun graphea partir dune permutation factorisante, 2000

[12] E. Dahlhaust, J. Gusted, R. McConnell Efficient and Practical ModularDecomposition

15