Diferente pentru taietura-minima intre reviziile #33 si #46

Nu exista diferente intre titluri.

Diferente intre continut:

h2. Algoritm
Pe parcursul articolului, vom considera un graf neorientat G, multimea nodurilor o vom nota cu V, iar pe cea a muchiilor cu E. Fiecare muchie _e_ are un cost asociat _w(e)_. Pentru a rezolva problema, vom cauta o modalitate cat mai simpla de a gasi 2 noduri _s_ si _t_, precum si valoarea taieturii minime _s-t_. Urmatoarea teorema ne explica de ce este necesar acest lucru:
Pe parcursul articolului, vom considera un graf neorientat $G$, multimea nodurilor o vom nota cu $V$, iar pe cea a muchiilor cu $E$. Fiecare muchie $e$ are un cost asociat $w(e)$. Pentru a rezolva problema, vom cauta o modalitate cat mai simpla de a gasi 2 noduri $s$ si $t$, precum si valoarea taieturii minime $s-t$. Urmatoarea teorema ne explica de ce este necesar acest lucru:
Teorema 1: _Fie s si t doua noduri dintr-un graf G. Notam cu G/{s,t} graful obtinut din G prin fuzionarea nodurilor s si t. Atunci taietura minima a grafului G este cea mai mica dintre taietura minima s-t a grafului G si taietura minima a grafului G/{s,t}._
Teorema 1: _Fie $s$ si $t$ doua noduri dintr-un graf $G$. Notam cu $G/{s,t}$ graful obtinut din $G$ prin fuzionarea nodurilor $s$ si $t$. Atunci taietura minima a grafului $G$ este cea mai mica dintre taietura minima $s-t$ a grafului $G$ si taietura minima a grafului $G/{s,t}$._
Teorema este adevarata deoarece facand o taietura minima in graf nodurile s si t fie vor fi in multimi diferite (primul caz tratat), fie in aceeasi multime (cel de-al doilea caz).
Teorema este adevarata deoarece facand o taietura minima in graf nodurile $s$ si $t$ fie vor fi in multimi diferite (primul caz tratat), fie in aceeasi multime (cel de-al doilea caz).
Asadar o procedura care gaseste o taietura minima _s-t arbitrara_ poate fi folosita pentru a construi un algoritm recursiv ce gaseste taietura minima.
Asadar o procedura care gaseste o taietura minima _$s-t$ arbitrara_ poate fi folosita pentru a construi un algoritm recursiv ce gaseste taietura minima.
Urmatorul algorim, care poarta denumirea de _cautare maxima de adiacenta_ (in engleza _maximum adjacency search_ sau _maximum cardinality search_) gaseste taietura _s-t_ dorita:
Urmatorul algorim, care poarta denumirea de _cautare maxima de adiacenta_ (in engleza _maximum adjacency search_ sau _maximum cardinality search_) gaseste taietura _$s-t$_ dorita:
== code(c) |
FazaTaieturiiMinime(G, w, a)
    retine taietura si micsoreaza graful G prin fuzionarea ultimelor doua noduri adaugate
==
Explicatie: O submultime A a lui V creste incepand cu un nod arbitrar pana cand A devine egala cu V. La fiecare pas, nodul care nu se afla in A, _cel mai puternic conectat_, este adaugat multimii. Intr-o formulare mai formala, putem spune ca adaugam nodul
Explicatie: O submultime $A$ a lui $V$ creste incepand cu un nod arbitrar pana cand $A$ devine egala cu $V$. La fiecare pas, nodul care nu se afla in $A$, _cel mai puternic conectat_, este adaugat multimii. Intr-o formulare mai formala, putem spune ca adaugam nodul
    z ∉ A astfel incat _w(A, z)_ = max{_w(A, y)_|y ∉ A},
