為什么我的標題要加上Kirchhoff's theorem呢,是因為之前我查這個定理是用這個英文在谷歌上查的,然后,,,,我看了20多分鐘的英文維基百科,然后爬墻去做別的題目了QAQ

---

?

行列式

?

前置知識

基礎的線性代數的知識

基本的數學知識

定義

?

名詞規定(其實就是一些可以一句話帶過的前置知識)(霧)

• 排列－＞就是把數字集合有序放置，如果是N階排列就是這個數字集合內數字為１～ｎ
• 逆序(對)－＞設一個數A位置為LL,另一個數B位置為GG,如果LL>GG但是A<B則稱其為逆序
• 奇OR偶排列－＞如果一個排列中逆序數目為奇數,就是奇排列,反之即為偶排列
  • 對換－＞把一個序列中任意兩個數對換位置，其余數不變，則稱其為一個對換
    • 一個定理，一次對換會改變序列的奇偶性
    • 證明：如果你調換的是一個逆序，則代表你消滅了一個逆序，所以逆序數目減一，由奇偶計算可知，逆序數目會變為相反的奇偶，同理，如果你調換的不是一個逆序，那么你增加了逆序數目＊１，所以逆序奇偶性發生變換．所以此定理成立

行列式定義為什么明明也是名詞定義的內容我要單獨拿出來呢,,,,因為我樂意略略路

• 對于一個矩陣，它的行列式是——
  

• N(i1,i2,i2..in)表示這個序列的逆序數目

• (i1,i2,...in)是一個1到n的排列

• 而一個n*n的矩陣行列式可以被記為det(A)，或者是|A|

• 用高斯消元實現

性質

• 行列互換，行列式不變

  • 就是把所有的ａ_i,j換為a_j,i??但是在N(XXX)中,每一個依舊都會再出現一次,最后的結果還是一樣的
    
• 兩行交換,行列式取反
  • 由對換的定理,我們可知,對換會改變排列的奇偶性,所以(-1)的指數奇偶性會變,所以行列式取反
• 行列式中,因子可以提出,行列式不發生改變
  • 首先是逆序，逆序只在意相對大小，所以不變化．其次是排列，就是把求和公式里提取一個公因數而已
    • 由對排列不變的證明（？）可知，如果某一行 *=k OR /=k，他也是不變的
• 某兩行相同，則行列式為０
  • 如果交換兩行，行列式變號，可矩陣沒有任何變化，所以行列式又應該不變。所以行列式為?0
  • 同理可知,若兩列成倍數關系,則行列式也是0
    
    • 其實就是提出一個公因子后,就變為了兩行相同了
• 某行加上了另一行的K倍,行列式也不會發生改變
  • 若ｉ行每一個數都增加了ｋ＊A_ｊ，則由∑的性質，我們可以把第ｉ行的求和公式拆為ｉ的求和加上ｋ＊Ａ_ｊ的求和公式，此時，后者和第ｊ行成倍數關系，所以求出的行列式為０，對最后答案沒影響，所以成立
• 一個矩陣行列式等于上三角矩陣的主對角線的乘積
  • 不清楚，不了解，不會證，背過它，我叫不知道

求解

利用高斯消元求解，由于精度問題，行列式不可出現小數（提問，小數是奇數還是偶數）所以要用輾轉相除法的高斯消元來求，時間復雜度是O(N^3logN)

?

