割集計算方法

❶ 求助一個離散數學問題

復習一下「割集」，「點割集」，「邊割集」「k，λ，δ」的定義，根據定義，寫出每個圖形的所有點割集，邊割集，計算一下。比較一下，就完成了。

❷ 一個具有7條支路4個結點的電路，連支和獨立割集數目分別是多少

先將每個支路等效成一個復阻抗，然後根據電路的網路結構將電路看成一一埠網路，計算出這個一埠網路的等效復阻抗，然後就像計算普通電流一樣，電壓除以復阻抗。最後得出的是含有虛部的電流值，也就是說這個電流和電壓之間有角度差

❸ DNA法求最小生成樹的編程

為了改進粘貼模型,提出了用生 化實驗實現求解割集的計算方法,並基於該方法給出了最小生成樹DNA演算法.首次將分離實驗擴展為基於分離板的分離實驗和基於電泳技術的分離實驗,所提出的 最小生成樹DNA演算法打破了DNA計算的計算模式——用求解割集的最小邊的方法逐步產生最小生成樹.用該方法求解割集利用了分離實驗運算的高度並行性,最 小生成樹DNA演算法的時間復雜度是線性的,從而降低了演算法的時間復雜度.

❹ 大學問題解答；最小割集，頂上事件概率 題目解答

咨詢記錄 · 回答於2021-08-05

❺ 電路割集定義中指出若移出割集,圖將變成兩部分,這個所謂的"兩部分"是什麼意思,一個結點算不算一部分

點算一個部分，方法基本是圍繞一個點分割開，這樣就成兩個部分了。點是一部分，另外的是一部分。按定義，這個點和另外那部分只要連上一個支路圖仍連同。把所有點找完後，可以把相連的兩個點和兩點之間的支路看成一部分，與其他的部分割開。

❻ 你好啊，老師。怎麼求最小割端集的數目，最小割邊集和最小混合割集的數目萬分感謝O(∩_∩)O~開心每一天

不好意思一年沒有編最小割了基本快忘了
最小割一般都是做邊割集，
至於點割集，只要把一個點拆成2個點，再連一條邊就行
最小割=最大流啊，如果只要輸出一個數量那直接一遍最大流就行
如果要輸出點集、邊集就會稍微麻煩一點

找到以前寫的一個程序，發現看一看還是蠻有用的（雖然效率低，但是容易懂）
題目是USCO 5.4的TELECOWMUNICATION
題目意思就是求N個點S-T的最小點割集
我的程序我貼一下吧（很爛的演算法，看看就行，別學）

procere dfs(k,dep:longint); //數據弱，深搜求最大流
var
i:longint;
procere go;
var
i,min:longint;
begin
min:=maxlongint;
for i:=1 to dep-1 do
if a[path[i],path[i+1]]<min then min:=a[path[i],path[i+1]];
for i:=1 to dep-1 do
begin
dec(a[path[i],path[i+1]],min);
inc(a[path[i+1],path[i]],min);
end;
tot:=tot+min;
end;
begin
visited[k]:=true;
path[dep]:=k;
if k=s then
begin
go;
ok:=true;
exit;
end;
for i:=1 to n do
begin
if ok then exit;
if not visited[i] then
if a[k,i]>0 then
dfs(i,dep+1);
end;
end;
begin
assign(input,'telecow.in');
assign(output,'telecow.out');
reset(input);
rewrite(output);
fillchar(a,sizeof(a),0);
readln(n,m,t,s);
t1:=t;s1:=s;
for i:=1 to n do begin a[i*2-1,i*2]:=1; a[i*2,i*2-1]:=1; end;
for i:=1 to m do //拆點
begin
readln(x,y);
a[x*2-1,y*2]:=1;
a[y*2-1,x*2]:=1;
end;
n:=n*2;
for i:=1 to n do for j:=1 to n do f[i,j]:=a[i,j];
t:=t*2-1; s:=s*2;
tot:=0;
repeat
fillchar(visited,sizeof(visited),false);
ok:=false;
dfs(t,1);
until not ok;
writeln(tot);
temp:=tot;
p:=false;
for i:=1 to n div 2 do
if i<>t1 then
if i<>s1 then
begin
a:=f;
a[i*2-1,i*2]:=0;a[i*2,i*2-1]:=0;
tot:=0;
repeat
fillchar(visited,sizeof(visited),false);
ok:=false;
dfs(t,1);
until not ok; //看i是不是一定在最小割集中
if tot<temp then
begin
temp:=tot;
if p then write(' ');
write(i);
p:=true;
f[i*2,i*2-1]:=0; f[i*2-1,i*2]:=0; //在的話刪除
end;
end;
writeln;
close(input);
close(output);
end.
其實還是很容易理解的，但效率不高

