Kirchhoffs sætning

Inden for grafteori er Kirchhoffs sætning , også kaldet matrix-træ-sætning , opkaldt efter fysiker Gustav Kirchhoff , en sætning, der giver det nøjagtige antal spændende træer for enhver ikke-rettet graf. Det er en generalisering af Cayleys formel, der giver dette resultat for komplette ikke-retningsgivende grafer.

Stater

Kirchhoffs sætning er baseret på begrebet Laplacian matrix , i sig selv defineret som forskellen mellem matrixen af ​​grader og adjacency matrixen i grafen. Formelt for en graf, hvor den laplaciske matrix er defineret af: G=(V,E){\ displaystyle G = (V, E)}V={v1,⋯,vikke}{\ displaystyle V = \ {v_ {1}, \ cdots, v_ {n} \}}

(L)jeg,j: ={grader⁡(vjeg)hvis jeg=j-1hvis jeg≠j og (vjeg,vj)∈E0hvis ikke{\ displaystyle (L) _ {i, j}: = \ left \ {{\ begin {matrix} \ deg (v_ {i}) & {\ mbox {si}} i = j \\ - 1 & {\ mbox {si}} i \ neq j {\ mbox {et}} (v_ {i}, v_ {j}) \ i E \\ 0 & {\ mbox {ellers}} \ end {matrix}} \ højre. }

Kirchhoffs sætning erklæres som følger:

Sætning  -  Antallet af spændende træer i grafen er lige op til tegnet til værdien af ​​en hvilken som helst kofaktor af . G{\ displaystyle G}L{\ displaystyle L}

Eksempel

Beregning af Laplacian matrix

Vi beregner først den laplaciske matrix i denne graf:

• Spidsen 1 er af grad 2, og den er forbundet med hjørnerne 2 og 5  : den første kolonne er værd (2, -1, 0, 0, -1, 0) .
• Toppunktet 2 er af grad 3, og det er forbundet med hjørnerne 1 , 3 og 5  : den anden kolonne er værd (-1, 3, -1, 0, -1, 0) .
• Hovedet 3 er af grad 2, og det er forbundet med hjørnerne 2 og 4  : den tredje søjle er værd (0, -1, 2, -1, 0, 0) .
• Hovedet 4 er af grad 3, og det er forbundet med hjørnerne 3 , 5 og 6  : den fjerde søjle er værd (0, 0, -1, 3, -1, -1) .
• Hovedet 5 er af grad 3, og det er forbundet med hjørnerne 1 , 2 og 4  : den femte søjle er værd (-1, -1, 0, -1, 3, 0) .
• Spidsen 6 er af grad 1, og den er forbundet med toppunktet 4  : den sjette søjle er værd (0, 0, 0, -1, 0, 1) .

Dette giver den laplaciske matrix:

L=(2-100-10-13-10-100-12-10000-13-1-1-1-10-130000-101){\ displaystyle L = {\ begin {pmatrix} 2 & -1 & 0 & 0 & -1 & 0 \\ - 1 & 3 & -1 & 0 & -1 & 0 \\ 0 & -1 & 2 & - 1 & 0 & 0 \\ 0 & 0 & -1 & 3 & -1 & -1 \\ - 1 & -1 & 0 & -1 & 3 & 0 \\ 0 & 0 & 0 & -1 & 0 & 1 \\\ ende {pmatrix}}}

Beregning af en af ​​medfaktorerne

Vi fjerner derefter enhver række og enhver kolonne fra matrixen. Hvis vi f.eks. Sletter den tredje kolonne og den anden række:

L∗=(2-10-100-1-100003-1-1-1-1-13000-101){\ displaystyle L ^ {*} = {\ begin {pmatrix} 2 & -1 & 0 & -1 & 0 \\ 0 & -1 & -1 & 0 & 0 \\ 0 & 0 & 3 & -1 & -1 \\ - 1 & -1 & -1 & 3 & 0 \\ 0 & 0 & -1 & 0 & 1 \\\ slut {pmatrix}}}

Kofaktoren er . Ifølge Kirchhoffs sætning er der 11 spændende træer. det(L∗)=-11{\ displaystyle \ det (L ^ {*}) = - 11}

Verifikation

Grafen har faktisk 11 spændende træer, hvilket kan ses i følgende figur:

Tilfælde af ikke-relaterede grafer

Hvis startgrafen ikke er tilsluttet , vil den laplaciske matrix være diagonal efter blok . Ved at slette en række og en kolonne vil der være mindst en relateret komponent, som ingen kolonne er blevet slettet for. Summen af ​​kolonnerne i denne komponent er derefter nul, så enhver kofaktor er nul. Vi ser tydeligt det faktum, at kun tilsluttede grafer har spændende træer.

Demonstration

Trin 1

Lad være en hvilken som helst orientering af og den tilknyttede incidensmatrix : hvis den har knuder og kanter, er der en række- og kolonnematrix , hvis generelle udtryk er defineret af: D{\ displaystyle D}G{\ displaystyle G}M{\ displaystyle M}G{\ displaystyle G}ikke{\ displaystyle n}m{\ displaystyle m}M{\ displaystyle M}ikke{\ displaystyle n}m{\ displaystyle m}

mjeg,j: ={1hvis vjeg er halen på ej-1hvis vjeg er leder af ej0hvis vjeg∉ej{\ displaystyle m_ {i, j}: = \ left \ {{\ begin {matrix} 1 & {\ mbox {si}} v_ {i} {\ mbox {er halen på}} e_ {j} \\ - 1 og {\ mbox {si}} v_ {i} {\ mbox {er hovedet på}} e_ {j} \\ 0 & {\ mbox {si}} v_ {i} \ notin e_ {j} \ slut {matrix}} \ højre.}

Lad os beregne den generelle betegnelse for : det svarer til punktproduktet af to linjer af . Hvis , tæller derfor for kanter, der går ud fra, og for kanter, der ankommer til , derfor . Hvis , så hvis en kant forbinder til , uanset retning, og hvis ikke. M∗=MMt{\ displaystyle M ^ {*} = MM ^ {t}}M{\ displaystyle M}jeg=j{\ displaystyle i = j}mjeg,j∗{\ displaystyle m_ {i, j} ^ {*}}12{\ displaystyle 1 ^ {2}}vjeg{\ displaystyle v_ {i}}(-1)2{\ displaystyle (-1) ^ {2}}vjeg{\ displaystyle v_ {i}}mjeg,j∗=deg(vjeg){\ displaystyle m_ {i, j} ^ {*} = deg (v_ {i})}jeg≠j{\ displaystyle i \ neq j}mjeg,j∗=-1{\ displaystyle m_ {i, j} ^ {*} = - 1}vjeg{\ displaystyle v_ {i}}vj{\ displaystyle v_ {j}}0{\ displaystyle 0}

Så vi har: L=MMt{\ displaystyle L = MM ^ {t}}

2. trin

Vi overvejer kun de tilsluttede grafer, hvilket sikrer . Vi betragter derefter en firkantet undermatrix på . m≥ikke-1{\ displaystyle m \ geq n-1}B{\ displaystyle B}(ikke-1)×(ikke-1){\ displaystyle (n-1) \ times (n-1)}M{\ displaystyle M}

Undergrafen, der svarer til, indeholder derfor noder og kanter, så det er enten et spændende træ, eller det indeholder en cyklus. Hvis den indeholder en cyklus, vil summen af ​​de tilsvarende kolonner være nul, og derfor vil determinanten for også være nul. B{\ displaystyle B}ikke{\ displaystyle n}ikke-1{\ displaystyle n-1}B{\ displaystyle B}B{\ displaystyle B}

Hvis det ikke indeholder en cyklus, er det et spændende træ , der indeholder mindst to blade. har derfor mindst en række, der svarer til et blad, derfor en række, der indeholder null-udtryk og et udtryk lig med eller . Ved at udvikle determinanten med hensyn til denne linje opnår vi således en gentagelsesrelation på antallet af noder i grafen. Hvis grafen har en node, er den tomme matrix determinant ved konvention, så uanset værdien , hvis den repræsenterer et spændende træ , og hvis ikke,T{\ displaystyle T}B{\ displaystyle B}ikke-2{\ displaystyle n-2}1{\ displaystyle 1}-1{\ displaystyle -1}B{\ displaystyle B}ikke{\ displaystyle n}B{\ displaystyle B}1{\ displaystyle 1}ikke{\ displaystyle n}B{\ displaystyle B}T{\ displaystyle T}det(B)=±1{\ displaystyle \ det (B) = \ pm 1}det(B)=0.{\ displaystyle \ det (B) = 0.}

Trin 3

Vi får ved at fjerne en linje fra . Determinanten for er derfor en medfaktor for bortset fra tegnet. Ved Binet-Cauchy-formlen opnår vi: M∗{\ displaystyle M ^ {*}}M{\ displaystyle M}M∗(M∗)t{\ displaystyle M ^ {*} (M ^ {*}) ^ {t}}L{\ displaystyle L}

Kofaktor(L)=∑B∈H(det(B))2{\ displaystyle {\ mbox {Cofactor}} (L) = \ sum _ {B \ i {\ mathcal {H}}} (\ det (B)) ^ {2}}

hvor repræsenterer undermatricerne til . I henhold til trin 2 er vilkårene for summen lig med 1 for hvert spændende træ og ellers 0, som slutter beviset. H{\ displaystyle {\ mathcal {H}}}(ikke-1)×(ikke-1){\ displaystyle (n-1) \ times (n-1)}M∗{\ displaystyle M ^ {*}}

Ansøgninger

Cayleys formel

Kirchhoffs sætning giver et hurtigt bevis på Cayleys formel . Sidstnævnte indikerer, at den komplette graf har spændende træer. Kikke{\ displaystyle K_ {n}}ikkeikke-2{\ displaystyle n ^ {n-2}}

Demonstration

Den laplaciske matrix af en komplet graf med n- hjørner er en matrix af formen: ikke×ikke{\ displaystyle n \ times n}

Likke×ikke=(ikke-1-1-1-1⋱-1-1-1ikke-1){\ displaystyle L_ {n \ times n} = {\ begin {pmatrix} n-1 & -1 & -1 \\ - 1 & \ ddots & -1 \\ - 1 & -1 & n-1 \\\ slut {pmatrix}}}

For eksempel kan vi slette den første række og den første kolonne, så vi får en matrix af formularen: ikke-1×ikke-1{\ displaystyle n-1 \ times n-1}

Likke-1×ikke-1∗=(ikke-1-1-1-1⋱-1-1-1ikke-1){\ displaystyle L_ {n-1 \ times n-1} ^ {*} = {\ begin {pmatrix} n-1 & -1 & -1 \\ - 1 & \ ddots & -1 \\ - 1 & - 1 & n-1 \ \\ slutning {pmatrix}}}

For at lette beregningen af ​​determinanten af trækkes den første kolonne fra den anden kolonne fra hver kolonne deraf . Vi ved faktisk, at determinanten er uforanderlig efter forskellen i kolonner. Vi opnår: Likke-1×ikke-1∗{\ displaystyle L_ {n-1 \ times n-1} ^ {*}}VSjeg{\ displaystyle C_ {i}}VS1{\ displaystyle C_ {1}}

det(Likke-1×ikke-1∗)=|ikke-1-ikke-ikke⋯-ikke-ikke-1ikke0⋯00-10ikke⋯00⋮⋮⋮⋱⋮⋮-100⋯ikke0-100⋯0ikke|{\ displaystyle \ det (L_ {n-1 \ times n-1} ^ {*}) = {\ begin {vmatrix} n-1 & -n & -n & \ cdots & -n & -n \\ - 1 & n & 0 & \ cdots & 0 & 0 \\ - 1 & 0 & n & \ cdots & 0 & 0 \\\ vdots & \ vdots & \ vdots & \ ddots & \ vdots & \ vdots \\ - 1 & 0 & 0 & \ cdots & n & 0 \\ - 1 & 0 & 0 & \ cdots & 0 & n \\\ end {vmatrix}}}

Tilføj derefter alle de andre linjer til den første linje . Vi ved faktisk, at determinanten er uforanderlig med summen af ​​rækker. Vi opnår: L1{\ displaystyle L_ {1}}Ljeg{\ displaystyle L_ {i}}

det(Likke-1×ikke-1∗)=|100⋯00-1ikke0⋯00-10ikke⋯00⋮⋮⋮⋱⋮⋮-100⋯ikke0-100⋯0ikke|{\ displaystyle \ det (L_ {n-1 \ times n-1} ^ {*}) = {\ begin {vmatrix} 1 & 0 & 0 & \ cdots & 0 & 0 \\ - 1 & n & 0 & \ cdots & 0 & 0 \\ - 1 & 0 & n & \ cdots & 0 & 0 \\\ vdots & \ vdots & \ vdots & \ ddots & \ vdots & \ vdots \\ - 1 & 0 & 0 & \ cdots & n & 0 \\ - 1 & 0 & 0 & \ cdots & 0 & n \\\ end {vmatrix}}}

Ved at udvide i forhold til den første linje og ved at bemærke, at diagonalen indeholder gange antallet , opnår vi resultatet . ikke-2{\ displaystyle n-2}ikke{\ displaystyle n}t(Kikke)=ikkeikke-2{\ displaystyle t (K_ {n}) = n ^ {n-2}}

Tilfældig og algoritmisk generation

Kirchoffs sætning bruges til at generere spændende træer på en sandsynlig måde. Nogle probabilistiske algoritmer bruger derefter disse træer.

Historie

Kirchoffs sætning er en af ​​de første anvendelser af den laplaciske matrix i en graf. Dette objekt er nu meget udbredt, især i spektral teori om grafer .

Noter og referencer

1. (da) Shayan Oveis Gharan, "  Nylige fremskridt i tilnærmelsesalgoritmer: tilfældige spændende træer  " , på University of Washington ,2015.

Se også

Bibliografi

(en) John M. Harris, Jeffry L. Hirst og Michael J. Mossinghoff, Combinatorics and Graph Theory , New York, Springer, koll.  "Undergraduate Texts in Mathematics",19. september 2008, 2 nd  ed. , 381  s. ( ISBN  978-0-387-79711-3 , læs online ) , s.  47-50

Relaterede artikler

• Grafteori
• Spændende træ
• Kofaktor

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">