Backtracking in grafuri

Backtracking in grafuri
1. Colorarea graiurilor

Enuntul si consideratii

Problema: Se da un graf, G = (X, U) si un numar de c culori. Se cere sa se coloreze fiecare nod
astfel incat sa nu existe doua noduri adiacente colorate identic.

Rezolvare: Fie X = si U dat prin matricea de adiacenta A[n, n]. Fie x[i] culoarea
nodului i. Prin urmare, avem ca:

(x[1], x[2], , x[n]) = a (x[i]<>x[j])

1<=i<j<=n

a[i,j] = 1

Adica, prin serializare, avem ca:

fflk(x[1], x[2], , x[k]) = a (x[i]<>x[k])

1<=i<k
a[i,j] = 1

Teorema celor 4 culori

Definitie: Numarul minim de culori pentru care exista o colorare a grafului in conditiile problemei
se numeste numar cromatic si se noteaza cu y(G).

Definitie: Un graf pentru care exista o reprezentare grafica in care muchiile nu se intretaie se
cheama graf planar.

Teorema (teorema celor patru culori): Daca un graf G este planar, atunci y(G) <= 4.

Programul in limbajul Pascal

program colorarea_grafurilor;

const maxsir = 100;

type indicesir = 1..maxsir;

type sir array [indicesir] of integer;

type matrice = array [indicesir, indicesir] of 0..1;

type tipbacktracking = (recursiv, iterativ);

var p: sir;

var np: indicesir;

var a: matrice;

function fi (k: indicesir; x: sir): boolean;
var i: indicesir;
begin

fi := true;

for i to k - 1 do
if a [i] [k] = 1 then
if x [i] = x [k] then
fi := false

end;

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i, j: indicesir;
begin

writeln ('O noua solutie este:');
for i := 1 to n do

writeln ('Nodul ', i, ' colorat cu culoarea ', x [i])
end;

procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then
exit;

if level np then

prelucreaza_solutie (np, x)
else

for i := 1 to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level np, p, x)

end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin
k := 1;
x [k] while k > 0 do
begin
repeat

inc (x [k]);

ok fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k] := 0;
end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin

case tip of

recursiv: btr np, p, x);
iterativ: bt (np, p, x)
end
end;

var i, j: indicesir;
begin

writeln ('Colorarea grafurilor');
write ('numarul de noduri n=');
readln (np);
for i := 1 to np do
for j := 1 to np do
begin

