筆記

Minmum spanning tree 在一個無向連通圖中，一個包含所有頂點的樹稱為 spanning tree，若圖裡的連線有權重，則權重總和最小的 spanning tree 就是 Minmum spanning tree。而在一個圖中， MST 可能有好幾個。 每個頂點所相鄰權重最小的連線必定包含於 MST 之中。 將 MST 中某些點和連線合併後，剩下的樹仍然是合併後所產生之子問題的 MST。 由上兩點可知，此問題可使用貪婪演算法，將某些必包含於 MST 的點和連線合併後，在遞迴求剩餘圖的 MST。 Kruskal 演算法： 找到整個圖中權重最小的連線，將此連線相連的兩點合併，遞迴直到完成。時間複雜度為 O(E logV)。 (必須注意，若兩頂點已合併則之間的連線不可再使用。) Prim 演算法： 由某一點出發，找相鄰權重最小的連線，將連線兩端合併，遞迴。此演算法可使用 heap 達成，將出發點相鄰連線皆丟入堆疊中，再找出權重最小者，若連線的對面不是已合併的頂點，則將該頂點合併，且加入所有與它相鄰的連線於堆疊中。時間複雜度為 O(E logV)。

一、拉格朗日定理 coset： 若 H 是群 G 的子群， g 為 G 中元素， 則稱 Hg 為 H 包含 g 的 right coset 。 其中 Hg 即是 H 每個元素 h 與 g 相乘 (hg) 所成的集合。 (若是改變乘法方向則為 left coset。) 若 a,b 落在 H 的同一個 right coset ，則 a = hb，h 屬於 H。 H 的所有 right coset 會形成 G 的一個分割 (partition)。 (因為單位元素在 H 裡， G 裡的任一個元素必定在某個 coset 當中...) 若 H 為有限子群，則 H、Hg、gH 中的元素個數相同。 拉格朗日定理 ：若 G 是一個有限群，而 H 是一個子群，則 |H| 必整除 |G| 。 ( |為集合元素個數之符號| ) index of H ：|G|/|H|，在 G 之中 H 不同的 right coset 的個數。 若 G 為有限群，則 任意元素之 order 可整除 G 的元素個數 。 (任意元素皆可形成一個循環子群，拉格朗日定理) 若是 |G| = n，則 G 中任意元素的 n 次方皆為 1。 若是 |G| 為質數，G 必為循環群 。 尤拉函數 f(n) = 比 n 小且與 n 互質的正整數數量。 f(質數 p) = p-1。 f(兩質數相乘 p*q) = (p-1)*(q-1)。 f(n) = |Zn*|。 尤拉定理：a 的 f(n) 次方同餘 1 (mod n)，只要 a 與 n 互質。 費馬小定理：a 的 p-1 次方同餘 1 (mod p)，只要 p 是質數且 a 不是 p 的倍數。