Razapinjuće stablo — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
|||
Ред 12:
Dodajući samo jednu granu u razapinjuće stablo će stvoriti cikl; takav cikl se naziva '''osnovni cikl'''. Postoji poseban fundamentalni cikl za svaku ivicu; tako, postoji 1-1 korespodencija između osnovnih ciklova 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
Dualnost izmeđ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.
| |||