Pânzele drumurilor hamiltoniene pe graful calului 5x5
Prelucrăm (prin comenzi perl) un fişier "informativ" şi reducem (printr-un program Python) cele 1728 de drumuri hamiltoniene ale calului de şah pe tabla 5x5, la un tablou javaScript conţinând cele 864 de drumuri "directe"; apoi, realizăm o funcţie javaScript care produce un element <canvas> pe care se vizualizează drumul indicat (pe tabla a cărei dimensiune este indicată).
Modelare C++ pentru probleme hamiltoniene
Pentru ce n găsim o secvenţă circulară a numerelor 1..n, astfel încât suma oricăror doi termeni vecini să fie pătrat perfect? Şirul cerut este un ciclu hamiltonian al grafului cu vârfurile 1..n în care avem câte o muchie pentru fiecare două valori a căror sumă este pătrat perfect.
Pe graful calului de şah de ordin 5x5 avem 4*304 + 8*56 + 64 = 1728 drumuri hamiltoniene (jumătate dintre ele fiind însă, inversele celorlalte).
Modelăm şi investigăm asemenea grafuri ("Square", "Knight"), bazându-ne pe o clasă "Hamilton" care oferă o metodă de căutare (backtracking compus cu regula lui Warnsdorff) a unui drum/ciclu hamiltonian.
Generarea expresiilor aritmetice cu patru operanzi
Modelăm expresiile aritmetice prin arbori binari, plecând de la o clasă abstractă pentru noduri şi angajând "smart pointers" din C++11. Generăm prin acest model, toate expresiile aritmetice cu 4 operanzi - filtrând eventual pe cele care interesează în privinţa valorii.
Generarea directă a unui ciclu eulerian, în grafurile complete
Pentru graful complet cu nodurile 0..2n şi cu listele de adiacenţă ordonate crescător, ciclul eulerian produs de algoritmul lui Hierholzer startat din nodul 2n este constituit din n cicli disjuncţi după muchii, având în comun vârful 2n şi respectiv lungimile 3+4*j (j=0..n-1); exceptând ciclul cel mai lung, nodurile fiecărui ciclu - afară de primul nod 2n şi de ultimele patru noduri - provin din nodurile de aceeaşi poziţie ale ciclului de lungime imediat superioară, prin majorarea acestora cu 2.
Model C++ de graf şi submodel de graf eulerian
Completăm modelul "minimal" de graf (introdus anterior), astfel încât să facilităm algoritmii care angajează muchiile grafului: după ce muchia este parcursă, ea trebuie "ştersă" (marcând-o drept "utilizată"), iar gradele curente ale capetelor ei trebuie decrementate. Derivăm de aici, o modelare a grafurilor euleriene (algoritmul lui Hierholzer) şi testăm pentru grafurile complete (K1001 poate fi "rezolvat" sub 100 de secunde).
vezi Cărţile mele (de programare)