Kirchhoffs træsætning

Fra Wikipedia, den frie encyklopædi
Spring til navigation Spring til søgning
Broom icon.svgDer 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.
Question book-4.svg

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 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 .