De ce contează?
Ești inginerul care trebuie să lege cu fibră optică toate cele 10 localități ale unui județ. Constructorii ți-au trimis oferte pentru zeci de tronsoane posibile, fiecare cu prețul lui. Orice schelet care leagă tot — orice arbore parțial — rezolvă problema tehnic. Dar contabilul nu te întreabă „e conex?", ci „cât costă?". Două scheleturi cu exact același număr de tronsoane pot diferi cu milioane de lei. Din acest capitol, întrebarea nu mai e „există un arbore parțial?", ci „care dintre ei e cel mai ieftin?".
Ce este
Recapitulare rapidă din lecția Arbore parțial (capitolul de noțiuni): un
arbore parțial al unui graf conex cu n noduri păstrează toate nodurile
și doar o parte din muchii, astfel încât rezultatul să fie arbore — conex și
fără cicluri. Numărul de muchii e forțat: exact n - 1, iar un astfel de
arbore există dacă și numai dacă graful e conex. Cel mai simplu obții unul cu o
parcurgere DFS sau BFS, păstrând muchiile de descoperire.
Până aici, orice arbore parțial era la fel de bun. Capitolul acesta schimbă regula jocului: muchiile primesc costuri.