Îl extindem la un copac minim, și îl desemnează. În cazul în care marginea, atunci lema este dovedit, prin urmare, luăm în considerare cazul când marginea. Luați în considerare calea de la vârf la vârf. Deoarece aceste vârfuri aparțin diferitelor părți ale tăieturii, cel puțin o margine a căii intersectează tăierea, o numim. Prin ipoteza lemnei. Înlocuim marginea c cu o margine. Arborele rezultat este, de asemenea, copacul minim al grafului, deoarece toate vârfurile sunt încă conectate și greutatea arborelui nu a crescut. Prin urmare, puteți adăuga la arborele minim de spanning din grafic, adică marginea este sigură.
[citare necesară] de asemenea
[edit] Surse de informare
Trimiteți-le prietenilor: