Exemplul considerat permite notarea următoarelor două caracteristici:
1 În lista s (G), nodurile pot fi repetate.
2. Când restabiliți copac ultima coaste se alătură în partea de sus a YP-2 și restul listei 1, 2, ..., p nu sunt egale cu partea de sus a YP-2.
Astfel, există o corespondență unu-la-unu între setul de arbori etichetați cu vârfuri p și setul de secvențe ale vârfurilor s (G). Numărul acestor secvențe este evident pp-2, care urma să fie dovedit.
Rețineți că printre arborii marcați pp-2 cu vârfuri p pot exista copaci izomorf.
Definiție 3. G1 subgrafic (X1, E1) a unui graf neorientat G (X, E) este numit un cadru sau un arbore de acoperire a graficului G, dacă G1 - arbore și X = X1.
Teorema 4. Un grafic G (X, E) are un schelet dacă și numai dacă este conectat.
Dovada. Nevoia pentru acest lucru este evidentă. Să dovedim suficiența. Fie G (X, E) un grafic conectat. Aflați dacă graficul G este muchie de ștergere, care nu încalcă conectivitatea grafului G. În cazul în care aceste margini nu este, atunci graful este un copac, în conformitate cu Teorema 1. Dacă o astfel de margine, cum ar fi un e, acolo, apoi aruncă afară și să vină la contele G1 (X, E1). Apoi efectuăm procedura specificată cu graficul G1, etc. După un număr finit de pași, scheletul graficului G este evident construit. Teorema este dovedită.
Dovada teoremei oferă un algoritm pentru construirea unui schelet într-un grafic conectat. Cu toate acestea, un grafic conectat poate avea mai multe schelete, deci este natural să puneți problema de a alege un schelet care să satisfacă condiții suplimentare.
Definiție 4. Un grafic cu margini încărcate (un grafic încărcat) este un grafic nedirecționat G (X, E), la fiecare margine eÎE din care corespunde numărului m (e) ³ 0, numit greutatea sau lungimea marginii e.
În mod similar, putem defini o digraph încărcat.
Poziționăm problema găsirii unui schelet G1 (X, E1) în graficul încărcat G (X, E) pentru care suma
este minimă. Un cadru cu această proprietate se numește schelet minimal. În conformitate cu teorema 4, fiecare grafic încărcat conectat are un schelet minimal. Această problemă apare în proiectarea liniilor de comunicații și electrice, a drumurilor, a conductelor etc. când sistemul este necesar pentru a conecta canalele de comunicare set noduri astfel încât oricare două noduri au fost conectate (eventual prin alte noduri), iar lungimea totală a canalelor de comunicare este redus la minimum; În acest caz, nodurile pot fi considerate ca noduri ale unui grafic încărcat ale cărui greutăți de margine corespund lungimii canalului de comunicare posibil între nodurile corespunzătoare. Apoi, rețeaua de canale dorită va fi scheletul minim al acestui grafic.
Algoritm pentru construirea unui schelet minimal
Fie G (X, E) un grafic încărcat conectat cu vârfuri p.
Pasul 1. Ca prima margine a scheletului minimal necesar, alegem o margine e1 cu cea mai mica greutate m (e1). Dacă există mai multe astfel de margini, atunci le luăm pe oricare dintre ele.
Pasul 2. Ca marginea a doua, luăm o margină e2 din setul E1 având greutatea m cea mai mică (e2) și astfel încât setul nu conține cicluri simple. Dacă există mai multe astfel de margini, atunci le luăm pe oricare dintre ele.
Pasul 3. Pentru marginea a treia alegem o margine e3 din setul E1 care are cea mai mica greutate m (e2) si pentru care setul nu contine cicluri simple. Dacă există mai multe astfel de margini, luăm oricare dintre ele.
Acest proces este repetat și după un anumit număr de pași k dă setul E =, la care este imposibil să se adauge o margine fără apariția unui ciclu. Subgraful G1 (X, E1) este scheletul minim al graficului G (X, E).
Justificarea algoritmului
Prin proprietatea 6 a teoremei 1, subgraful G1 (X, E1) construit este un arbore, deci k = p -1. Dovada minimalității scheletului G1 (X, E1) este împărțită în două etape. În primul rând să G (X, E) - un grafic complet cu greutatea tuturor marginilor sunt distincte, și lăsați-G2 (X, E2) - cadrul minim al graficului G. Dacă E2 ¹E1, apoi ia în considerare el - primul din multitudinea de muchii E1, E2 nu aparține . În coloană
în virtutea proprietății 6 din Teorema 1 există un ciclu unic simplu m. Ciclul m conține o margine e0ÏE1. Graficul G3 (X, E3), unde
, nu conține cicluri și are o margine n-1, deci este un copac. Setul este conținut în E2 și, prin urmare, nu conține cicluri. Apoi, în virtutea algoritmului de mai sus, m (e0)> m (el). Rezultă că greutatea totală a arborelui G3 (X, E3) este mai mică decât greutatea arborelui G2 (X, E2). Acest lucru contrazice cadru G2 este minimă, astfel încât E2 = E1 și G1 (X, E1) - un schelet minimal unic a graficului G.
Acum permiteți G (X, E) să fie un grafic conectat arbitrar. Dacă m (e1) = m (e2), atunci facem o substituție
m (e1) mm (e1) = m (e1) + e,
m (e2) m '(e2) = m (e2) + 2e,
luând e astfel încât greutățile m (e1) și m (e2) să fie conservate cu alte greutăți. Facem graficul G completat, adăugând astfel de margini
. În graficul rezultat, singurul schelet minimal este scheletul obținut cu ajutorul algoritmului considerat. Este ușor de observat că acest schelet este minim în graficul original G (X, E).
Figura 4 prezintă graficul încărcat G și scheletul său minim G1.
