* 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)

* 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 nostru)

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:

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$

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 $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$