h2. 'Kcity':problema/kcity

h3. "Bandwidth"-ul si "Pathwidth"-ul unui graf
 
Sa consideram ca nodurile unui graf sunt renumerotate cu numere de la $1$ la $N$ si sa notam cu $BMAX$ valoarea maxima a diferentei (in modul) dintre numerele asociate a doua noduri adiacente. "Bandwidth"-ul $B$ al unui graf este valoarea minima a lui $BMAX$ dintre toate renumerotarile posibile ale nodurilor. Determinarea acestei valori $B$ nu se poate realiza in timp polinomial. In cadrul problemei date, nodurile au fost deja numerotate corespunzator, astfel incat graful sa aiba un "bandwidth" mic, egal cel mult cu valoarea $K$ data.
 
"Pathwidth"-ul unui graf este un numar ce reflecta cat de mult structura grafului este asemanatoare cu cea a unui drum. Daca un graf $G$ are un "pathwidth" $P$, atunci exista un graf-drum $D$, cu nodurile $D{~1~}, D{~2~}, ..., D{~X~}$, avand urmatoarele proprietati:
 
* fiecare nod $D{~i~}$ corespunde unei submultimi de cel mult $P$ noduri ale grafului $G$
* oricare doua noduri adiacente ale grafului $G$, $u$ si $v$, se afla impreuna in cel putin una din submultimile $D{~1~},...,D{~X~}$
* orice nod $u$ al grafului $G$ apartine unor multimi $D{~i~}$ care formeaza un sub-drum al grafului $D$ (mai exact, niciun nod $u$ al lui $G$ nu poate sa apartina unui submultimi $D{~i~}$, sa nu apartina unei submultimi $D{~j~}$ {$(j > i)$} si apoi sa apartina din nou unei alte submultimi $D{~k~}$ $(k > j)$
 
Daca avem o renumerotare a unui graf $G$ corespunzatoare unui "bandwidth" mic, atunci putem obtine si o descompunere cu "pathwidth" mic a grafului G, care ne va ajuta sa rezolvam problema.
 
h3. Solutie de complexitate $O(N * numar_stari * K^3^)$
 
Elementele teoretice prezentate mai sus nu sunt neaparat necesare pentru a rezolva problema. Se "ghiceste" usor ca problema se rezolva folosind programare dinamica pe un numar exponential de stari, care depinde, insa, numai de $K$, care este o valoare mica.
 
Vom calcula urmatoarele valori:
 
* $minp[i][S]$ = numarul minim de drumuri cu care se pot acoperi nodurile $1,2,...,i$, iar starea la pasul $i$ sa fie $S$
* $minc[i][S]$ = numarul minim de cicluri cu care se pot acoperi nodurile $1,2,...,i$, iar starea la pasul $i$ sa fie $S$ (nu trebuie sa apartina neaparat unui ciclu inchis si nodurile din cadrul starii curente sau cele care apartin deja unor drumuri care au capetele in cadrul starii curente)
 
O stare $S$ la pasul $i$ este reprezentata de starea ultimelor $K$ noduri $(i-K+1, i-K+2, ..., i)$. O prima idee de definire a starii este urmatoarea: fiecare nod se poate afla in una din urmatoarele $3$ stari:
 
* are gradul $0$ (este un drum ce consta doar din nodul respectiv)
* are gradul $1$ (este un capat al unui drum)
* are gradul $2$ (se afla in interiorul unui drum sau al unui ciclu – in orice caz, daca un nod are gradul $2$, el nu mai prezinta interes in algoritmul noastru)
 
Definind o stare astfel, ar exista $3{^K^}$ stari in total. La fiecare pas $i$, am considera toate starile $S'$ de la pasul $i-1$ si, adaugand nodul $i$, impreuna cu unele muchii, la starea $S'$, am obtine niste stari $S$, pentru pasul $i$. Avem urmatoarele optiuni:
 
* pentru cazul acoperii cu drumuri
** nodul $i$ formeaza un drum nou (are gradul $0$) => numarul de drumuri creste cu $1$
** nodul $i$ extinde un drum deja existent (il legam de un nod $j$ de grad $0$ sau $1$, cu conditia sa existe muchia $i-j$) => numarul de drumuri ramane acelasi
** nodul $i$ leaga doua drumuri diferite (il legam de nodurile $j$ si $k$ de grad $0$ sau $1$, unind astfel doua drumuri) => numarul de drumuri scade cu $1$
* pentru cazul acoperirii cu cicluri
** nodul $i$ formeaza un drum nou (are gradul $0$) => numarul de cicluri ramane la fel
** nodul $i$ extinde un drum deja existent (il legam de un nod $j$ de grad $0$ sau $1$, cu conditia sa existe muchia $i-j$) => numarul de cicluri ramane la fel
** nodul $i$ leaga doua drumuri diferite (il legam de nodurile $j$ si $k$ de grad $0$ sau $1$, unind astfel doua drumuri) => numarul de cicluri ramane la fel
** nodul $i$ leaga cele $2$ capete ale unui drum => numarul de cicluri creste cu $1$
** daca nodul $i > K$, trebuie sa ne asiguram, inainte de a trece mai departe, ca nodul $i-K$ are gradul $2$ (se afla in interiorul unui drum sau al unui ciclu) => optiunile de mai sus nu sunt valide decat daca, in urma aplicarii lor, nodul $i-K$ are gradul $2$
 
Observam o dificultate in cazul in care nodul $i$ trebuie sa uneasca doua drumuri de grad $1$. In cazul acoperirii cu drumuri, trebuie sa ne asiguram ca el nu leaga capetele aceluiasi drum (inchizand, de fapt, un ciclu, in timp ce noi credeam ca a unit $2$ drumuri). In cazul acoperii cu cicluri trebuie sa putem realiza aceeasi distinctie. Asadar, modul in care am definit starea nu este corect, desi era, poate, cel mai intuitiv.
 
O stare va trebui definita in felul urmator: fiecare din cele $K$ noduri ale starii se poate afla in una din urmatoarele situatii:
 
* are gradul $0$ (este un drum ce consta doar din nodul respectiv) – se codifica prin $0$
* are gradul $1$ si este capatul unui drum care are un identificator bine specificat - se codifica prin identificatorul drumului
* are gradul $2$ (se afla in interiorul unui drum sau al unui ciclu) - se codifica prin $-1$
 
De exemplu, pentru $K=6$, starea $S=(-1, 1, 0, 2, -1, 1)$ specifica faptul ca primul si al cincilea nod au gradul $2$, al treilea nod are gradul $0$, al doilea si al saselea nod sunt capetele aceluiasi drum, care are identificatorul $1$, iar al patrulea nod este capatul unui drum ce are identificatorul $2$ (celalalt capat fiind ramas undeva in urma).
 
Conform noii definitii a starilor, acestea trebuie generate explicit. Observam ca doar doua noduri pot fi capetele aceluiasi drum, ca identificatorii drumurilor ii putem genera de la $1$ pana la cate drumuri pot exista intr-o stare (maxim $K$) si ca putem considera identificatorii drumurilor sortati in ordinea in care apar in cadrul starii nodurile ce sunt capetele acestora. De exemplu, starea $S=(-1, 2, 0, 1, -1, 2)$ nu ar avea sens, fiind echivalenta cu cea prezentata mai sus, schimband doar identificatorii drumurilor intre ei. Pentru $K=6$ exista $2364$ astfel de stari.
 
Raspunsul dorit il gasim intr-una din starile de la pasul $N$:
 
* pentru acoperirea cu drumuri se alege minimul dintre toate valorile $minp[N][S]$
* pentru acoperirea cu cicluri se alege valoarea $minc[N][S]$, unde $S$ este starea in care toate nodurile au gradul $2$ ; daca aceasta valoare este infinit, atunci rezultatul este $-1$
 

h2. 'Consir':problema/consir
h2. 'Polig':problema/polig