Kirchhoffs træ sætning

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

Kirchhoffs træ sætning, opkaldt efter Gustav Kirchhoff, er en meget anvendt sætning indenfor det matematiske område grafteori. Sætningen omhandler antallet af udspændende træer i en graf. Nogle sætninger som følger af Kirchhoffs træ sætning er Cayleys formel, som omhandler antallet af udspændende træer i komplette grafer, samt Scoins formel som omhandler antallet af udspændende træer i de komplette todelte grafer.

Kirchoffs træ sætning[redigér | redigér wikikode]

Lad K være konduktansmatricen for en sammenhængende graf \Gamma og lad K_i være den matrix, der fås af K ved at man sletter række i og søjle i. Da er

det(K_i)=\tau(\Gamma) \,,

hvor \tau(\Gamma) er antallet af udspændende træer i \Gamma.