$z ∉ A astfel incat w(A, z) = max{w(A, y) | y ∉ A},$
unde _w(A, y)_ este suma costurilor muchiilor dintre nodul y si nodurile care apartin multimii A. La sfarsitul fiecarei astfel de faze, ultimele doua noduri adaugate fuzioneaza, ceea ce inseamna ca cele doua noduri sunt inlocuite de un nou nod, si orice muchii de la un nod ramas la cele doua noduri scoase sunt inlocuite de o noua muchie de cost egal cu suma costurilor precedentelor doua muchii. Muchiile intre cele doua noduri sunt eliminate. Taietura lui V ce separa ultimul nod adaugat de restul grafului se numeste taietura fazei. Cea mai mica dintre aceste taieturi ale fazei, reprezinta rezultatul dorit, si anume taietura minima in graf.
unde $w(A, y)$ este suma costurilor muchiilor dintre nodul $y$ si nodurile care apartin multimii $A$. La sfarsitul fiecarei astfel de faze, ultimele doua noduri adaugate fuzioneaza, ceea ce inseamna ca cele doua noduri sunt inlocuite de un nou nod, si orice muchii de la un nod ramas la cele doua noduri scoase sunt inlocuite de o noua muchie de cost egal cu suma costurilor precedentelor doua muchii. Muchiile intre cele doua noduri sunt eliminate. Taietura lui $V$ ce separa ultimul nod adaugat de restul grafului se numeste taietura fazei. Cea mai mica dintre aceste taieturi ale fazei, reprezinta rezultatul dorit, si anume taietura minima in graf.
== code(c) |
TaieturaMinima(G, w, a)
            atunci actualizeaza taietura minima curenta
==
Observatie: Nodul _a_ ramane fixat pe parcursul intregului algoritm. Am putea sa il alegem insa in mod arbitrar la fiecare pas.
Observatie: Nodul $a$ ramane fixat pe parcursul intregului algoritm. Am putea sa il alegem insa in mod arbitrar la fiecare pas.
h2. Corectitudine
Pentru a demonstra corectitudinea algoritmului, trebuie mai intai sa demonstram urmatoarea lema:
Lema 1: _Fiecare taietura faza reprezinta o taietura minima s-t, unde s si t sunt ultimele 2 noduri adaugate in faza curenta._
Lema 1: _Fiecare taietura faza reprezinta o taietura minima $s-t$, unde $s$ si $t$ sunt ultimele 2 noduri adaugate in faza curenta._
Demonstratie: Procedura FazaTaieturiiMinime sorteaza nodurile grafului curent, incepand cu a si terminand cu _s_ si cu _t_, in functie de ordinea in care acestea au fost adaugate in multimea A. Vom analiza o taietura C _s-t_ oarecare a grafului curent si vom demonstra ca are costul mai mare sau egal cu cel al taieturii faza.
Demonstratie: Procedura FazaTaieturiiMinime sorteaza nodurile grafului curent, incepand cu a si terminand cu $s$ si cu $t$, in functie de ordinea in care acestea au fost adaugate in multimea $A$. Vom analiza o taietura $C$ $s-t$ oarecare a grafului curent si vom demonstra ca are costul mai mare sau egal cu cel al taieturii faza.
Numim un nod _v ≠ a_ activ (in raport cu taietura C) daca _v_ si ultimul nod aduagat inainte de _v_ se afla in multimi diferite. Fie _w(C)_ costul taieturii C, A{~v~} multimea nodurilor adaugate inaintea lui _v_, C{~v~} taietura lui A{~v~} ∪ _v_ indusa de C, iar _w(C{~v~})_ costul taieturii induse.
Numim un nod $v ≠ a$ activ (in raport cu taietura $C$) daca $v$ si ultimul nod adaugat inainte de $v$ se afla in multimi diferite. Fie $w(C)$ costul taieturii $C, A{~v~}$ multimea nodurilor adaugate inaintea lui $v, C{~v~}$ taietura lui $A{~v~} ∪ v$ indusa de $C$, iar $w(C{~v~})$ costul taieturii induse.
Vom arata prin inductie ca pentru fiecare nod activ _v_,
Vom arata prin inductie ca pentru fiecare nod activ $v$,
    _w(A{~v~}, v) ≤ w(C{~v~})_
$w(A{~v~}, v) ≤ w(C{~v~})$
# Pentru primul nod activ, propozitia de mai sus este adevarata deoarece avem egalitate.
# Presupunem adevarata propozitia pentru toate nodurile active adaugate inaintea unui nod activ _v_, si fie _u_ urmatorul nod activ ce urmeaza sa fie adaugat. Atunci avem:
# Presupunem adevarata propozitia pentru toate nodurile active adaugate inaintea unui nod activ $v$, si fie $u$ urmatorul nod activ ce urmeaza sa fie adaugat. Atunci avem:
    _w(A{~u~}, u) = w(A{~v~}, u) + w(A{~u~}\A{~v~}, u)_ = α
