勵志

勵志人生知識庫

割集怎么找

要找割集,可以按照以下步驟進行:

確定要分析的電路或網絡,並利用圖論的知識將其轉化爲有向圖,選擇一箇參考點。

從有向圖中選擇一棵樹,這棵樹應包含所有節點且不形成迴路。可以移除樹中的一條邊,形成兩個部分,割集就是將圖分成這兩部分的邊的集合。

確定割集中的邊,一箇割集至少包含樹中的一條邊和一些枝(非樹邊)。確保移除割集中的邊後,原圖會變成不連通的。

綜合所有的割集,形成割集集合。每個割集都是原圖中一些邊的集合,當這些邊被移除時,原圖會變成不連通的。

舉例來說,如果有條支路3,可以先找出以它爲基礎的基本割集。然後移除所有連支,形成一棵樹。接着移除支路3,這時樹被分成兩部分N1和N2。在N1部分的底部和N2的左端分別畫箭頭,然後將支路3和連接N1、N2的連支(如1、4、6)連接起來,就構成了一箇基本割集。這個過程可以用於尋找電路或其他網絡中的割集。