Kirchhoffs træsætning

Der er ingen kildehenvisninger i denne artikel, hvilket er et problem. Du kan hjælpe ved at angive kilder til de påstande, der fremføres. Hvis ikke der tilføjes kilder, vil artiklen muligvis blive slettet.

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

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

${\displaystyle det(K_{i})=\tau (\Gamma )\,}$,

hvor ${\displaystyle \tau (\Gamma )}$ er antallet af udspændende træer i ${\displaystyle \Gamma }$.