Википедија

Razapinjuće stablo — разлика између измена

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Нема описа измене
Ред 10:
 
==Osnovni ciklusi==
Dodajući samo jednu granu u razapinjuće stablo ce stvoriti cikl; takav cikl se naziva '''osnovni cikl'''. Postoji poseban fundamentalni cikl za svaku ivicu; tako, postoji 1-1 korespodencija izmedjuizmeđu osnovnih cikala i grana koje nisu u razapinjućem stablu. Za povezan graf sa ''V'' vrhova, bilo koje razapinjuće drvo će imati ''V''-1 grana, i tako, graf od ''E'' grana će imati ''E''-''V''+1 osnovnih ciklova. Za bilo koje dato razapinjuće stablo ovi ciklovi će formirati bazu za prostor ciklova.
 
Sličan pojmu osnovnog cikla je pojam '''osnovni podskup'''. Brisanjem samo jedne grane razapinjućeg stabla, vrhovi će biti particionisani u dva disjunktna podskupa. Osnovni podskup je definisan kao skup grana koje moraju biti uklonjene iz grafa ''G'' da bi se ostvarila ista particija. Tako, postoji tacno ''V''-1 osnovnih podskupova grafa, po jedan za svaku granu razapinjućeg stabla.
 
Dualnost izmedjuizmeđu osnovnih podskupova i osnovnih ciklova je uvedena uz napomenu da se grane cikla koje nisu u razapinjućem stablu mogu pojaviti samo u podskupovima na drugim granama cikla; i obrnuto: grane podskupa se mogu pojaviti samo u onim ciklovima koji sadrže odgovarajuću granu podskupa.
 
==Razapinjće šume==
Преузето из „https://sr.wikipedia.org/wiki/Razapinjuće_stablo”