1 inline int gauss(int n){ 2 //利用輾轉相除術進行高斯消元 3 //之所以用輾轉相除，只為了保持精度 4 int ans=1; 5 for(register int i=1;i<=n;i++){ 6 for(register int k=i+1;k<=n;k++){ 7 while(a[k][i]){ 8 int d=a[i][i]/a[k][i]; 9 for(register int j=i;j<=n;j++) 10 a[i][j]=(a[i][j]-1LL*d*a[k][j]%mod+mod)%mod; 11 swap(a[i],a[k]),ans=-ans; 12 //交換行，行列式改變 13 } 14 } 15 ans=1ll*ans*a[i][i]%mod,ans=(ans+mod)%mod; 16 //求解行列式 17 } 18 return ans; 19 }

?

---

矩陣樹定理----Kirchhoff's theorem

定義

(翻譯自維基百科并加上我的一些理解QAQ好怕出鍋)

在數學的圖論領域中,基爾霍夫定理或基爾霍夫矩陣樹定理，是由古斯塔夫·基爾霍夫所命名的一個算法.其算法是關于求解一個圖中的生成樹的數目.這個算法可以在計算器中,以拉普拉斯矩陣為基準,在以多項式時間內求解．同時，他作為Ｃayley公式的推廣，它可以在完全圖中求解出生成樹的數目．

基爾霍夫定理以拉普拉斯矩陣的定義為基礎．拉普拉斯矩陣等于原圖的度數矩陣(以矩陣的形式記錄每個點的出入度之和)減去鄰接矩陣(以矩陣的方式記錄點于點之間是否連邊,連邊為1,否則為0)之差．

對于給定的有N的點的連通圖G，我們用λ₁,?λ₂,?...,?λ_n?1來標記在拉普拉斯矩陣中特質值不為０(就是數值不為０）的點，生成樹的數目就是

舉個例子

在上圖中,菱形圖G的拉普拉斯矩陣Q為

?

接下來，構造一個矩陣Q^＊，構造方式就是在原矩陣Q中刪去任意第ｒ行和第ｒ列，以刪去第一行第一列為例

?

?

最后Q^＊的行列式可求得為８，故，原圖的生成樹數目也為８

NOTICE(譯者加)：此算法適用于無向圖中，允許重邊和自環在維基百科下面還有證明，但是由于譯者（懶）水平有限，故而無法翻譯或者自己給出證明方式，感興趣的同學可以去看看這篇博客給出的證明．

NOTICE(譯者加)：關于鄰接矩陣與度數矩陣

• 鄰接矩陣就是若原圖中兩點（x,y）有邊，則 G(x,y)++,G(y,x)++;
• 度數矩陣就是若原圖中點x與y有邊,則D(x,x)++,D(y,y)++;
• 所以可以簡化為a[x][y]--,a[y][x]--,a[x][x]++,a[y][y]++;

求解

1 inline void add(int x,int y){ 2 --a[x][y],--a[y][x],++a[x][x],++a[y][y]; 3 //構造基爾霍夫矩陣 4 } 5 6 inline int gauss(int n){ 7 //利用輾轉相除術進行高斯消元 8 //之所以用輾轉相除，只為了保持精度 9 int ans=1; 10 for(register int i=1;i<=n;i++){ 11 for(register int k=i+1;k<=n;k++){ 12 while(a[k][i]){ 13 int d=a[i][i]/a[k][i]; 14 for(register int j=i;j<=n;j++) 15 a[i][j]=(a[i][j]-1LL*d*a[k][j]%mod+mod)%mod; 16 swap(a[i],a[k]),ans=-ans; 17 //交換行，行列式改變 18 } 19 } 20 ans=1ll*ans*a[i][i]%mod,ans=(ans+mod)%mod; 21 //行列式求解 22 } 23 return ans; 24 } 25 26 int ans=1; 27 ans=1ll*ans*gauss(n-1)%mod; 28 //求解N*N大小的矩陣的生成樹數目

---

后記

注冊博客園賬號更多的是心血來潮，但是還是感謝可能存在的因為我的博客而受益的人愿意看，以及某P姓大佬的,,,,,菲克．可能是因為這篇博客耗費我時間最長了（不算查資料和準備時間，我從早上九點寫到十二點），所以可能才會有這篇后記吧．也算是一個難忘的回憶了．希望我AFO幾年后，等到我心態更成熟一些時,看著我寫過的東西，笑著說，這就是我曾經的青春啊，玫金色的愛戀伴以蔚藍色的憂傷，白銀色的筆尖輔以淺紫色的鍵盤，機房中回蕩的笑聲加上哭泣的眼淚，如同初春的青梅，苦澀與甜蜜交織，畫出我記憶中最美好的時光

NOTICE：本博客代碼參考自Siyuan,如有侵權,立馬修改

轉載于:https://www.cnblogs.com/fallen-down/p/11206442.html

總結

以上是生活随笔為你收集整理的学习小记-----行列式矩阵树定理Kirchhoff's theorem的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。