De ce contează?
Ai o rețea de cabluri care leagă toate serverele unei firme — un arbore, fără nicio legătură în plus. Cineva îți oferă un cablu nou, mult mai ieftin decât unul dintre cele montate. Îl montezi: apare o buclă — exact una, nici mai multe. Tai cel mai scump cablu de pe buclă și rețeaua e din nou arbore, dar mai ieftină. Acest schimb banal — pui o muchie, scoți alta — este argumentul cu care se demonstrează corectitudinea algoritmilor Kruskal și Prim.
Ce este
Din lecția despre arbori știi definiția și echivalențele („conex + n-1
muchii" etc.). Aici le transformăm în unelte de demonstrație — exact cele pe
care le vei folosi la arborele parțial de cost minim (APM):
- Lanțul unic. Între oricare două noduri
ușivexistă exact un lanț. Nu „măcar unul" — fix unul. Orice muchie de pe acest lanț e un pod obligatoriu întreușiv. - O muchie în plus → exact UN ciclu. Adaugi muchia nouă
(u, v): ea închide unicul lanțu … vîntr-un ciclu. Fiindcă lanțul era unic, ciclul e unic — un al doilea ciclu ar cere un al doilea lanț, care nu există. - Schimbul. Din ciclul abia format ștergi orice altă muchie
f: capetele luifrămân legate prin restul ciclului, deci graful e tot conex, iar numărul de muchii revine lan-1— ai din nou un arbore, doar că a schimbat o muchie cu alta (și, într-un graf ponderat, costul). - Cel puțin două frunze. Orice arbore cu măcar două noduri are cel puțin
două noduri de grad
1— capetele celui mai lung lanț nu pot avea alți vecini. E motorul demonstrațiilor prin inducție: smulgi o frunză și rămâi tot cu un arbore, pen-1noduri.
Primele trei unelte formează împreună o singură mișcare — schimbul de muchii:
Schimbul de muchii (exchange argument): într-un arbore, adaugi o muchie → apare exact un ciclu; ștergi orice altă muchie de pe acel ciclu → ai tot un arbore, cu alt cost. Dacă muchia scoasă era mai scumpă decât cea adăugată, noul arbore e strict mai ieftin — deci arborele inițial nu era minim. Pe acest raționament se sprijină corectitudinea lui Kruskal și Prim: orice arbore care „refuză" o muchie ieftină obligatorie poate fi îmbunătățit printr-un schimb.