Kirchhoffs træ sætning

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

Kirchhoffs træ sætning - (Kirchhoff's theorem) - der er 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.