生成數(shù)計數(shù)

對于一個無向簡單圖，$n$個點和$n?1$條邊構(gòu)成一個生成樹，生成樹計數(shù)就是求這個無向圖中一共有幾種不同的生成樹(任意兩邊不同)

• 度矩陣
  $n\times n$ 的矩陣，統(tǒng)計每個點的度數(shù)，只有$i=j$時矩陣才有正值，其余為零。
• 鄰接矩陣
  $n\times n$ 的矩陣，如果$（u，v）$存在邊，對應(yīng)矩陣$g[u][v]=g[v][u]=1$，其余為零。
• 拉普拉斯矩陣(Laplacian matrix) 也叫做導(dǎo)納矩陣、基爾霍夫矩陣(Kirchhoff)或離散拉普拉斯算子，主要應(yīng)用在圖論中，作為一個圖的矩陣表示。
  度矩陣 - 鄰接矩陣

生成樹的個數(shù)就是Kirchhoff矩陣$n?1$階行列式的值
行列式模板

對于有重邊的情況，拉普拉斯矩陣矩陣也能用.

例題

• ACcode
• UVA 10766
  題意：公司的一些部門不能存在直接的隸屬關(guān)系，問一共有多少分配部門關(guān)系的方案
  生成樹計數(shù)的裸題，把不能直接隸屬的標記一下，求出矩陣就行
• SPOJ DETER3
  裸題
• URAL 1627
  題意：讓所有相鄰的臥室連成一個生成樹，枚舉每個點的四個方向求出矩陣
• HDU 4305
  題意：給出$n$個點，兩點之間距離不超過一定距離的點可以相互傳染，但是中間不能有其他的點。
  暴力枚舉所有點如果符合第一個條件，再暴力判斷兩點之間是不是有第三個點。
  需要判斷點在不在線段上，首先叉積看3點是否共線，然后判斷點是不是在兩點確定的矩形內(nèi)部
• HDU 4408
  題意：帶權(quán)生成樹，求一共有幾個最小生成樹。
  Kruskal思想，從最小的點開始合并，權(quán)值相同的邊不會影響的下一個權(quán)值的合并。我們只需求所有權(quán)值情況下的生成數(shù)個數(shù)，然后相乘。
  中間用到縮點存在重邊，不過不影響矩陣的性質(zhì)
• SPOJ HIGH
  裸題

總結(jié)

以上是生活随笔為你收集整理的Matrix-Tree （生成树计数）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。