$w(A{~u~}, u) = w(A{~v~}, u) + w(A{~u~}\A{~v~}, u) = α$
In continuare, avem w(A{~v~}, u) ≤ w(A{~v~}, v), deoarece atunci cand a fost ales, nodul _v_ era mai puternic conectat decat _u_ in raport cu A{~v~}. Prin inductie avem w(A{~v~}, v) ≤ w(C{~v~}). Toate muchiile dintre A{~u~}\A{~v~} si _u_ conecteaza multimi diferite ale taieturii C. Deci ele contribuie la w(C{~u~}), dar nu si la w(C{~v~}). Asadar:
In continuare, avem $w(A{~v~}, u) ≤ w(A{~v~}, v)$, deoarece atunci cand a fost ales, nodul $v$ era mai puternic conectat decat $u$ in raport cu $A{~v~}$. Prin inductie avem $w(A{~v~}, v) ≤ w(C{~v~})$. Toate muchiile dintre $A{~u~}\A{~v~}$ si $u$ conecteaza multimi diferite ale taieturii $C$. Deci ele contribuie la $w(C{~u~})$, dar nu si la $w(C{~v~})$. Asadar:
    _α ≤ w(C{~v~}) + w(A{~u~}\A{~v~}, u) ≤ w(C{~u~})_
$α ≤ w(C{~v~}) + w(A{~u~}\A{~v~}, u) ≤ w(C{~u~})$
Concluzie: Cum _t_ este tot timpul un nod activ in raport cu C, putem concluziona ca _w(A{~t~}, t) ≤ w(C{~t~})_, ceea ce demonstreaza ca orice taietura _s-t_ are costul cel putin la fel de mare ca taietura faza.
Concluzie: Cum $t$ este tot timpul un nod activ in raport cu $C$, putem concluziona ca $w(A{~t~}, t) ≤ w(C{~t~})$, ceea ce demonstreaza ca orice taietura $s-t$ are costul cel putin la fel de mare ca taietura faza.
h2. Analiza complexitatii
In cadrul procedurii TaieturaMinima, vom apela procedura FazaTaieturiiMinime de O(|V|) ori. Observam ca in cadrul acestei din urma proceduri, avem nevoie de o structura de date care sa poata efectua in mod eficient urmatoarele operatii: _extrage_cheia_maxima_ si _creste_valoarea_unei_chei_. Putem folosi un heap Fibonacci pentru a efecuta operatia _extrage_cheia_maxima_ in {$O(log V)$} amortizat, iar pentru _creste_valoarea_unei_chei_ in {$O(1)$} amortizat, obtinand astfel o complexitate finala de {$O(|V|*|E| + |V|^2^*log |V|)$}. Nu recomand insa implementarea unei asemenea structuri in conditii de concurs, un heap binomial fiind suficient, obtinandu-se astfel o complexitate de {$O(|V|*|E|*log |V|)$}
In cadrul procedurii TaieturaMinima, vom apela procedura FazaTaieturiiMinime de $O(|V|)$ ori. Observam ca in cadrul acestei din urma proceduri, avem nevoie de o structura de date care sa poata efectua in mod eficient urmatoarele operatii: _extrage_cheia_maxima_ si _creste_valoarea_unei_chei_. Putem folosi un heap Fibonacci pentru a efecuta operatia _extrage_cheia_maxima_ in {$O(log |V|)$} amortizat, iar pentru _creste_valoarea_unei_chei_ in O(1) amortizat, obtinand astfel o complexitate finala de {$O(|V|*|E| + |V|^2^*log |V|)$}. Nu recomand insa implementarea unei asemenea structuri in conditii de concurs, un heap binar fiind suficient, obtinandu-se astfel o complexitate de {$O(|V|*|E|*log |V|)$}
h2. Probleme de taietura in concursurile de algoritmica
* Croco - .campion 2006/2007, runda 07
* Terrorists - TopCoder, SRM 334, divizia I
* 'Croco':problema/croco - .campion 2006/2007, runda 07
* 'Terrorists':http://www.topcoder.com/stat?c=problem_statement&pm=7246 - TopCoder, SRM 334, divizia I
* 'Sabotaj':problema/sabotaj - FMI No Stress 2010

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3700