Cycle Basis

一張圖上的一個環，可以表示成長度為E，值只有0或1的向量，0代表邊沒有出現在環上，1代表邊有出現在環上。（應該是Galois Field order E吧？）

從一張圖上找出一大堆環，作為基底，利用linear combination（xor運算）可得到圖上所有環。

cycle basis的數量為定值E-(V-1)。問題在於如何讓cycle basis總權重最小，這是P問題。

演算法目前有兩大類型，但是時間複雜度都很高。

主要的應用是紀錄化學結構。

Fundamental Cycle Basis

先從一張圖上找出一棵spanning tree，然後每一條cross edge都可以做出獨一無二的環，這些cross edge所形成的環，剛好構成E-(V-1)大小的cycle basis。

這個問題是NP-hard。