Clasele 11-12 lecția 20 - 25 feb 2015

From Algopedia
Jump to: navigation, search

Discutarea problemelor de la OLI

Judecând după rezultate, bănuiesc că a fost ceva în neregulă cu subiectele. Sunt tare curios să le văd și să le discutăm!

Cicluri euleriene

Definiție: Fie un graf G = (V, E). Un ciclu în acest graf se numește ciclu eulerian dacă vizitează fiecare muchie exact o dată.

Mai prezintă interes și cazul când un graf nu admite un ciclu eulerian, dar admite o cale euleriană, așadar o cale care pornește dintr-un nod, se termină într-un alt nod și vizitează fiecare muchie exact o dată.

Condiții de existență

  • Un graf neorientat admite un ciclu eulerian dacă și numai dacă toate nodurile au grad par.
  • Un graf neorientat admite o cale euleriană dacă și numai dacă există exact două noduri cu grad impar.
  • Un graf orientat admite un ciclu eulerian dacă și numai dacă toate nodurile au gradul la intrare egal cu gradul la ieșire.
  • Un graf orientat admite o cale euleriană dacă și numai dacă există exact un nod s cu d_{o}(s)-d_{i}(s)=1, exact un nod t cu d_{i}(t)-d_{o}(t)=1, iar pentru restul nodurilor d_{o}(u)=d_{i}(u).

Demonstrație pentru prima proprietate

  • „⇒”: Presupunem că graful neorientat admite un ciclu eulerian C=\langle v_{0},v_{1},...v_{{m-1}},v_{m}=v_{0}\rangle . Pe acest ciclu, fiecare apariție a unui nod v_{i} contribuie cu două unități la gradul lui v_{i}, datorită muchiilor (v_{{i-1}},v_{i}) și (v_{i},v_{{i+1}}). De aceea, gradul lui v_{i} va fi par.
  • „⇐”: Presupunem că toate nodurile au grad par. Pornim dintr-un nod oarecare s și parcurgem muchii fără a parcurge vreo muchie de două ori, până când nu mai putem continua. Observăm că în acest moment am revenit în nodul s. De ce? Toate nodurile au grad par, deci la intrarea într-un nod există în mod sigur o altă muchie pe care să părăsim acel nod. Excepție face nodul s, în care, la un moment dat, vom reveni și nu vom mai putea pleca din nou.

Fie C ciclul găsit. Să considerăm gravul G'=(V,E-C). În G′, toate nodurile continuă să aibă grade pare, deoarece C scade o valoare pară din fiecare grad. Identificăm în mod recurent cicluri euleriene pentru componentele conexe ale lui G′. Cazul de bază este graful fără muchii. Deoarece G este conex, C trebuie să aibă cel puțin un nod în comun cu fiecare din componentele conexe ale lui G′. Inserăm ciclurile euleriene ale tuturor componentelor în C.

Algoritmul lui Fleury

Algoritmul lui Fleury traversează graful alegând la fiecare moment o muchie care să nu deconecteze graful rămas (unde print „graful rămas” înțelegem graful indus de mulțimea muchiilor rămase). Practic, algoritmul lui Fleury evită să traverseze muchii critice (punți). Din această cauză, el face teste costisitoare la fiecare pas și este ineficient.

  • Discuție despre corectitudinea afirmației de pe infoarena: „Pentru implementarea algoritmului lui Fleury, putem face o parcurgere în adâncime din nodul de start, etichetând muchiile după tipul lor (muchii de arbore și muchii de întoarcere). La fiecare pas în construirea ciclului, vom alege întotdeauna muchiile de întoarcere înaintea muchiilor de arbore.”

Algoritmul lui Hierholzer

Algoritmul lui Hierholzer decurge imediat din demonstrația de mai sus, dar implementarea în O(m+n) nu este trivială, în special pentru grafuri neorientate. În esență algoritmul este:

  • Găsește un ciclu cât mai lung, C.
  • Parcurge ciclul găsit.
  • Fie u nodul curent din parcurgere. Dacă u are încă muchii netraversate
    • Găsește un nou ciclu C′pornind din u
    • Inserează C′ în C la poziția curentă.

