キルヒホッフの定理

数学のグラフ理論の分野において、キルヒホッフの定理、またはグスタフ・キルヒホッフにちなんで名付けられたキルヒホッフの行列木定理は、グラフ内の全域木の数に関する定理であり、この数はグラフのラプラシアン行列の部分行列の行列式から多項式時間で計算できることを示している。具体的には、この数はラプラシアン行列の任意の余因子に等しい。キルヒホッフの定理は、完全グラフ内の全域木の数を提供するケイリーの公式を一般化したものである。

キルヒホッフの定理は、グラフのラプラシアン行列の概念に依存しており、これはグラフの次数行列（頂点の次数の対角行列）と隣接行列（頂点が隣接しているエントリに対応する場所に 1 が、そうでない場合は 0 になる (0,1) 行列）の差に等しくなります。

n 個のラベル付き頂点を持つ連結グラフGに対して、そのラプラシアン行列の非ゼロ固有値をλ ₁、  λ ₂、 ...、  λ _{n −1とする。すると、} Gの全域木の数は

${\displaystyle t(G)={\frac {1}{n}}\lambda _{1}\lambda _{2}\cdots \lambda _{n-1}\,.}$

キルヒホッフの1847年の論文の英訳はJBオトゥールによって作成され、1958年に出版されました。^[1]

まず、例のダイヤモンド グラフGのラプラシアン行列Qを構築します(右の図を参照)。

${\displaystyle Q=\left[{\begin{array}{rrrr}2&-1&-1&0\\-1&3&-1&-1\\-1&-1&3&-1\\0&-1&-1&2\end{array}}\right].}$

次に、 Qから任意の行と任意の列を削除して行列Q ^*を作成します。たとえば、行1と列1を削除すると、次のようになります。

${\displaystyle Q^{\ast }=\left[{\begin{array}{rrr}3&-1&-1\\-1&3&-1\\-1&-1&2\end{array}}\right].}$

最後に、 Q ^*の行列式を取ってt ( G )を取得します。ダイヤモンド グラフの場合は 8 になります。(この例では、 t ( G ) はQの (1,1) 補因子であることに注意してください。)

（以下の証明はコーシー・ビネの公式に基づいています。キルヒホッフの定理の基本的な帰納的議論は、ムーア（2011）の654ページにあります。^[2]）

まず、ラプラシアン行列には、任意の行と任意の列にわたる要素の合計が 0 になるという特性があることに注目してください。したがって、行と列を追加し、それらを入れ替え、行または列に -1 を掛けることで、任意のマイナーを他の任意のマイナーに変換できます。したがって、余因子は符号まで同じであり、実際に同じ符号を持つことが検証できます。

次に、マイナーM ₁₁の行列式が全域木の数を数えることを示します。n をグラフの頂点の数、m をグラフの辺の数とします。接続行列Eはn行m列の行列で、次のように定義できます。( i , j ) がグラフのk番目の辺であり、 i < jであるとします。すると、E _ik = 1、E _jk = −1 となり、列kの他のすべての要素は0 になります (この修正された接続行列Eを理解するには、有向接続行列を参照してください)。前の例 ( n = 4、m = 5) の場合:

${\displaystyle E={\begin{bmatrix}1&1&0&0&0\\-1&0&1&1&0\\0&-1&-1&0&1\\0&0&0&-1&-1\\\end{bmatrix}}.}$

ラプラシアンL は、接続行列とその転置行列の積に因数分解できることを思い出してください。つまり、L = EE ^Tです。さらに、F を最初の行を削除した行列Eとすると、 FF ^T = M ₁₁となります。

コーシー・ビネの公式により、次のように書ける。

${\displaystyle \det \left(M_{11}\right)=\sum _{S}\det \left(F_{S}\right)\det \left(F_{S}^{\mathrm {T} }\right)=\sum _{S}\det \left(F_{S}\right)^{2}}$

ここで、S はサイズn − 1 の [ m ]のサブセットにまたがり、F _{S は}、 S内のインデックスを持つFの列である( n − 1) 行 ( n − 1) 列の行列を表します。すると、すべてのS は元のグラフのn − 1 個の辺を指定し、それらの辺が全域木を誘導するのはF _Sの行列式が +1 または -1 の場合のみであり、それらの辺が全域木を誘導しないのは行列式が 0 の場合のみであることが示されます。これで証明は完了です。

ケイリーの公式は、キルヒホッフの定理の特別なケースとして従います。これは、ある場所で 1、別の場所で -1、他の場所で 0 であるすべてのベクトルが、完全グラフのラプラシアン行列の固有ベクトルであり、対応する固有値がnであるためです。これらのベクトルは一緒にn − 1次元 の空間に広がるため 、他にゼロ以外の固有値は存在しません。

あるいは、ケイリーの公式は完全グラフK _nの異なるラベル付き木の数を数えるので、K _nのラプラシアン行列の任意の余因子を計算する必要があることに注意する。この場合のラプラシアン行列は

${\displaystyle {\begin{bmatrix}n-1&-1&\cdots &-1\\-1&n-1&\cdots &-1\\\vdots &\vdots &\ddots &\vdots \\-1&-1&\cdots &n-1\\\end{bmatrix}}.}$

