Generarea directă a unui ciclu eulerian, în grafurile complete
În scopul investigării structurii ciclului eulerian furnizat pentru grafurile complete K2n+1, modificăm metoda Egraph::find_tour() din [1] - dar numai pentru a şi afişa, fiecare subciclu constituit în stiva de lucru până la finalizarea ciclului eulerian:
void Egraph::find_tour(int u) { // algoritmul lui Hierholzer std::stack<int> cycle; // evidenţiază câte un ciclu al grafului cycle.push(u); // nodul de start indicat la apel while(! cycle.empty()) { int u = cycle.top(); std::cout << u << ": "; // Afişează "top"-ul curent al stivei de lucru while(degree[u] > 0) { // avansează pe o muchie [u,v] "neutilizată" int v = descend(u); std::cout << v << " "; // Afişează vârful adăugat traseului curent cycle.push(v); // trece prin v delEdge(u, v); // "şterge" [u,v] şi actualizează gradul curent u = v; // trasează mai departe din nodul v } std::cout << '\n'; // Afişează pe linie nouă, viitorul subciclu constituit pe stivă // Descarcă nodurile din `cycle` din care nu mai există muchii neutilizate // şi expandează `cycle` dintr-un nod care încă are gradul curent nenul. // tour[] înregistrează subciclurile rezultate (în final - conţine ciclul eulerian) while(! cycle.empty() && (degree[cycle.top()] == 0)) { int u = cycle.top(); cycle.pop(); tour.push_back(u); // inserează (invers) subciclul rezultat în stivă } std::cout << '\n'; // Separă subciclurile afişate, de ciclul eulerian final } }
Singura modificare constă în adăugarea a patru "instrucţiuni" std::cout (dintre care două doar separă liniile afişate); comentariile păstrate din [1] sunt marcate cu verde.
Experimentând pentru diverse valori n, avem de sesizat o anumită stabilitate în privinţa producerii pe stiva de lucru a ciclurilor parţiale; putem deduce anumite caracteristici structurale ale ciclului eulerian produs de algoritmul lui Hierholzer (pe care se bazează "find_tour()") şi în final, vom putea sintetiza o formulare directă pentru un ciclu eulerian particular structurat, al lui K2n+1.
Un exemplu preliminar de investigare a subciclurilor
Bineînţeles că putem încerca ideea de investigare avansată mai sus, pe orice graf eulerian. Ne convine să considerăm grafuri uşor de generat - de exemplu acelea de ordin n definite printr-o relaţie precum: fiecare 0..n-3 este adiacent cu următorii doi şi 1 este adiacent cu n-1; le desemnăm prin X2 ("grafuri neXt-doi"). Am mai observa că ierarhia X2, X3 ("next-trei"), X4, ..., Xn-1 conduce chiar la grafurile complete.
#include "egraph.h" /* a vedea [1] */ #include <iostream> #include <cstdlib> // atoi() using namespace std; int main(int argc, char* argv[]) { int n = argc > 1? atoi(argv[1]): 10; // ordinul grafului (implicit, 10) int from = argc > 2? atoi(argv[2]): 0; // vârful de start (implicit, 0) Egraph X2(n); // graf neorientat, cu vârfurile 0..n-1 for(int i=0; i < n-2; ++i) { X2.addEdge(i, i+1); // Fiecare vârf este adiacent cu X2.addEdge(i, i+2); // "următoarele" două } X2.addEdge(1, n-1); // altfel am avea lanţ (nu ciclu) eulerian X2.to_DOT("X2.dot"); // `dot -Tpng -Kcirco -Estyle=bold -o X2.png X2.dot` int has = X2.have_tour(); // testează dacă există ciclu/lanţ eulerian switch(has) { case NECONEX: cout << "neconex\n"; break; case MANY_ODD: cout << "conex neEulerian\n"; break; case CYCLE: cout << "ciclu Eulerian din " << from << ":\n"; break; default: cout << "lanţ Eulerian:\n"; from = has; break; } if(from != -1) { X2.find_tour(from); // Determină şi afişează subciclurile X2.print_tour(); // şi apoi, ciclul eulerian final. } }
Compilând (cum am arătat în [1]) şi executând de exemplu pentru n=9, obţinem:
vb@vb:~/EGRAPH$ ./next_doi 9 ciclu Eulerian din 0: 0: 1 2 0 Primul subciclu rezultat în stiva de lucru 2: 3 1 8 6 4 2 Al doilea (din nodul 2 al primului) 4: 3 5 4 Al treilea (din nodul 4 al precedentului) 5: 6 7 5 Al patrulea subciclu 0 1 2 3 1 8 6 4 3 5 6 7 5 4 2 0 ciclul eulerian final
Ciclul eulerian a rezultat compunând patru cicluri disjuncte - trei de lungime 3 şi unul de lungime 6; dar schimbând vârful de start, ciclul eulerian rezultă din compunerea a trei, sau a două subcicluri - iar cu anumite vârfuri de start, ciclul eulerian se obţine chiar şi într-un singur pas:
vb@vb:~/EGRAPH$ ./next_doi 9 1 ciclu Eulerian din 1: 1: 0 2 1 3 2 4 3 5 4 6 5 7 6 8 1 1 0 2 1 3 2 4 3 5 4 6 5 7 6 8 1
vb@vb:~/EGRAPH$ ./next_doi 9 5 ciclu Eulerian din 5: 5: 3 1 0 2 1 8 6 4 2 3 4 5 6 7 5 5 3 1 0 2 1 8 6 4 2 3 4 5 6 7 5
Nu-i cazul să ne ocupăm mai mult de grafurile "X2"; dar sunt previzibile următoarele caracteristici ale ciclului eulerian furnizat de algoritmul lui Hierholzer: cu nodul de start 1, ciclul eulerian rezultă într-un singur pas (oricare ar fi n); există şi alte noduri (dificil de precizat, care anume) cu aceeaşi proprietate ca nodul 1 - iar plecând din alte noduri, ciclul eulerian rezultă compunând un anumit număr de 3-cicli (de lungime 3), cu încă un singur q-ciclu, q > 3.
Aici ne referim la "algoritmul lui Hierholzer" în redactarea "find_tour()" de mai sus, cu metodele (cele mai fireşti) de parcurgere şi de "ştergere" moştenite din clasa Graph din [1]).
Structura furnizată pentru K2n+1 de algoritmul lui Hierholzer
Pentru grafurile complete (de ordin impar) ciclul eulerian furnizat - cu 0 ca nod iniţial - rezultă din combinarea a exact două subcicluri disjuncte, a căror formă este relativ uşor de "abstractizat" (încât până la urmă, vom putea formula direct un ciclu eulerian într-un astfel de graf).
vb@vb:~/EGRAPH$ ./etest 7 K7 (cu 0 ca "start"!) 0: 1 2 0 3 1 4 0 5 1 6 0 primul subciclu 6: 2 3 4 2 5 3 6 4 5 6 al doilea subciclu 0 1 2 0 3 1 4 0 5 1 6 2 3 4 2 5 3 6 4 5 6 0
Colorând muchiile (ca să prezint aici imaginea) devine evident că subciclul "roşu" este ciclul eulerian al subgrafului 5-complet cu nodurile 2..6, iar cel "negru" îmbină ciclul 0-1-2 cu alţi doi cicli care conţin [0, 1] şi câte o muchie a acestui subgraf.
Altfel spus (dar mai general), subciclul roşu al lui K2n+1 este exact ciclul eulerian al lui K2n-1, urcând însă valorile termenilor cu 2: 0..2n-3 —> 2..2n-1.
Experimentând şi pe alte cazuri, nu-i greu să deducem că pentru K2n+1 primul subciclu furnizat de find_tour() combină 3-ciclul [0, 1, 2, 0] cu 4-ciclii [0, 3, 1, 4, 0], [0, 5, 1, 6, 0], ..., [0, 2n-1, 1, 2n, 0] - rezultând forma generală:
[0, 1, 2, 0, 3, 1, 4, 0, ..., 0, 2k-1, 1, 2k, 0, ..., 0, 2n-1, 1, 2n, 0]
în care 1 apare de exact n ori, fiind precedat de 0 şi 2k-1 (dacă 2k-1 > 1) şi urmat imediat de vârful 2k, k=1..n. Rezultă uşor că acest subciclu are lungimea 4n-1; al doilea subciclu menţionat va avea lungimea n(2n+1) - (4n-1) = n(2n-3)+1 (K2n+1 având în total, n(2n+1) muchii).
Al doilea subciclu începe de la nodul 2n, cu muchia [2n, 2]; descrierea generală directă a acestuia pare a fi mai complicată, dar în jurul lui 3 (apoi şi în jurul lui 5, 7, etc.) observăm structuri similare celor întâlnite în jurul lui 1 în cadrul primului subciclu:
vb@vb:~/EGRAPH$ ./etest 11 graful K11 (n = 5) 10: 2 3 4 2 5 3 6 2 7 3 8 2 9 3 10 4 5 6 4 7 5 8 4 9 5 10 6 7 8 6 9 7 10 8 9 10 0 1 2 0 3 1 4 0 5 1 6 0 7 1 8 0 9 1 10 2 3 4 2 5 3 6 2 7 3 8 2 9 3 10 4 5 6 4 7...
Desigur, descrierea cea mai simplă este cea observată mai sus, când am colorat muchiile: pentru K11 acesta este exact ciclul eulerian al lui K9, înlocuind 0..7—>2..9.
După secvenţa iniţială [2, 3, 4] urmează acum şablonul [2, 2k-1, 3, 2k] repetat succesiv pentru k=3..n (similar cu [0, 2k-1, 1, 2k] pentru k=2..n, în cazul primului subciclu). În continuare - la o primă vedere - după [4, 5, 6] urmează şablonul [4, 2k-1, 5, 2k] repetat succesiv pentru k=4..n; urmează [6, 7, 8] şi [6, 2k-1, 7, 2k] pentru k=5..n; ş.a.m.d. (depinzând de cât este n).
Urmând această descriere aproximativă, găsim după câteva experimente următoarea formulă precisă, de generare a celui de-al doilea subciclu:
2n, [ 2i, 2i+1, 2i+2, [ 2i, k, 2i+1, k+1, ]* ]*
k=2i+3, k < 2n+1, k += 2 (cu pasul 2)
i=1, i < (n-1)/2 (i += 1)
(aici, []* înseamnă repetarea conţinutului pentru valorile specificate dedesubt ale variabilei interne)
Îmbinând, următoarea secvenţă obţine cele două subcicluri disjuncte indicate mai sus:
// în K2n+1 (0..2n): ciclu eulerian partiţionat în două subcicluri int m = (n-1) / 2; cout << "\nPrimul subciclu:\n0 1 2 "; for(int k=2; k <= m; ++k) cout << 0 << " " << 2*k-1 << " 1 " << 2*k << " "; cout << "0\nAl doilea subciclu:\n" << 2*m << " "; for(int i=1; i < m; ++i) { cout << 2*i << " " << 2*i+1 << " " << 2*i+2 << " "; for(int k=2*i+3; k < n; k+=2) cout << 2*i << " " << k << " "<< 2*i+1 << " " << k+1 << " "; }
Inserând al doilea şir în locul penultimului termen din primul, rezultă - în mod direct - un ciclu eulerian al grafului K2n+1 (notând vârfurile cu 0..2n).
Pentru a verifica experimental că şirul obţinut astfel este un "şir eulerian" - a vedea şi [2] - al unui graf complet putem proceda şi astfel: înscriem termenii şirului într-un vector<int> cycle; (în loc de a-i afişa, ca în secvenţa redată mai sus); definim Egraph S(n) şi setăm adiacenţa în acest graf pe baza vectorului "cycle":
for(vector<int>::iterator it=cycle.begin(); it != cycle.end()-1; ++it)
S.addEdge(*it, *(it+1)); "uneşte" fiecare termen cu cel din dreapta sa
Apoi folosim S.to_DOT("S.dot"), obţinând prin execuţia programului constituit astfel, fişierul "S.dot" - pentru care, programul utilitar dot ne va da o imagine grafică a grafului S (şi putem vedea că a rezultat un graf complet). În [2] am procedat similar, pentru un alt "şir eulerian".
Rezultatul algoritmului depinde totuşi, de implementare!
Rezultatul algoritmului lui Hierholzer este un ciclu/lanţ eulerian (dacă există); dar faptul că rezultă un ciclu sau altul (care ciclu se obţine) depinde totuşi, de implementarea algoritmului - mai precis, depinde de ordinea în care se găsesc adiacenţii fiecărui vârf.
În cazul nostru, am folosit următoarea secvenţă (cea mai firească!) pentru a defini adiacenţa:
// defineşte un graf complet de ordinul n (impar)
Egraph K(n);
for(int i=0; i < n-1; ++i) // oricare două vârfuri sunt adiacente
for(int j=i+1; j < n; ++j)
K.addEdge(i, j); // înscrie j ca adiacent al lui i şi i ca adiacent al lui j
Desigur, am ignorat aspectul particular că pentru grafurile complete considerarea listelor de adiacenţă nu este necesară: adiacenţii fiecărui j sunt valorile 0..n-1 exceptând j.
Cu alte cuvinte, pentru fiecare vârf (număr 0..n-1), adiacenţii săi sunt înscrişi (în lista de adiacenţă corespunzătoare), în ordine crescătoare. Totodată, Graph::descend(u) determină primul adiacent nevizitat al vârfului indicat (parcurgând ascendent lista adiacenţilor acestuia) - a vedea [1].
Din aceste motive, ne-au rezultat tocmai "şirurile euleriene" de formatul evidenţiat mai sus; pe de altă parte - deoarece ordinea adiacenţilor nu depinde de n - am putea accepta (fără demonstraţie propriu-zisă!) că formatul respectiv - dedus în mod empiric - este valabil pentru oricare K2n+1.
Întâlnim şi în alte părţi, asemenea demonstraţii indirecte. De exemplu: este uşor să demonstrăm direct că într-un triunghi echilateral oarecare, medianele sunt concurente într-un punct care le împarte în raportul 2/3; dar atunci - pe baza faptului că rapoartele, coliniaritatea punctelor şi concurenţa dreptelor se păstrează prin proiecţie - rezultă (fără a fi necesară şi o demonstraţie directă) că proprietatea respectivă (angajând doar rapoarte şi concurenţă) este valabilă pentru orice triunghi (ştiind că acesta poate fi obţinut prin proiecţia unuia echilateral pe un anumit alt plan).
Pentru încă un exemplu de asemenea deducere a unui format general, să considerăm K5 şi să operăm algoritmul lui Hierholzer din ultimul nod:
0: 1 2 3 4 lista de adiacenţă a lui 0, în K5 1: 0 2 3 4 2: 0 1 3 4 3: 0 1 2 4 4: 0 1 2 3 adiacenţii ultimului nod: 0, 1, 2, ..., n-1
Din 4, primul nevizitat (pe o muchie care pleacă din 4) este 0; intrând la linia lui 0, primul nevizitat al acestuia este 1; la fel, pe linia lui 1 avem de ales 2, apoi de pe linia lui 2 alegem 0 (acesta fiind primul nevizitat printr-o muchie care să plece din 2); pe linia 0, primul nevizitat este acum 3, iar mai departe, de pe linia lui 3 avem de ales ca primul nevizitat pe 1; în linia 1 ne-a rămas 4 (singurul nevizitat din linia 1) şi apoi, de pe linia 4 alegem 2, de pe linia 2 - pe 3 şi în sfârşit, de pe linia 3 avem de ales 4. Algoritmul se încheie, fiindcă pe linia 4 nu mai există noduri nevizitate.
Constatăm că am obţinut ciclul eulerian 4, 0, 1, 2, 0, 3, 1, 4, 2, 3, 4 şi anume, într-un singur pas - nu cu două subcicluri, evidenţiate anterior pentru cazul când nodul de start era 0.
Rezultatul depinde de n în sensul evident - pentru K7 avem alte noduri decât pentru K5 - dar faptul că am obţinut ciclul eulerian într-un singur pas, se datorează numai ordonării existente în listele de adiacenţă. Prin urmare, am putea conchide (fără altă demonstraţie) că pentru orice n, algoritmul lui Hierholzer demarat din ultimul nod, produce un ciclu eulerian pentru K2n+1 într-un singur pas (în condiţia ca listele de adiacenţă să fie ordonate crescător).
Nu mai este cazul să experimentăm, pentru a găsi "formula generală" a ciclului determinat astfel: ultima linie de adiacenţă (în cazul redat mai sus, 4: 0,1,2,3) şi prima linie coincid dacă ignorăm nodul de rang maxim; aceasta înseamnă că după ce se parcurge muchia [2n, 0] şi se intră pe linia lui 0, ajungem exact în situaţia în care am fi luat ca punct de start nodul 0, exceptând doar faptul că într-un caz muchia [2n, 0] este prima, iar în celălalt este ultima parcursă. Rezultă că "şirurile euleriene" rezultate din 0 şi respectiv din 2n diferă numai prin poziţia muchiei [0, 2n]:
vb@vb:~/EGRAPH$ ./etest 5 4 4 0 1 2 0 3 1 4 2 3 4 ciclu eulerian în K5, din 4 (un singur pas) muchia [4, 0] este prima vb@vb:~/EGRAPH$ ./etest 5 0: 1 2 0 3 1 4 0 primul subciclu 4: 2 3 4 al doilea subciclu 0 1 2 0 3 1 4 2 3 4 0 ciclu eulerian în K5, din 0 (doi paşi) muchia [4, 0] este ultima
Lucrurile evidenţiate mai sus sunt valabile pentru oricare K2n+1, fiindcă raţionamentele noastre şi însăşi desfăşurarea algoritmului s-au bazat pe faptul că oricare vârf este adiacent cu oricare dintre celelalte vârfuri şi pe faptul că listele de adiacenţă sunt ordonate crescător - iar acestea sunt în fond proprietăţi calitative, nu depind de n.
Partiţionarea în subşiruri care diferă prin 2 şi descompunerea în cicli disjuncţi
Să vedem dacă putem formula mai bine, şirul eulerian obţinut (într-un singur pas) când startăm algoritmul din nodul 2n ("ultimul" din K2n+1).
Pentru cazul în care 0 este nodul de start, am observat mai sus că subciclul al doilea provine din ciclul eulerian al lui K2n-1, majorând cu 2 termenii acestuia; iar când am exemplificat algoritmul pe matricea liniilor de adiacenţă am putut observa că după alegerea valorilor 0, 1, 2, 0 urmează un timp, alegeri de valori aflate în matrice la o distanţă de două linii sau de două coloane, faţă de precedenta alegere (ulterior, această distanţă se măreşte, dar rămâne constantă pe porţiuni).
Deci pentru contextul nostru, doi este o valoare "cheie"! Ar fi de aşteptat ca în şirul eulerian obţinut să există secvenţe de termeni care se pot obţine una din alta prin translatare cu 2; după câteva încercări, am găsit o formulare "matriceală" a acestuia, în care secvenţa de pe linia următoare are termenii cu doi mai mari decât cei aflaţi pe aceleaşi coloane, în cadrul liniei precedente. Redăm în această formă, şirurile obţinute pentru K5, K7, K9 şi respectiv K11:
4 0 1 2 0 3 1 4 2 3 4 6 0 1 2 0 3 1 4 0 5 1 6 2 3 4 2 5 3 6 4 5 6 8 0 1 2 0 3 1 4 0 5 1 6 0 7 1 8 2 3 4 2 5 3 6 2 7 3 8 4 5 6 4 7 5 8 6 7 8 10 0 1 2 0 3 1 4 0 5 1 6 0 7 1 8 0 9 1 10 2 3 4 2 5 3 6 2 7 3 8 2 9 3 10 4 5 6 4 7 5 8 4 9 5 10 6 7 8 6 9 7 10 8 9 10
Prima linie este tocmai secvenţa menţionată mai la început ca "primul subciclu" în cazul startării din 0 - dar eliminând 0 de la sfârşit şi prefixând-o cu 2n:
[2n, 0, 1, 2, 0, 3, 1, 4, ..., 0, 2k-1, 1, 2k, ..., 0, 2n-1, 1, 2n]
Este uşor de constatat că după primul termen 2n, pe prima linie urmează exact 3 + 4(n-1) = 4n-1 termeni, ultimul fiind 2n.
Liniile următoare încep în a doua coloană şi termenii fiecăreia sunt cu 2 mai mari decât cei de pe aceleaşi coloane din linia precedentă; rezultă că ultimul termen pe fiecare linie este 2n, iar numărul de termeni de pe fiecare linie este cu 4 mai mic decât numărul termenilor de pe linia precedentă (neglijând din prima linie, termenul 2n aflat în prima coloană a sa); rezultă deasemenea (să ne uităm la valorile din a doua coloană 0,2,4,...,2n-2), că numărul de linii pe care este astfel reprezentat şirul eulerian respectiv este egal cu n.
Să mai observăm că ştergând ultima linie şi ultimele 4 valori de pe fiecare dintre celelalte linii din reprezentarea de mai sus a şirului eulerian corespunzător lui K2n+1 şi apoi, diminuând cu 2 primul termen din prima linie - rezultă exact reprezentarea corespunzătoare lui K2n-1 (confirmând observaţia "de recurenţă" făcută când am colorat muchiile, mai la început). Desigur, procedând analog putem formula reprezentarea lui K2n+1 din aceea a lui K2n-1 (adăugând câte 4 termeni şi o nouă linie şi incrementând cu 2 sub-secvenţele noi, de la o linia la alta) .
Pentru o verificare a formulei, cel mai convenabil este să folosim Python (putem forma cu uşurinţă noi liste, specificând diverse criterii de selecţie, sau anumite procesări):
# -*- coding: utf-8 -*- from operator import add # pentru a concatena liste, folosind reduce() def eul_seq(n): """ furnizează un şir eulerian al grafului complet cu nodurile 0..2n, sub forma unei partiţii ([2n] şi apoi încă n liste de termeni) """ lrows = [[]]*n # pregăteşte cele n liste (linii ale reprezentării) # constituie prima linie (listă), dar fără termenul iniţial 2n row0 = [[0, 2*k-1, 1, 2*k] for k in xrange(2, n+1)] lrows[0] = [0, 1, 2] + reduce(add, row0) # fiecare linie măreşte cu 2 pe cea precedentă (exceptând ultimii 4 termeni) for i in range(1, n): lrows[i] = [v+2 for v in lrows[i-1][:4*(n-i)-1]] # prefixează cu [2n] şi returnează partiţia de liste formată return [[2*n]] + lrows from pprint import pprint # "pretty prints" k13 = eul_seq(6) # şir eulerian în K_13, partiţionat pe linii pprint(k13) print reduce(add, k13) # şirul respectiv, redat ca o singură listă
Executând programul de mai sus, obţinem reprezentarea pe linii şi respectiv, reprezentarea uzuală (într-o singură listă) a şirului eulerian corespunzător grafului K13:
vb@vb:~/EGRAPH$ python formula.py [[12], [0, 1, 2, 0, 3, 1, 4, 0, 5, 1, 6, 0, 7, 1, 8, 0, 9, 1, 10, 0, 11, 1, 12], [2, 3, 4, 2, 5, 3, 6, 2, 7, 3, 8, 2, 9, 3, 10, 2, 11, 3, 12], [4, 5, 6, 4, 7, 5, 8, 4, 9, 5, 10, 4, 11, 5, 12], [6, 7, 8, 6, 9, 7, 10, 6, 11, 7, 12], [8, 9, 10, 8, 11, 9, 12], [10, 11, 12]] [12,0,1,2,0,3,1,4,0,5,1,6,0,7,1,8,0,9,1,10,0,11,1,12,2,3,4,2,5,3,6,2, 7,3,8,2,9,3,10,2,11,3,12,4,5,6,4,7,5,8,4,9,5,10,4,11,5,12,6,7,8,6,9, 7,10,6,11,7,12,8,9,10,8,11,9,12,10,11,12]
Am ajuns de la grafuri la şiruri de numere… Dar să nu uităm că termenii vecini ai şirului eulerian obţinut reprezintă muchii ale lui K2n+1; conectând mintal primul termen din linie cu ultimul termen al precedentei linii (în cadrul formatului matriceal de redare introdus mai sus) şi reexprimând pentru grafuri, ajungem la această caracterizare:
Pentru graful complet K2n+1 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 - exceptându-i primul nod 2n şi ultimele 4 noduri - provin din nodurile de aceeaşi poziţie din ciclul de lungime imediat superioară, prin majorarea acestora cu 2.
Ilustrăm aceasta pentru K7 (pentru n mic, din motive uşor de înţeles):
vb@vb:~/EGRAPH$ ./etest 7 6
ciclu Eulerian (produs într-un singur pas)
6 0 1 2 0 3 1 4 0 5 1 6 2 3 4 2 5 3 6 4 5 6
cu descompunerea în trei cicluri (disjuncte după muchii) care trec toate prin 6 şi au lungimile 11, 7, 3:
6 0 1 2 0 3 1 4 0 5 1 6
6 2 3 4 2 5 3 6
6 4 5 6
fiind "deplasate" între ele cu 2:
6 0 1 2 0 3 1 4 0 5 1 6 2 3 4 2 5 3 6 = [0 1 2 0 3 1 4] + 2 4 5 6 = [2 3 4] + 2
Dacă înlocuim 2n (primul vârf din ciclul cel mai lung) cu 2(n-1), eliminăm ciclul de lungime 3 şi eliminăm ultimele câte 4 noduri (muchii) din fiecare ciclu rămas - obţinem ciclul eulerian (de aceeaşi formă) corespunzător lui K2n-1.
Privind "descompunerea în cicluri", trebuie amintit următorul rezultat (Veblen, 1912): mulţimea muchiilor unui graf poate fi partiţionată în cicluri dacă şi numai dacă gradul fiecărui vârf este par (să observăm că nu este vorba neapărat, de graf conex). Algoritmul lui Hierholzer produce o asemenea partiţionare pentru grafurile euleriene, rezultatul depinzând în primul rând de modul în care sunt ordonate listele de adiacenţă; pentru grafurile complete de ordin impar, cu listele de adiacenţă ordonate crescător - rezultă cicluri euleriene care au caracteristicile structurale relevate mai sus, fiind astfel uşor de formulat chiar şi direct.
vezi Cărţile mele (de programare)