割集计算方法

❶ 求助一个离散数学问题

复习一下“割集”，“点割集”，“边割集”“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、协助设计系统，故障树分析可以作为设计工具，创建输出或较低层模组的需求。