Putem parcurge ciclul C cu o coadă, de la stânga la dreapta. În acest caz este important să îl inserăm pe C′ imediat după poziția curentă (nu înainte), ca să ne asigurăm că și nodurile din C′ sunt analizate.

Pentru o implementare considerabil mai scurtă (deși mai greu de înțeles), putem parcurge ciclul C în ordine inversă, folosind o stivă. Această implementare are avantajul că nu mai trebuie să inserăm sub-ciclurile găsite -- stiva face aceasta pentru noi.

void euler(int u) {
  Stack S = { u };
  while (!S.empty()) {
    u ← S.top();
    if (u are muchii netraversate) {
      v ← vecin al lui u;
      șterge (u,v) din listele de adiacență ale lui u (și v, dacă G este neorientat);
      S.push(v);
    } else {
      S.pop();
      print u;
    }
  }
}

Așa cum este comun în recursivitate, privim problema la nivel local pentru a o rezolva la nivel global. Dacă nodul u nu mai are muchii neexplorate, îl tipărim și revenim în nodul părinte. Dacă nodul u mai are muchii, alegem una dintre ele la întâmplare, (u, v) și îl punem pe v pe stivă pentru a găsi un nou ciclu în acea direcție.

Detalii de implementare

Stivă proprie

Întrucât ciclul găsit poate avea lungime m, nu ne putem baza pe stiva recursivității. Trebuie să ne implementăm propria stivă.

Graf neorientat

Dacă graful este neorientat, știm deja că stocarea prin liste de adiacență dublează memoria necesară, deoarece muchia (u, v) trebuie stocată atât în lista de adiacență a lui u, cât și a lui v.

La parcurgerile DFS sau BFS, acest lucru nu ne deranjează, căci folosim un vector de variabile booleene care să evite revizitarea nodurilor. Dar când căutăm un ciclu eulerian, dorim să revizităm noduri! Din această cauză, trebuie să gestionăm cazul în care muchia (u, v) a fost traversată dinspre u spre v și trebuie să interzicem traversarea ei și dinspre v spre u. Iată două abordări.

Infoarena propune să parcurgem naiv lista de adiacență a lui v, să-l găsim pe u și să ștergem înregistrarea respectivă. Această abordare poate fi acceptabilă în grafuri rare. De exemplu, când n = 100.000 și m = 500.000, și presupunând că graful este relativ uniform, atunci fiecare nod va avea, la început, 10 vecini în medie și tot mai puțini pe măsură ce algoritmul elimină muchii. Dar dacă graful are un subgraf foarte dens sau dacă, de exemplu, n = 1.001 și m = 500.000, atunci fiecare nod va avea 1.000 de vecini în medie. Complexitatea algoritmului devine O(mn).

O implementare mai curată va facilita găsirea în O(1) a muchiei (v, u) dându-se muchia (u, v). De exemplu, putem ține pointeri între cele două muchii. Pentru invalidarea muchiei (v, u), o putem șterge direct, dacă stocăm listele de adiacență ca liste dublu înlănțuite, sau îi putem da lui u o valoare specială (0, -1 etc.).

Punctul de pornire

La limită, definiția ciclului eulerian nu exclude posibilitatea unor noduri de grad 0. Trebuie să ținem minte să începem traversarea dintr-un nod cu grad nenul. Acesta poate fi, de exemplu, primul capăt al primei muchii citite.

Problema poștașului chinez

Fie un graf neorientat cu costuri pe muchii. Dorim să traversăm toate muchiile acestui graf cu cost total minim. Putem repeta muchii.

Când graful admite un ciclu sau o cale euleriană, acela este chiar răspunsul. Ce facem când graful nu este eulerian? Discuție.

Probleme

  • Ciclu Eulerian (Infoarena) este un excelent punct de pornire. Remarcați că graful este neorientat și, mai mult, este un multigraf (admite muchii multiple între aceleași noduri, precum și bucle).
    • toate problemele menționate acolo
    • off-topic: parsarea ieșirii?
  • Biți (Infoarena) cere găsirea unui ciclu Eulerian într-un graf special cu 2^{n} noduri. Discuție despre secvențe de Bruijn.

Temă