write ('a i, j,

readln (a [i] [j])
end;

write ('numarul de culori c=');
readln (p for i to np do
p [i] p backtracking (iterativ, np, p)
end.

1.4. Programul in limbajul C

include <stdio.h>

define MAXSIR 100

define RECURSIV 1

define ITERATIV 2

// dimensiunile multimilor Mi

int a [MAXSIR][MAXSIR], p [MAXSIR];

int np;

define TRUE

define FALSE

functia de continuare

int fi (int k, int x[])

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

backtracking implementarea recursiva

void btr (int level, int np, int p[], int x[])

void bt   (int np, int p[], int x[])

if (x [k] <= p [k])
if (k np)prelucreaza_solutie (np, x);
else

else
k-- ;

void backtracking (int tip, int np, int p

void main ()

printf ('numarul de culori c=');

scanf ('%d', &(p    [1]));

for (i = 2; i <=    np; i++)
p [i] = p [1];

backtracking (ITERATIV, np, p);
}

1. Exercitii si probleme

Fie harta administrativa a unei tari. Fiecarui nod ii atasam o unitate administrativa. Fiecarei
frontiere intre doua judete ii atasam o muchie. Ce puteti spune despre numarul cromatic al
graful obtinut?

Avem o harta politica a Europei. Cate culori sunt necesare pentru a colora aceasta harta?

1.6. Rezolvarea exercitiilor si problemelor

Graful construit este un graf planar, deci are numarul cromatic cel mult 4.

Conform teoremei celor 4 culori, sunt suficiente 4 culori.

2. Determinarea drumurilor intre doua noduri

Enuntul si consideratii

Problema: Se considera un labirint. Se cere sa se determine toate drumurile care duc de la o pozitie
initiala (intrarea in labirint) la o pozitie finala (iesirea din labirint) fara a trece de doua ori prin
acelasi nod. Labirintul se da sub forma unui graf in care fiecare nod reprezinta o camera si fiecare
muchie reprezinta o usa(cale) de acces intre cele doua camere.

Rezolvare: Problema este echivalenta cu determinarea tuturor lanturilor neciclice intre doua
noduri ale unui graf. Fie acest graf G(X, U), cu X= si U dat prin matricea de adiacenta
A[n, n]. Fie L= un lant ce incepe in pozitia init e X. L este o solutie
acceptata daca si nu mai daca L este neciclic si x[k] = final, adica:

^ (L) = '(x[k] = final) a ( a (x[i] <> x[j]))

1<=i<j<=k
a[x[i],x[i+1]]=1
a[init, x[1]]=1

Practic, avem o problema tipica de backtracking cu solutii de lungime variabila, prin urmare:

9 (k, L) = a (x[i] <> x[k]))
1<=i<k
a[x[k-1],x[k]]=1
a[init, x[1]]=1

Programul in limbajul Pascal

program drumurile_dintre_doua_noduri;

const maxsir = 100;

type indicesir = 1..maxsir;

type sir array [indicesir] of integer;

type matrice = array [indicesir, indicesir] of 0..1;

type tipbacktracking = (recursiv, iterativ);

var p: sir;

var np: indicesir;

var a: matrice;

i capetele drumului j
var x0, xf: indicesir;

i functia de continuare j

function fi (k: indicesir; x: sir): boolean;
var i: indicesir;
begin

fi := true;

i drumul incepe cu x0 j
if (k = 1) then

if ( x [1] <> x0) then
fi := false;
i nu avem dubluri j
for i := 1 to k - 1 do
if x [i] = x [k] then
fi := false;

i nodul nou introdus sa fie adiacent cu penultimul j
if (k > 1) then

if ( a [x [k - 1], x[k]] = 0) then
fi := false

end;

i functia obiectiv j

function ffi (k: indicesir; x: sir): boolean;
begin

ffi := fi (k, x);

i drumul se termina cu xf j
if ( x [k] <> xf) then

ffi := false;
end;

i prelucrarea unei solutii x de dimensiune n j
procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

for i := 1 to n do

write (x [i], ' ');
writeln
end;

i backtracking implementarea recursiva j
procedure btvr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if (level > maxsir) or (level < 1) then
exit;

if (np > maxsir) or (np < 1) then
exit;

if level <= np then

for i := 1 to p [level] do
begin

x [level] := i;

if ffi (level, x) then

prelucreaza_solutie (level, x)
else if fi (level, x) then

btvr (level np, p, x)
end

end;

procedure btv (np: indicesir; p, x: sir);
var k: integer;
var ok, ok1, ok2: boolean;
begin
k x [k] while k > 0 do
begin
repeat

inc (x [k]);

ok1 ffi (k, x);

ok2 fi (k, x);

ok ok1 or ok2 or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if ok1 then

prelucreaza_solutie (k, x)
else
begin
inc (k);
x [k] end

else

dec (k)
end
end;

procedure backtrackingv (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;

begin

case tip of

recursiv: btvr np, p, x);
iterativ: btv (np, p, x)
end
end;

var i, j: indicesir;
begin

writeln ('Determinarea drumurilor elementare intre doua
noduri:');

write ('numarul de noduri n=');

readln (np);

for i := 1 to np do

for j := 1 to np do
begin

write ('a [', i, ', ', j, '] =

readln (a [i] [j])
end;

write ('de la x0 = ');
readln (x0);

write ('pana la xf = ');

readln (xf);

for i := 1 to np do

p [i] := np;
backtrackingv (iterativ, np, p)
end.

2.3. Programul in limbajul C

include <stdio.h>

define MAXSIR

define RECURSIV

define ITERATIV

// dimensiunile multimilor Mi

int p [MAXSIR];
int np;

// matricea de adiacenta
int a [MAXSIR][MAXSIR];

// capetele drumului
int x0, xf;

define TRUE 1

define FALSE

functia de continuare

int fi (int k, int x[])

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

backtracking implementarea recursiva

void btvr (int level, int np, int p[], int x[])

void btv (int np, int p[], int x[])

if (x [k] <= p [k])
if (ok1)
prelucreaza_solutie (k, x);
else

else
k--;

void backtracking (int tip, int np, int p[])

void main ()

printf ('de la x0 = ');
scanf ('%d', &x0);
printf ('pana la xf = ');
scanf ('%d', &xf);
for (i = 1; i <= np; i++)
p [i] = np;

backtracking (ITERATIV, np, p);
}

Exercitii si probleme

Este functia de continuare aleasa cea mai buna functie de continuare?

Cum putem afla numarul de drumuri de lungime data intre doua noduri?

Cum poate fi folosita valoarea de la problema precedenta in cazul nostru?

Rezolvarea exercitiilor si problemelor

Contraexemplu:

Numarul de drumuri de lungime k intre doua noduri i si j este elementul de pe linia i si coloana j
a matricii A^k.

Notam cu N(k) numarul de drumuri de lungime k intre cele doua noduri din graf. Atunci,
Numarul de solutii gasite de program <= N(1) + N(2) + + N(n). Cu egalitate daca graful este
aciclic . In acest caz, daca init si final fac parte din aceeasi componenta conexa, atunci exista
exact un drum, daca nu fac parte din aceeasi componenta conexa, atunci nu exista nici un drum.

3. Circuitele hamiltoniene

Enuntul si consideratii

Problema: Se considera un graf. Se cere sa se determine toate circuitele hamiltoniene .
Rezolvare: Problema este echivalenta cu determinarea tuturor permutarilor multimii nodurilor
(x[1], x[2], , x[n]) pentru care x[1] este fixat , iar doua noduri succesive sunt adiacente. Prin
urmare, functia 9 este:

9(x) = ( a (x[i] <> x[k])) a ( a (a[x[i],x[i+1]] = 1)) a (a[x[1],x[n]=1])
1<=i<k<=n 1<=i<n

sau, serializand, obtinem functia de continuare:

9 (x[1]) = (x[1]=1), pentru k =1

9k(x[1],x[2],,x[k]) = (x[k]<>x[k-1]) a (a[x[k],x[k-1]), pentru 1 < k < n
9_n(x[1],x[2],,x[n]) = (x[n]<>x[n-1]) a (a[x[n],x[n-1]) a (a[x[n],x[1]), pentru k = n

de unde se poate implementa algoritmul backtracking imediat.

Programul in limbajul Pascal

program circuit_hamiltonian;

const maxsir = lOO;

type indicesir l..maxsir;

type sir array [indicesir] of integer;

type matrice = array [indicesir, indicesir] of O..l;

type tipbacktracking = (recursiv, iterativ);

i dimensiunile multimilor Mi j

var p: sir;

var np: indicesir;

i matricea de adiacenta j
var a: matrice;

i functia de continuare j

function fi (k: indicesir; x: sir): boolean;
var i: indicesir;
begin

fi := true;

i nodurile distincte 2 cate doua j
for i := l to k - l do
if x [i] = x [k] then
fi := false;

i circuitul incepe cu nodul l pentru a nu numara de doua ori un
circuit j

if k = l then

if x [l] <> l then
fi := false;
i nodurile sunt adiacente doua cate doua j
if k > l then

if a [x [k], x [k - l]] = O then
fi := false;
i ultimul nod adiacent cu primul j
if k = np then

if a [x [np], x [l]] = O then
fi := false;

end;

i prelucrarea unei solutii x de dimensiune n j
procedure prelucreaza_solutie (n: indicesir; x: sir);
var i, j: indicesir;
begin

writeln ('O noua solutie este:');

write

for i := l to n do

write (x [i], writeln (x [l], end;

i backtracking implementarea recursiva j
procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then

exit;

if level np then

prelucreaza_solutie (np, x)
else

for i := 1 to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level np, p, x)

end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin
k := 1;
x [k] while k > 0 do
begin
repeat

inc (x [k]);

ok fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k] end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin

case tip of

recursiv: btr np, p, x);
iterativ: bt (np, p, x)
end
end;

var i, j: indicesir;

begin

writeln ('Circuite
write ('numarul de

readln (np);
for i := 1 to np do
for j := 1 to np do
begin

write ('a [', i, j,

readln (a [i] [j])
end;

for i := 1 to np do

p [i] := np;
backtracking (iterativ, np, p)
end.

3.3. Programul in limbajul C

include <stdio.h>

define MAXSIR 100

define RECURSIV 1

define ITERATIV 2

// dimensiunile multimilor Mi

int a [MAXSIR][MAXSIR], p [MAXSIR];

int np;

define TRUE 1

define FALSE 0

// functia de continuare

int fi (int k, int x[])

if (k == 1)

if (x [1] != 1)
return FALSE;
// nodurile sunt adiacente doua cate doua
if (k > 1)

if (a [x [k], x [k - 1]] == 0)
return FALSE;
// ultimul nod adiacent cu primul
if (k == np)

if (a [x [np], x [1]] == 0)
return FALSE;

return TRUE;
}

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

backtracking implementarea recursiva

void btr (int level, int np, int p[], int x[])

void bt (int np, int p[], int x[])

if (x [k] <= p [k])
if (k == np)
prelucreaza_solutie (np, x);
else

else
k-- ;

void backtracking (int tip, int np, int p[])

void main ()

for (i i <= np; i++)
p [i] np;

backtracking (ITERATIV, np, p);

3.4. Exercitii si probleme

Care e rolul testului x[1]=1 in functia de continuare?

Care e rolul testului a[x[1],x[n]] in functia de continuare?

3. Rezolvarea exercitiilor si problemelor

Scopul este de a nu numara de mai multe ori un circuit . De exemplu, in lipsa acestei conditii,
circuitele [1, 2, 3] si [2, 3, 1] vor fi de doua ori numarate

Scopul este de a inchide circuitul .

4. Circuitele euleriene

4.1. Enuntul si consideratii

Problema: Se considera un graf. Se cere sa se determine toate circuitele euleriene .
Rezolvare: Problema este echivalenta cu determinarea tuturor permutarilor multimii aecelor (x[1],
x[2], , x[n]) pentru care x[1] este fixat , iar doua noduri succesive sunt adiacente. Notam arcul i
ca fiind (u1[i], u2[i]) pentru a simplifica constructia functiei de continuare care este imediata.

4.2. Programul in limbajul Pascal

program euleriene;

const maxsir = 100;

type indicesir = 1..maxsir;

type sir array [indicesir] of integer;

type tipbacktracking = (recursiv, iterativ);

var p: sir;

var np: indicesir;

u1, u2: sir;
var m: indicesir;

function fi (k: indicesir; x: sir): boolean;
var i: indicesir;
begin

fi := true;

for i to k do
if x [i] = x [k] then
fi := false;

if k = 1 then

if x [1] <> 1 then
fi := false;

if k = np then

if u2 [x [k]] <> u1 [x [1]] then
fi := false;

if k > 1 then

if u2 [x [k - 1]] <> u1 [x [k]] then
fi := false

end;

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

write u1 for i := 1 to n do

write (u2 [x [i]],

writeln end;

procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then
exit;

if level np then

prelucreaza_solutie (np, x)
else

for i to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level np, p, x)

end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin
k := 1;
x [k] while k > 0 do
begin
repeat

inc (x [k]);

ok fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k] end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin

case tip of

recursiv: btr np, p, x);
iterativ: bt (np, p, x)

end
end;

var i: indicesir;
begin

writeln ('Generarea circuitelor euleriene pentru un graf G');
write ('numarul de arce m readln (np);
for i := 1 to np do
begin

write ('pentru arcul ', i, ' dati capatul din stanga: ');
read (u1 [i]);

write ('pentru arcul ', i, ' dati capatul din dreapta: ');
read (u2 [i]);
p [i] := np
end;

backtracking (iterativ, np, p)
end.

4.3. Programul in limbajul C

include <stdio.h>

define MAXSIR 100

define RECURSIV 1

define ITERATIV 2

// dimensiunile multimilor Mi
int p [MAXSIR];
int np;

// sirul arcelor

int u1 [MAXSIR], u2 [MAXSIR], m;

define TRUE 1

define FALSE 0

// functia de continuare

int fi (int k, int x[])

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

backtracking implementarea recursiva

void btr (int level, int np, int p[], int x[])

void bt (int np, int p[], int x[])

if (x [k] <= p [k])
if (k np)
prelucreaza_solutie (np, x);
else

else
k--;

void backtracking (int tip, int np, int p[])

void main ()

backtracking (ITERATIV, np, p);
}

4.4. Exercitii si probleme

Demonstrati ca o conditie necesara si suficienta ca un graf conex sa admita circuite euleriene
este ca pentru fiecare nod, gradul de intrare sa fie egal cu gradul de iesire

Modificati si demonstrati enuntul anterior pentru grafuri neorientate si cicluri euleriene.

4. Rezolvarea exercitiilor si problemelor

'=>' Fie C un circuit eulerian si fie x un nod oarecare. Fie k numarul de aparitii a lui x in
circuit. Rezulta imediat ca grad intrare (x) = k si grad iesire (x) = k. Adica gradele de intrare si
iesire sunt egale.

'<=' imediat prin constructia partiala a circuitului, cu pastrarea unui invariant legat de paritatea
nodurilor.

O conditie necesara si suficienta ca un graf G sa admita cicluri euleriene este ca pentru fiecare
nod, gradul sa fie par.

'=>' G admite cicluri euleriene; fie C=[x1, x2, , xn, x1] un astfel de ciclu. Se pot transforma
muchiile in arce asfel incat C'=[x1, x2, , xn, x1] sa fie circuit eulerian. Deci gradul de intrare
= gradul de iesire. Dar cum fiecarei muchii incidente unui nod ii corespunde un arc, rezulta ca
jumatate intra si jumatate ies, adica numarul initial de muchii era par.

'<=' G graf cu gradele nodurilor pare. Transformam muchiile in arce astfel incat sa avem
pentru fiecare nod indeplinita conditia ca gradul de intrare = gradul de iesire^[12]. In noul graf
orientat G va exista un circuit eulerian C=[x1, x2, , xn, x1]. Prin urmare si in graful initial va
exista un ciclu eulerian C=[x1, x2, , xn].