Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- c) Pentru a alege $l$ a.i. sa aiba loc egalitatea $p_{l}(s;t;G)=k_{l}(s;t;G)$ pentru $\forall$ graf $G$, vom alege mai intai toate cazurile unde $p_{l}(s;t;G)$ si $k_{l}(s;t;G)$ sunt egale cu $0$. Ele sunt egale cu $0$ in momentul in care nu se gaseste niciun drum de lungime maxim $l$ intre $s$ si $t$ $\Rightarrow$ asta este valabil pentru $\forall$ $l\in \lbrace 2,..., min(d(s,t))-1 \rbrace$, unde $min(d(s,t))$ reprezinta lungimea celui mai scurt drum de la $s$ la $t$. Mai ramane de ale un singur $l$ si anume atunci cand $l$ are fix lungimea celui mai mic drum de la $s$ la $t$. Cand avem un singur drum de lungime minima intre cele doua varfuri $\Rightarrow$ ca si $p_{l}(s;t;G)$ si $k_{l}(s;t;G)$ sunt ambele egale cu 1. Cand avem insa n drumuri de lungime minima avem 2 cazuri:\\
- 1. Toate drumurile sunt disjuncte, in acest caz vom avea $p_{l}(s;t;G)=n$ si $k_{l}(s;t;G)=n$, deoarece avem nevoie de fix $n$ noduri pentru a deconecta $s$ de $t$.\\
- 2. Avem k drumuri disjuncte. In acest caz avem numarul maxim de drumuri disjuncte care $\exists$ intre $s$ si $t$ este reprezentat de $k$. Pentru a deconecta $s$ si $t$ in cel mai eficient mod (alegand numarul minimi de noduri) este evident ca vom deconecta nodurile comune mai multor drumuri, care este, in cazul nostru fix numarul de drumuri disjuncte.\\
- Deci si in cazul in care $l$ are lungimea celui mai mic drum de la $s$ la $t$ are loc egalitatea $p_{l}(s;t;G)=k_{l}(s;t;G)$.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement