Spring til indhold

Kirchhoffs træsætning

Fra Wikipedia, den frie encyklopædi

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 | rediger kildetekst]

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

,

hvor er antallet af udspændende træer i .