sarcina de a găsi minime se întinde Graficul copac

Probleme aplicate de teoria grafurilor

Această problemă apare în proiectarea de linii electrice, conducte, drumuri, etc. atunci când este necesar pentru a conecta un sistem de canal central specificat (link-uri), astfel încât oricare două centre au fost conectate direct sau prin intermediul altor canale, și că lungimea totală (costul) de canale de comunicații a fost minimă.

Definiția. Un grafic se numește echilibrat dacă marginile sau arcelor sale sunt atribuite anumite numere (greutate).

Definiția. Backbone se întinde copac sau grafic este un subgraf conectat de cicluri fără a conține toate nodurile din graficul inițial. Subgrafic cuprinde o parte sau toate muchiile graficului original.

Într-o coloană poate fi izolată prin mai multe nuclee (Figura 5.1.).

Figura 5.1 Diverse schelete grafic K3.3

Problema arborelui minim se întinde este formulat după cum urmează: într-un grafic conectat suspendat pentru a găsi scheletul greutate minimă, adică scheletul, greutatea totală a cărei margini este minimă.

Luați în considerare algoritmul Kruskal pentru construirea arborelui minim se întinde a graficului. Scheletul este construit treptat, se adaugă o margine la fiecare pas. Algoritmul utilizează două reguli.

1) Prima margine a miezului - marginea minimă de greutate în graficul original.

2) În cazul în care scheletul a fost deja adăugat (i au muchia greutate minimă între margini, care nu sunt încă incluse în cadrul
și nu formează cicluri de margini deja adăugate.

Figura 5.2 schelet minim

Exemplul 5.1. Găsiți arborele minim se întinde într-un grafic (Figura 5.2.).

Construcția miezului va începe cu marginile (v1, vj), deoarece are o greutate minimă (puteți începe cu nervurile (v2, v5)). Cum să se alăture coaste la miezul:

Rețineți că nervurile (v2, v3), (v1, v5) nu au fost incluse în cadru, deși au avut o greutate mai mică decât nervura (v4, v5) coaste, deoarece ele formează bucle deja incluse.

Un alt exemplu de aplicare a acestei probleme. Să presupunem că avem o mulțime de aerodromuri, și aveți nevoie pentru a determina minimul (suma distanțelor), set de zboruri, ceea ce ar permite să zboare de pe orice aeroport la orice. Soluția la această problemă ar fi arborele minim se întinde de un grafic complet al distanțelor dintre aerodromuri

În continuare, vom enumera doar sarcinile care apar în teoria grafic și în utilizarea practică. Algoritmi pentru soluționarea lor dincolo de domeniul de aplicare al acestui curs.