Note de curs, probleme algoritmică, 29 noiembrie 2013

From Algopedia
Revision as of 11:06, 30 November 2013 by Dan (talk | contribs) (Created page with "În acest curs am discutat problemele: * [http://acm.timus.ru/problem.aspx?space=1&num=1056 1056 - Computer Net]; * [http://acm.timus.ru/problem.aspx?space=1&num=1641 1641 - D...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

În acest curs am discutat problemele:

1045 - Funny Game

Această problemă este o problemă simplă de teoria jocurilor, care se rezolvă prin aceleași tehnici descrise în cursul anterior.

1056 - Computer Net

Cerința

Dându-se un arbore, să se identifice toate nodurile centrale. Un nod este central dacă se află la distanță maximă de un alt nod.

Soluție

Soluția presupune, în principiu, parcurgerea nodurilor în ordine, de la marginea arborelui către centrul său.

Concret, vom flosi o coadă în care, inițial, vom introduce toate funzele (nodurile cu gradul 1). Cât timp coada nu este goală, vom scoate un nod din coadă și îl vom șterge din arbore împreună cu muchia care îl leagă de arbore; dacă prin ștergerea muchiei respective vom obține un nou nod cu gradul 1 (o nouă frunză) îl vom adăuga și pe acesta în coadă.

Atunci când introducem inițial frunzele în coadă, le atribuim acestora distanța 0 (față de "marginea" arborelui). Atunci când introducem o nouă frunză în arbore, îi atribuim acesteia o distanță cu 1 mai mare decât a nodului pe care l-am eliminat și a dus la introducerea ei în coadă.

În final, nodurile cu cea mai mare distanță sunt și centri.

Se poate demonstra ușor că orice arbore are cel mult 2 noduri-centri.

Demonstrație

Presupunem prin absurd că un arbore are 3 centri. Acești cetri formează un arbore. Singurul arbore neetichetat cu 3 noduri are un nod cu gradul 2, care nu este frunză. Acest nod va avea o distanță față de "marginea" arborelui mai mare cu 1 decât celelalte două noduri-centri. Dar, acest lucru este o contradicție, deoarece toate nodurile-centri trebuie să se afle la aceeași distanță de "marginea" arborelui.

În general, presupunând prin absurd că un arbore ar avea mai mult de 2 centri, atunci sub-arborele format de acești centri va conține cel puțin un nod intern, care mai fi "mai central" decât frunzele sale.

A doua soluție

Pornind dintr-un nod la întâmplare A, se identifică (printr-o parcurgere) cel mai depărtat nod B de acesta. Pornind din nodul B, se identifică (printr-o parcurgere) cel mai depărtat nod C de acesta.

Între nodurile B și C se va forma un lanț de lungime maximă în arbore. La mijlocul acestuia se vor afla nodurile centrale ale arborelui.

1641 - Duties

Aceasta este o problemă constructivă. Deoarece acest gen de problemă stimulează creativitatea și imaginația, nu voi prezenta nicio soluție. De altfel, o multitudine de soluții sunt posibile.

1416 - Confidential

Cerința

Dându-se un graf, să se calculeze costul arborelui parțial de cost minim și costul celui de-al doilea arbore parțial de cost cât mai mic.

Soluție

Primul arbore parțial

Se sortează muchiile crescător, după cost.

Se pornește de la graful inițial, dar fără nicio muchie. Astfel, fiecare nod formează propria sa componentă conexă. Se parcurge lista de muchii, așa cum a fost sortată. Pe rând, se încearcă adaugarea fiecărei muchii. Dacă muchia curentă unește două componente conexe (două noduri din componente conexe distincte), atunci se va adăuga la graf (va face parte din primul arbore parțial). Dacă muchia curentă închide un ciclu (unește două noduri din aceeași componentă conexă) atunci va fi ignorată (nu va face parte din primul arbore parțial).

Al doilea arbore parțial

Pornind de la primul arbore parțial, vom precalcula, pentru fiecare pereche de noduri costul celei mai scumpe muchii de pe lanțul care le unește.

Parcurgem toate muchiile care nu fac parte din primul arbore parțial. Pentru fiecare muchie vom forma un potențial al doilea arbore parțial astfel: vom adăuga primului arbore parțial muchia curentă (i, j) și îi vom șterge cea mai scumpă muchie de pe lanțul i -> j.

În final, dintre toți potențialii arbori parțiali secundari îl vom alege pe cel mai ieftin.