充分必要条件 二分图 二分图-二分图,二分图-充分必要条件

充分必要条件 二分图 二分图-二分图,二分图-充分必要条件

二分图又称作二部图,是图论中的一种特殊模型。

二分图_二分图 -二分图

二分图又称作二部图、两偶图,是图论中的一种特殊模型。设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。
简而言之,就是顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集。

二分图_二分图 -充分必要条件

无向图G为二分图的充分必要条件是,G至少有两个顶点,且其所有回路的长度均为偶数。
证先证必要性。
设G为二分图。由于X,Y非空,故G至少有两个顶点。若C为G中任一回路,令
C = (v0,v 1,v2,…,v l-1,v l = v0)
其中诸vi (i = 0,1,…,l)必定相间出现于X及Y中,不妨设
{v0,v2,v4,…,v l = v0} Í X
{v1,v3,v5,…,v l-1} Í Y
因此l必为偶数,从而C中有偶数条边。
再证充分性。
设G的所有回路具有偶数长度,并设G为连通图(不失一般性,若G不连通,则可对G的各连通分支作下述讨论)。
令G的顶点集为V,边集为E,现构作X,Y,使= G。取v0ÎV,置
X = {v | v= v0或v到v0有偶数长度的通路}
Y = V-X
X显然非空。现需证Y非空,且没有任何边的两个端点都在X中或都在Y中。
由于|V|≥2并且G为一连通图,因此v0必定有相邻顶点,设为v1,那么v1ÎY;故Y不空。
设有边(u,v),使uÎX,vÎX。那么,v0到u有偶数长度的通路,或u = v0;v0到v有偶数长度的通路,或v = v0。无论何种情况,均有一条从v0到v0的奇数长度的闭路径,因而有从v0到v0的奇数长度的回路(因从闭路径上可能删去的回路长度总为偶数),与题设矛盾。故不可能有边(u,v)使u,v均在X中。
“没有任何边的两个端点全在Y中”的证明可仿上进行,请读者思考。

二分图_二分图 -最大匹配

给定一个二分图G,在G的一个子图M中,M的边集中的任意两条边都不依附于同一个顶点,则称M是一个匹配。
求二分图最大匹配可以用最大流或者匈牙利算法。

最大匹配

给定一个二分图G,在G的一个子图M中,M的边集中的任意两条边都不依附于同一个顶点,则称M是一个匹配.
选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)
如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配.

匈牙利算法

求最大匹配的一种显而易见的算法是:先找出全部匹配,然后保留匹配数最多的.但是这个算法的复杂度为边数的指数级函数.因此,需要寻求一种更加高效的算法.
增广路的定义(也称增广轨或交错轨):
若P是图G中一条连通两个未匹配顶点的路径,并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径.
由增广路的定义可以推出下述三个结论:
1-P的路径长度必定为奇数,第一条边和最后一条边都不属于M.
2-P经过取反操作可以得到一个更大的匹配M'.
3-M为G的最大匹配当且仅当不存在相对于M的增广路径.
匈牙利算法
用增广路求最大匹配(称作匈牙利算法,匈牙利数学家Edmonds于1965年提出)
算法轮廓:
⑴置M为空
⑵找出一条增广路径P,通过取反操作获得更大的匹配M'代替M
⑶重复⑵操作直到找不出增广路径为止
g:array[1..maxn,1..maxm]of boolean;
y:array[1..maxm]of boolean;
link:array[1..maxm]of longint;
function find(v:longint):boolean;
var i:longint;
begin
for i:=1 to m do
if g[v,i] and (not y[ i ]) then
begin
y[ i ]:=true;
if (link[ i ]=0)or find(link[ i ]) then
begin
link[ i ]:=v;
find:=true;
exit;
end;
end;
find:=false;
end;
begin
//read the graph into array g[][]
for i:=1 to n do
begin
fillchar(y,sizeof(y),0);
if find(i) then inc(ans);
end;
其中n,m分别为2部图两边节点的个数,两边的节点分别用1..n,1..m编号
g[x][y]=true表示x,y两个点之间有边相连
link[y]记录的是当前与y节点相连的x节点
y记录的是y中的i节点是否被访问过.
算法的思路是不停的找增广轨,并增加匹配的个数,增广轨顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广轨的表现形式是一条"交错轨",也就是说这条由图的边组成的路径,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过.这样交错进行,显然他有奇数条边.那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推.也就是将所有的边进行"反色",容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对.另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再找到增广轨时,就得到了一个最大匹配.这也就是匈牙利算法的思路.
代码中find(i)就是寻找有没有从x点i开始的增广轨,如果有就进行上述操作,代码是递归的,所以看起来不是很显然,画个图试试就很清楚了.

