Razapinjuće stablo — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
|||
Ред 31:
Broj ''t(G)'' razapinjućih stabala povezanog grafa je dobro proučena invarijanta. U nekim slučajevima, lako je izračunati ''t(G)'' direktno. Na primer, ako je ''G'' drvo samo po sebi, ''t(G)''=1, a ako je ''G'' cikličan graf <math>C_n</math> sa ''n'' vrhova, onda je ''t(G)'' = ''n''. Za bilo koji graf ''G'', broj ''t(G)'' se može izračunati koristeći Kirkhovu matrica-drvo teoremu.
Kajlejeva formula je formula za broj razapinjućih stabala u [[kompletan graf|kompletnom grafu]] <math>K_n</math> sa ''n'' vrhova. Formula
Ako je ''G'' potpun dvostrani graf <math>K_{p,q}</math> tada je <math>t(G)=p^{q-1}q^{p-1}</math>, dok je ''G'' ''n''-dimenzioni hiperkockasti graf <math>Q_n</math>, tada je <math>t(G)=2^{2^n-n-1}\prod_{k=2}^n k^{{n\choose k}}</math>. Ove formule su takođe posledice matrica-drvo teoreme.
| |||