上記の行列の任意の余因子はn ^{n −2}であり、これはケーリーの公式です。

キルヒホッフの定理は多重グラフにも当てはまります。行列Qは次のように変更されます。

• エントリq _{i,j は}− mに等しく、ここでm はiとj の間のエッジの数です。
• 頂点の次数を数えるとき、すべてのループは除外されます。

単純グラフはm = 1 のマルチグラフであるため、完全マルチグラフのケイリーの公式は、上記と同じ方法でm ^{n −1} ( n ^{n −1} −( n −1) n ^{n −2} )となります。

キルヒホッフの定理は、ラプラシアン行列の定義を変更することで強化できます。各頂点から発する辺を数えたり、頂点のペアを接続したりするのではなく、各辺に不定値ラベルを付け、修正されたラプラシアン行列の ( i , j ) 番目のエントリを、 i がj と等しくない場合のi番目とj番目の頂点間の辺に対応する不定値の合計、および iがjと等しい場合のi番目の頂点から発する辺に対応するすべての不定値の負​​の合計とします。

任意の行と列を削除することによって修正されたラプラシアン行列の行列式は（元のラプラシアン行列から全域木の数を見つけるのと同様）、グラフの辺に対応する不定値における同次多項式（キルヒホッフ多項式）になります。項を収集し、可能なすべてのキャンセルを実行した後、結果の式の各単項式は、その単項式に現れる不定値に対応する辺で構成される全域木を表します。このようにして、行列式を計算するだけで、グラフのすべての全域木の明示的な列挙を取得できます。

この定理の証明についてはBollobás (1998)を参照のこと。^[3]

グラフの全域木はグラフィックマトロイドの基底を形成するため、キルヒホッフの定理はグラフィックマトロイドの基底の数を数える公式を提供します。同じ方法は、グラフィックマトロイドの一般化である通常のマトロイドの基底の数を数えるのにも使用できます(Maurer 1976)。

キルヒホッフの定理は、有向多重グラフ内の有向全域木の数を数えるように修正することができます。行列Qは次のように構成されます。

• 異なるiとjのエントリq _{i,j は}− m に等しくなります。ここで、m はiからjへのエッジの数です。
• エントリq _{i,i は、} iの入次数からiでのループ数を引いた値に等しくなります。

頂点iを根とする有向全域木の数は、Qのi番目の行と列を削除して得られる行列の行列式である。

キルヒホッフの定理は、重み付けされていないグラフ内のk成分全域森を数えることに一般化できる。 ^[4] k成分全域森とは、すべての頂点を含み、サイクルのない、つまり各頂点のペアの間に最大1つのパスしかない、 k個の連結成分を持つ部分グラフである。連結成分を持つこのような森Fが与えられたとき、その重みを各成分の頂点数の積として定義する。すると ${\textstyle F_{1},\dots ,F_{k}}$${\textstyle w(F)=|V(F_{1})|\cdot \dots \cdot |V(F_{k})|}$

${\displaystyle \sum _{F}w(F)=q_{k},}$

ここで、合計はすべてのk成分全域森林にわたっており、多項式の 係数である。${\textstyle q_{k}}$${\textstyle x^{k}}$

${\displaystyle (x+\lambda _{1})\dots (x+\lambda _{n-1})x.}$

多項式の最後の因数は、固有値がゼロであることによる。より明確に言えば、この数は次のように計算できる。 ${\textstyle \lambda _{n}=0}$${\textstyle q_{k}}$

${\displaystyle q_{k}=\sum _{\{i_{1},\dots ,i_{nk}\}\subset \{1\dots n-1\}}\lambda _{i_{1}}\dots \lambda _{i_{nk}}.}$

ここで、和はのn − k要素部分集合全体にわたる。例えば、 ${\textstyle \{1,\dots ,n\}}$

${\displaystyle {\begin{aligned}q_{n-1}&=\lambda _{1}+\dots +\lambda _{n-1}=\mathrm {tr} Q=2|E|\\q_ {n-2}&=\lambda _{1}\lambda _{2}+\lambda _{1}\lambda _{3}+\dots +\lambda _{n-2}\lambda _{n-1}\\q_{2}&=\lambda _{1}\dots \lambda _{n-2}+\lambda _{1}\dots \lambda _{n-3}\lambda _{n-1}+\dots +\lambda _{2}\dots \lambda _{n-1}\\q_{1}&=\lambda _{1}\dots \lambda _{n-1}\\\end{aligned}}}$

n −1 個のコンポーネントを持つ全域木の場合には1 つのエッジに対応するため、k = n −1 の場合はQの固有値の合計がエッジの数の 2 倍になることを示します。k = 1 の場合は、すべての全域木の重みがnであるため、元のキルヒホッフの定理に対応します。

証明は、キルヒホッフの定理の証明と同様に行うことができます。接続行列の可逆な部分行列は、各コンポーネントの頂点を選択できる kコンポーネント スパニング フォレストに全単射的に対応します。${\displaystyle (nk)\times (nk)}$

係数はQの特性多項式の係数の符号までです。 ${\textstyle q_{k}}$

• 木に関するトピックのリスト
• BEST定理
• マルコフ連鎖木定理
• 最小全域木
• 試験シーケンス

• キルヒホッフの定理の証明