Arborele de întindere minim

Arborele de întindere minim (sau arborele de întindere minim ) dintr-un grafic ponderat conectat (nedirecționat)  este arborele de întindere al acestui grafic care are greutatea minimă posibilă, unde greutatea arborelui este suma greutăților marginilor sale.

Exemplu

Problema găsirii arborelui de întindere minim apare adesea într-un cadru similar: să presupunem că există n orașe care trebuie conectate prin drumuri, astfel încât să se poată ajunge din orice oraș în oricare altul (direct sau prin alte orașe). Este permisă construirea de drumuri între anumite perechi de orașe și se cunoaște costul construirii fiecărui astfel de drum. Este necesar să se decidă ce drumuri să construiască pentru a minimiza costul total al construcției.

Această problemă poate fi formulată în termenii teoriei grafurilor ca problema găsirii arborelui de întindere minim într-un graf ale cărui vârfuri reprezintă orașe, marginile sunt perechi de orașe între care se poate așeza un drum direct, iar greutatea muchiei este egală. la costul construirii drumului corespunzător.

Algoritmi

Există mai mulți algoritmi pentru găsirea arborelui de acoperire minim. Unele dintre cele mai faimoase sunt enumerate mai jos:

• algoritmul lui Prim ,
• Algoritmul lui Kruskal (sau algoritmul lui Kruskal),
• algoritmul lui Boruvka ,
• Algoritm de ștergere inversă (obținerea unui arbore de acoperire minim dintr-un grafic ponderat cu margini conectat).

Sarcini conexe

Problema arborelui Steiner este similară cu problema arborelui de întindere minimă . Conține mai multe puncte pe plan și este necesar să se așeze un grafic al căilor între ele, astfel încât să se minimizeze suma lungimilor căilor. Principala diferență față de problema arborelui de întindere minim în acest caz este că este permisă adăugarea de puncte de ramificație suplimentare pentru a reduce și mai mult suma lungimilor marginilor. Problema arborelui Steiner este NP-complet .

Literatură

• Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Chapter 23. Minimum spanning trees // Algorithms: construction and analysis = Introduction to Algorithms / Ed. I. V. Krasikova. - Ed. a II-a. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .