二分图的讲解

二次图内符号含义学习二次图前应该首先知道二次图内各符号所代表的含义或装置。

下面表格中列举了本图中一些常见符号：进线柜一次接线示意图进线开关柜交流电流回路1、计量回路计量回路的作用主要是将小电流传至智能电度表中，用于电能的计算。

检修或更换电度表时切记勿将电流互感器二次侧开路。

2、测量回路测量回路主要是将小电流传至综保装置，用于电流的检测。

后台显示的电流即取于此处。

3、线路保护回路此图中故障录波的作用就是实时监控电流变化，在发生故障时为判断故障提供判断依据，提高故障处理速度。

4、母线保护回路同样是监控电流变化，达到故障设定值作用于跳闸或告警。

5、零序保护回路线路柜后面都可看到在电缆上装有零序电流互感器，作用就是监控零序电流，将信号传至小电流选线装置柜用于告警及故障查找，再传至综保装置用于告警或跳闸。

进线开关柜交流电压回路1、电度计量图中DFY也相当于一个接线端子，不过次接线端子上带有短接片，即可将电流互感器短路，也可将电压互感器开路。

进线开关柜开入开出原理图1、综保装置外部开入开出接线图此图中QA为柜内控母小空开，QF、S8、S9、S均为断路器内部触点，S8为试验位置触点，S9为工作位置触点，在试验位置时S8闭合，离开实验位置时S8断开，到达工作位置时S9闭合，离开后S9断开。

S为断路器储能触点，储能成功闭合，未储能断开。

QK为开关柜上远方/就地转换开关，JD为接地刀触点，接地刀合上就闭合，接地刀拉开为断开。

6LP为开关柜上置检修状态压板。

2、综保装置内部开入开出接线图图中KKJ为合后位置继电器，可以用于区分是正常分闸还是故障分闸。

TWJ为跳位继电器，用于综保上跳位指示。

HWJ为合位继电器，用于综保上合位指示。

进线开关柜控制原理图上图为开关柜的控制原理图，看懂此图也就知道了我们的开关柜是怎么控制的，都经过哪些设备控制分合的。

QA为控制小母线空开，In为综保装置，KK为合分闸转换开关，HC为合闸线圈，TQ为分闸线圈，Y1为合闸闭锁电磁铁，LP都为压板，DL为断路器内辅助触点。

Maigo的KM算法讲解(的确精彩)顶点Ｙｉ的顶标为B［i]，顶点Xi与Yj之间的边权为w[ｉ,j]。

在算法执行过程中的任一时刻，对于任一条边(ｉ,j),A［i]+B[j]>=w［i,ｊ]始终成立。

KM 算法的正确性基于以下定理：* 若由二分图中所有满足A［i］+B[j]=ｗ[ｉ,ｊ］的边（i，ｊ)构成的子图（称做相等子图）有完备匹配,那么这个完备匹配就是二分图的最大权匹配。

这个定理是显然的。

因为对于二分图的任意一个匹配，如果它包含于相等子图,那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图,那么它的边权和小于所有顶点的顶标和。

所以相等子图的完备匹配一定是二分图的最大权匹配。

初始时为了使A［ｉ]＋B[j]>=w[i,j]恒成立,令A[i]为所有与顶点Xi关联的边的最大权，Ｂ[ｊ］＝0。

如果当前的相等子图没有完备匹配,就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。

我们求当前相等子图的完备匹配失败了,是因为对于某个Ｘ顶点,我们找不到一条从它出发的交错路。

这时我们获得了一棵交错树,它的叶子结点全部是X顶点。

现在我们把交错树中X顶点的顶标全都减小某个值ｄ,Y顶点的顶标全都增加同一个值d，那么我们会发现：两端都在交错树中的边(i，j）,A［i]+B[j]的值没有变化。

也就是说,它原来属于相等子图，现在仍属于相等子图。

两端都不在交错树中的边(ｉ，ｊ)，A[i］和B[j]都没有变化。

也就是说,它原来属于(或不属于)相等子图，现在仍属于(或不属于)相等子图。

X端不在交错树中，Y端在交错树中的边(i，ｊ)，它的Ａ［ｉ]+B[j]的值有所增大。

它原来不属于相等子图,现在仍不属于相等子图。

X端在交错树中,Ｙ端不在交错树中的边（i,j),它的A［ｉ]+B[j]的值有所减小。

也就说,它原来不属于相等子图，现在可能进入了相等子图,因而使相等子图得到了扩大。

现在的问题就是求d值了。

完全2-分图的l-边-连通度
王斌;罗光耀
【期刊名称】《重庆工商大学学报（自然科学版）》
【年(卷),期】2007(24)3
【摘要】连通图G所谓的l-边-连通度(ι-edge-connectivity),就是使图G成为至少ι个分支所必须去掉的最少边数,记作λι(G),即λι(G)=min{ㄧE'
ㄧ∶E'E(G),ω(G-E')≥ι}.研究了完全2-分图的ι-边-连通度,得到了定理:设
G=G[V1,V2]是一个完全2-分图,V1=r,V2=s,r+k=s,k≥0为整数.则图G的(k+2)-边-连通度为(k+1)r,即λk+2(G)=r(k+1).
【总页数】3页(P223-224,227)
【作者】王斌;罗光耀
【作者单位】重庆工商大学,理学院,重庆400067;重庆工商大学,理学院,重庆400067
【正文语种】中文
【中图分类】O157.5
【相关文献】
1.三次图的完全扩容图的连通度 [J], 萨如拉;阿勇嘎
2.3-正则Cayley图的l-边-连通度 [J], 雷澜
3.二部图2-等周边连通度最优的充分条件 [J], 段晋芳;原军
4.关于二分图的线连通度的一个结论 [J], 潘登斌
5.关于二分图的线连通度的一个结论 [J], 潘登斌
因版权原因，仅展示原文概要，查看原文内容请购买。

二分图的定义二分图的定义非常简单，有两组顶点，一组顶点记为L ，另一组记为R ，L 和R 没有公共的元素，并且所有的边都是连接L 和R 中的点的，对于L 和R 本身，它们内部的任何两个点都没有边相连，这样的无向图就叫二分图。

《组合数学》上这样讲解：二分图可描述为：一，顶点的集合；二，将该顶点集分成两部分的一个划分；三，连接一部分的一个顶点与另一部分的一个顶点的边的集合。

二分图是无向图，那么什么样的无向图是二分图呢？有以下定理：定理：无向图G 为二分图的充分必要条件是，G 至少有两个顶点, 且其所有回路的长度均为偶数。

证明：至少两个顶点，这个显然，把这个条件忽略掉，着重考虑回路长度为偶数这一条件。

先证充分性：由于图中可能有回路也可能无回路，无回路的情况应该最简单，自然考虑分类讨论。

于是，分类讨论后，充分性的证明转化成以下两个命题：a)所有无回路的无向图都是二分图；b)所有有回路且回路长度为偶数的无向图都是二分图。

对于a) ，因为无回路无向图总是能把它画成一棵树，所以，这个命题等价于：所有的树都是二分图。

到这里，命题a) 证明显然，因为有一种很简单的从树构造二分图的方法：令树的奇数层的结点为集合L ，令树的偶数层结点为集合R ，这样就从树得到了一个二分图。

再看命题b) ，可以把b) 转化为a) 。

对于图中的每一个回路，我们都从中拿掉一条边，这样可以消灭所有的回路，由a) 知消灭掉所有回路之后的图是二分图。

把此时得到的二分图画成一棵树，拿掉一条边后的回路此时就是树中的一条路径，并且路径的长度为奇数，这就意味着路径的头结点和尾结点所在层数的编号一个是奇数一个是偶数，用上面的从树构造二分图的方法知，头结点和尾结点分别在集合L 中和集合R 中，我们再把拿掉的这条边加上去，只不过是在L 和R 中的两个顶点间连接了一条边，图仍然是原来的二分图。

至此，充分性得证。

再证必要性。

假设二分图中的一条回路是(v0, v1, v2, …, vm, v0) ，由于是二分图，相邻顶点必不属于同一个集合，用L 标记属于集合L 的点，用R 标记属于集合R 的点，不妨假设v0 属于L ，则上面的回路可以标记为L, R, L, R, …, L, R ，由此可见，回路必有偶数个顶点，因此必有偶数条边。

学习二等分1．通过操作活动让幼儿感知很多物体(图形)能够分成相等的二份，并知道整体大于部分，部分小于整体及等分后的一份叫整体的二分之一。

2．培养幼儿探求知识的兴趣及解决问题的水平。

【活动准备】1．幼儿人手一份不同形状、不同颜色的图形(◇□△○)，操作材料若干(绸带、橡皮泥、米、苹果)。

【活动过程】一、幼儿第一次尝试(探索实物的二等分)1．提出要求：今天老师给小朋友绸带、，橡皮泥、米、苹果。

请小朋友动脑筋把这些实物分成两个相同的部分，就是分后的两个部分是一模一样的(重复一次，加以强调)，能够利用尺子、剪刀这些工具来分。

2．幼儿尝试，教师巡视鼓励幼儿积极动手、动脑，遇到问题自己想办法解决(时间5分钟)。

3．反馈尝试结果。

二、幼儿第二次尝试学习几何图形的二等分，探索怎样的图形能够“二等分”1．提出要求：(出示几何图形)生活中有很多的东西可二等分，今天老师给你们准备的是几何图形，现在请小朋友用折的办法把几何图形二等分，看看是不是所有的图形都能够二等分。

2．幼儿尝试，教师巡视，引导幼儿能够相互讨论。

(放音乐)3．幼儿反馈尝试结果。

三、游戏“抢金钥匙”1．讲解要求和玩法(出示背景图)。

下面我们来玩抢金钥匙的游戏，游戏时我们分成三组，每组都要回答很多题目，就是区别这些卡片上的实物是不是二等分，记住每人只答一题，答对了前进一步，再请后面的小朋友答，后面的若答错了，请别的小朋友帮忙，哪队先拿到金钥匙哪队为胜，回答是不是二等分声音一定要响亮。

2．幼儿游戏，教师判断幼儿答得是否准确，如错误禁止前进。

3．游戏结束。

总结。

【算法】⼆分图的判定⼆分图的判定 给定⼀个具有n个顶点的图。

要给图上每个顶点染⾊，并且要使相邻的顶点颜⾊不同。

判断是否能最多⽤两种颜⾊进⾏染⾊。

题⽬保证没有重边和⾃环。

概念：把相邻顶点染成不同颜⾊的问题叫做图的着⾊问题。

对图进⾏染⾊所需要的最⼩颜⾊数称为最⼩着⾊度。

最⼩着⾊度为2的图称作⼆分图。

分析：如果只⽤两种颜⾊，那么确定⼀个顶点的颜⾊之后，和它相邻的顶点的颜⾊也就确定了。

因此，选择任意⼀个顶点出发，依次确定相邻顶点的颜⾊，就可以判断是否可以被2种颜⾊染⾊了。

这个问题⽤深度优先搜索可以简单实现。

#include <bits\stdc++.h>using namespace std;#define MAX_V 1000//输⼊vector<int> G[MAX_V]; //图int V; //顶点数int color[MAX_V]; //顶点的颜⾊（1 or -1）//顶点v，颜⾊cbool dfs(int v,int c){color[v] = c;//把当前顶点相邻的顶点扫⼀遍for(int i = 0;i < G[v].size(); i++){//如果相邻顶点已经被染成同⾊了,说明不是⼆分图if(color[G[v][i]] == c) return false;//如果相邻顶点没有被染⾊,染成-c,看相邻顶点是否满⾜要求if(color[G[v][i]] == 0 && !dfs(G[v][i],-c)) return false;}//如果都没问题，说明当前顶点能访问到的顶点可以形成⼆分图return true;}void solve(){//可能是不连通图，所以每个顶点都要dfs⼀次for(int i = 0;i < V; i++){if(color[i] == 0){//第⼀个点颜⾊为 1if(!dfs(i,1)){cout << "No" << endl;return;}}}}int main(){//输⼊}。

⼆分图匹配Hopcroft-Carp算法详解⼆分图基本最⼤匹配 集合X中有n个点，集合Y中有m个点，X与Y间共有E条边。

　匈⽛利算法 O(n*m) . jpg 每次从⼀个结点出发搜索匹配点，当且仅当搜到的结点未匹配或匹配后更优时，匹配。

1 #include<cstdio>2 #include<string>3 #include<cstring>4 #include<vector>56const int N = 1000 + 10;78int n, m, e, mry[N];9bool vis[N];10 std::vector <int> Q[N];1112int read() {13int x = 0, f = 1;14char c = getchar();15while (!isdigit(c)) {16if (c == '-') f = -1;17 c = getchar();18 }19while (isdigit(c)) {20 x = (x << 3) + (x << 1) + (c ^ 48);21 c = getchar();22 }23return x * f;24 }2526bool DFS(int u) {27int size = Q[u].size();28for (int i = 0; i < size; ++ i)29if (!vis[Q[u][i]]) {30 vis[Q[u][i]] = 1;31if (!mry[Q[u][i]] || DFS(mry[Q[u][i]])) {32 mry[Q[u][i]] = u;33return1;34 }35 }36return0;37 }3839int main() {40 n = read(), m = read(), e = read();41for (int i = 1; i <= e; ++ i) {42int u = read(), v = read();43if (u <= n && v <= m) Q[u].push_back(v);44 }45int ans = 0;46for (int i = 1; i <= n; ++ i) {47 memset(vis, 0, sizeof vis);48if (DFS(i)) ++ans;49 }50 printf("%d\n", ans);51return0;52 }匈⽛利算法　Hopcroft-Carp 算法 O(sqrt(n)*E) 由于⽹上对HC的讲解很少，因此我想在这⾥讲讲HC。