二分图_二分图 -翻译成C语言

//其中n,m分别为2部图两边节点的个数,两边的节点分别用1..n,1..m编号
bool g[n][m];//g[x][y]表示x,y两个点之间有边相连
bool y[m];//y[i]记录的是y中的i节点是否被访问过.
int link[m];//link[y]记录的是当前与y节点相连的x节点
bool find(int v)
{
int i;
for(i=0;i
{
if(g[v][i]&&!y[i])
{
y[i]=true;
if(link[i]==0||find(link[i])
{
link[i]=v;
return true;
}
}
}
return false;
}
int main()
{
//read the graph int array g[][]
for(i=0;i
{
memset(y,0,sizeof(y));
if(find(i)) ans++;
}
return 0;
};i++)>;i++)>,e,y>,e,y>

  

爱华网本文地址 » http://www.413yy.cn/a/8103330103/61349.html

更多阅读

webplayer电影地址与下载方法转 - unity web player下载

webplayer播放资源用普通的嗅探方法并不能够找到要下载的连接,从这一方面说有效防止了盗版和盗链,不过,今天在网上看到了一个方法,虽然看起来比较麻烦,其实还是蛮简单的,个人整理了一下,以备后用。1. 首先下载一个网络嗅探器(局域网,校园网以

学好数学的必要条件 数学充分必要条件

经常有人同学或家长来信咨询数学怎么学的问题,从和他们沟通的过程中,我发现不少同学内心很想学好数学,可是不知道怎么付出行动。今天我就和大家谈谈学数学的事情,给出一些方法和建议,同学们趁此寒假,可以针对性补充或提高。数学真的那么

2012年安徽省高考理科数学第21题浅析 安徽省理科状元 金星

2012年安徽省高考理科数学第21题浅析2012年安徽省高考理科数学第21题:数列 满足(1)证明: 是递减数列的充分必要条件是 ;(2)求 的取值范围,使 是递增数列.笔者认为,这道试题的题型新颖别致,内涵深刻丰富,是一道匠心独具、十分难得的好题,对我

欧拉图与汉密尔顿图 加拿大汉密尔顿地图

欧拉图定义1:图G的一个回路,若他通过G中的每一条边,这样的回路成为欧拉回路,具有这种回路的图叫欧拉图定义2:无向连通图G是欧拉图的充分必要条件是G的每一个结点均具有偶次数 (有进有出)定义3:通过图G中每一条边的通路(非回路)称为欧拉通路。

矩阵的逆和伪逆 矩阵的伪逆

  对于矩阵A,如果存在一个矩阵B,使得AB=BA=E,其中E为与A,B同维数的单位阵,就称A为可逆矩阵(或者称A可逆),并称B是A的逆矩阵,简称逆阵。(此时的逆称为凯利逆)  矩阵A可逆的充分必要条件是|A|≠0。  伪逆矩阵是逆矩阵的广义形式。由于奇

声明:《充分必要条件 二分图 二分图-二分图,二分图-充分必要条件》为网友为将来而努力分享!如侵犯到您的合法权益请联系我们删除