下面說下求最小割集最普遍，也是效率很高的演算法：Stoer-Wagner演算法
其實就是n遍最大生成樹，具體方法很容易搜到
1.min=MAXINT，固定一個頂點P
2.從點P用類似prim的s演算法擴展出「最大生成樹」，記錄最後擴展的頂點和最後擴展的邊
3.計算最後擴展到的頂點的切割值（即與此頂點相連的所有邊權和），若比min小更新min
4.合並最後擴展的那條邊的兩個端點為一個頂點（當然他們的邊也要合並）
5.轉到2，合並N-1次後結束
6.min即為所求，輸出min
這種方法加上堆優化就很快了

我二分圖什麼的非常弱，也許幫不上你什麼忙
你也可以自己到網上找Stoer-Wagner的標程研究一下

❼ 割集容量怎麼算

管道網路中每條邊的最大通過能力（容量）是有限的，實際流量不超過容量。
最大流問題(maximum flow problem)，一種組合最優化問題，就是要討論如何充分利用裝置的能力，使得運輸的流量最大，以取得最好的效果。求最大流的標號演算法最早由福特和福克遜於1956年提出，20世紀50年代福特(Ford)、福克遜(Fulkerson)建立的「網路流理論」，是網路應用的重要組成成分。

❽ 圖論割集問題

回答樓主,圖論大多問題的解決,需要用到遍歷演算法,判斷割集我想不會有其它演算法,遍歷的演算法目前是圖論中最基本最重要的演算法,當然對一些特殊的圖可能會有其它方法.遍歷演算法的計算復雜度不是很大的,是多項式演算法,在計算機上可以實現.當然在選取邊和點時應考慮技巧性,這恐怕是個難題,否則會出現組合爆炸,就象貨郎擔問題一樣,比如選擇點可以首先考慮選取度數最大的點,選取邊一定要選不在迴路上的邊.這需要你的智慧.
割集分為點割集和邊割集,對一個圖G=(V,E)來說如果存在一個結點集V的子集,從G中刪除這些結點後,它的連通分圖的個數增多,則稱該子集為點割集,對一個連通圖來說,刪除這些結點後,連通圖變為不連通.點割集一般不是唯一的,含有最小結點個數的點割集稱為最小點割集,類似可定義邊割集和最小邊割集,僅含1個點的點割集稱為割點,僅含1個邊的邊割集稱為割邊,割邊也稱為橋.
求一個連通簡單圖的割集的演算法,我想可用遍歷的演算法,目前常用的是深度優先搜索或者廣度優先搜索演算法來做,這是圖論中最基本的演算法,這種演算法可求出圖的連通分圖的個數,以此來判斷某子集是否是割集.

❾ 故障樹割集怎麼算

於故障樹分析法的結構函數定義如下： 設故障樹（FT）中有n個底事件 ，C ∈ 為某些底事件的集合，當其中全部底事件都發生時，頂事件必然發生，則稱C為故障樹的1個割集。

若C是1個割集，且任意去掉其中1個底事件後就不再是割集，則稱C為最小割集。若FT 有k個最小割集，只要有1個最小割集 ( j =1，2，…k )中的全部底事件X 均發生，故障必定發生。

k個最小割集中，只要有一個發生，頂事件就發生。

(9)割集計算方法擴展閱讀：

故障樹分析可以用於：

1、了解最上方事件和下方不希望出現狀態之間的關系。

2、顯示系統對於系統安全/可靠度規范的符合程度。

3、針對造成最上方事件的各原因列出優先次序：針對不同重要性的量測方式建立關鍵設備/零件/事件的列表。

4、監控及控制復雜系統的安全性能（例如：特定某飛機在油料閥x異常動作時是否可以安全飛行？此情形下飛機可以飛行多久）。

5、最小化及最佳化資源需求。

6、協助設計系統，故障樹分析可以作為設計工具，創建輸出或較低層模組的需求。