列出连通集

第３７卷　

Ｖｂ１．３７　第１０期　

ＮＯ．１０　计算机工程　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２０１１年５月　

Ｍａｖ　２０１１　

・软件技术与数据库・　文章编号：１ｏｏ　＿３４２８（２ｏ１１）１　＿＿００５５—＿０３　文献标识码：Ａ　中田分类号：ＴＰ３１１．５２　

最小连通支配集问题的化简算法　

高文字　

（广东商学院信息学院，广州５　１０３２０）　

摘要：分析连通支配集的支配性约束和连通性约束条件，提出２条针对简单无向连通图最小连通支配集问题的化简规则。规则通过对图　

中节点的邻节点进行分类以及寻找图的割点提前确定一些必选节点，同时删除一些多余节点，从而降低原问题的规模。从理论上证明了化　

简规则的正确性，并通过随机仿真实验验证化简规则的有效性。　关奠词：最小连通支配集；化简；参数算法；复杂性　

Ｒｅｄｕｃｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　

Ｍｉｎｉｍｕｍ　Ｃｏｎｎｅｃｔｅｄ　Ｄｏｍｉｎａｔｉｎｇ　Ｓｅｔ　Ｐｒｏｂｌｅｍ　

ＧＡＯＷｅｎ－ｙｕ　

（Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　Ｓｃｈｏｏｌ，Ｇｕａｎｇｄｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＢｕｓｉｎｅｓｓ　Ｓｔｕｄｉｅｓ，Ｇｕａｎｇｚｈｏｕ　５１０３２０，Ｃｈｉｎａ）　

［Ａｂｓｔｒａｃｔ］Ｂｙ　ａｎａｌｙｚｉｎｇ　ｔｈｅ　ｄｏｍｉｎａｎｔ　ｃｏｎｓｔｒａｉｎｔｓ　ａｎｄ　ｃｏｎｎｅｃｔｉｖｉｔｙ　ｃｏｎｓｔｒａｉｎｔｓ　ｏｆ　ｃｏｎｎｅｃｔｅｄ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ，ｔｗｏ　ｒｅｄｕｃｔｉｏｎ　ｒｕｌｅｓ　ｆｏｒ　ｍｉｎｉｍｕｍ　

ｃｏｎｎｅｃｔｅｄ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ　ｉｎ　ｓｉｍｐｌｅ　ｃｏｎｎｅｃｔｅｄ　ｇｒａｐｈ　ｉｓ　ｐｒｏｐｏｓｅｄ．Ｔｈｅｓｅ　ｒｕｌｅｓ　ｃａｎ　ｆｉｎｄ　ｏｕｔ　ｓｏｍｅ　ｒｅｑｕｉｒｅｄ　ｎｏｄｅｓ　ａｎｄ　ｄｅｌｅｔｅ　ｓｏｍｅ　ｒｅｄｕｎｄａｎｔ　ｎｏｄｅｓ　ｉｎ　ａｄｖａｎｃｅ　ｔｈｒｏｕｇｈ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ｏｆ　ｎｅｉｇｈｂｏｒｓ　ｏｆ　ａｎｙ　ｎｏｄｅ，ａｎｄ　ｔｈｒｏｕｇｈ　ｆｉｎｄｉｎｇ　ｃｕｔ　ｎｏｄｅｓ　ｉｎ　ｇｒａｐｈ，ｔｈｕｓ　ｒｅｄｕｃｉｎｇ　ｔｈｅ　ｓｉｚｅ　ｏｆ　ｔｈｅ　ｏｒｉｇｉｎａｌ　ｐｒｏｂｌｅｍ．　

IOI2005国家集训队作业：图的连通度问题研究 长郡中学 任恺

图的连通度问题研究

1．图的连通度的定义

图要么是连通的，要么是不连通的。但对于任意连通图来说，它们的连通程度也可能是不同的。为了精确地体现连通的程度，下面将引入两个概念：边连通度和顶点连通度。

设G = (V, E)是一个n阶图。如果G是完全图Kn，那么我们定义它的顶点连通度为

κ(Kn) = n – 1

否则，定义它的顶点连通度为

κ(G) = min{|U| : Gv-u是非连通的}

即最小顶点数，删除这些顶点便是非连通图。

图G的边连通度定义为从图G中删除边而使G非连通的最小边数，用λ(G)表示。

这里的图G=(V, E)代表无向图或有向图，且没有自环和重边。

下面将主要讨论无向图的边连通度，有向图的边连通度和顶点连通图可以以此类推。

2．无向图的边连通度

在无向图G中，令顶点v的度数deg(v)表示与顶点v相连的边的数目。无向图G的最小度δ(G)定义为：δ(G) = min{deg(v) | v属于G}。考虑有向图G中，v的入度表示为in-deg(v)，v的出度表示为out-deg(v)，相应的最小度为：δ(G) =

min{in-deg(v), out-deg(v)| v属于G}。在整篇文章中，图的点数用n表示，边数用m表示。

另u和v表示图G中的一对不相同的点。定义λ(u, v)表示从图G中删除最少的边，使得u和v之间不存在任何路径。在有向图G中，λ(u, v)表示从G中删除最少的弧(有向边)，使得不存在任何从u到v的有向路径。注意到，在无向图中，有λ(u, v) =λ(v, u)，在有向图中却不符合这个等式。

显然，λ(u, v)就是图中u和v的最小割。求两点之间的最小割，根据最大流IOI2005国家集训队作业：图的连通度问题研究 长郡中学 任恺

最小割定理，可以用最大流算法求解：令u为网络的源点，v为网络的汇点，每条边的容量为1，u到v的最大流便是u和v之间的最小割。预流推进算法可以在O(nm)时间复杂度下求出最大流。另外，每条边的容量都为1，可以用Hoproft算法在()Onm的时间复杂度下求出单位容量网络的最大流。具体算法的实现不在本文讨论范围之内，这里不再赘述。

电子科技大学二00四至二00五年第二学期

电路分析 (120分钟) 考试日期2005年 月 日

题号 1 2 3 4 5 选择题 总分

得分

阅卷人

一、选择题 (请将正确结果的代号，如A、B、C、D填入括号内，只有一个正确结果)

1．对于含有b条支路、n个结点的平面连通集总参数电路，可以列（ ）个网孔方程

A、b个 B、b-n+1 C、b-1 D、n-1

2．在电路分析中，集总假设条件：（其中λ：波长；f：频率；L：电路尺寸）。

A、 λ << L B、f >> 50MHz C、λ >> L

D、f << 50MHz

3．如图3所示，求支路电流＝（ A ）

A、-9A B、-10A

C、-7A D、-3A

4．如图4所示电路中电压U等于（ D ）

A、4V B、6V

C、-4V D、-6V

5．如图5所示，求单口的等效电导G等于（ C ）

A、0.091 S B、1.37 S

C、1 S D、2 S

6．如图6所示，求单口的等效电阻R＝( B )

A、7Ω B、-7Ω

C、14Ω D、-14Ω

7．如图7所示，求电流源电流IS＝( A )

A、4A B、-4A

C、2A D、-2A

7Ω

7Ω 9Ω 21Ω 19A i

图3

2Ω 3Ω 6Ω G

图5 +

– 2Ω

10V U 3Ω

图4 + –

6Ω 4Ω

12Ω 6Ω

1A IS

图7 7Ω

14i i -

+

图6 8．如图8所示，求单口的等效电阻Rab＝（ C ）

A、17Ω B、13Ω

图论学习笔记

⽬录图的概念简史欧拉与⼽尼斯堡七桥问题

等价问题：“欧拉⼀笔画”\(\equiv\)与任⼀个顶点相关联的边必须是偶数条。图的基本概念图⽆向图邻接与关联

邻接与关联：

\((p,q)\)图

另⼀种表⽰⽅法：(p,q)图图相等与特殊的图

图相等、特殊的图（平凡图、零图）有向图

疑惑：⽆向图是集合反⾃反、对称的关系。有向图中为保证反⾃反性，去掉了⾃⾝到⾃⾝的有向线段\(\{(v,v)|v \in V\}\)。但是，图是不允许存在⾃⾝到⾃⾝的边吗？

答案：是的。图的表⽰图解法与邻接矩阵法

图解法与邻接矩阵法：

问题：关系的闭包在图中的意义是什么？图模型

利⽤图建模现实问题，并⽤图的理论加以解决的能⼒。

例⼦：结婚问题、地图与导航⼦图⼦图概念⽣成⼦图

特例：⽣成⼦图

记号：去除顶点u，去除边{u,v}

尤其地，注意去除边的记号不是去除u、v两个顶点。导出⼦图

（1）顶点导出⼦图：若V1⊆V(G)，则以V1为顶点集，以两个顶点均在V1中的边集组成的图，称为图G的顶点导出⼦图，记为G(V1)。

例如：求G(V1)，V1 ={1,3,5}

则G(V1)为

（2）边的导出⼦图：若E1⊆E(G),则以E1为边集，以E1中所有边的顶点为顶点集组成的图，称为图G的边的导出⼦图，记为G(E1)。

例如：求G(E1)，E1 = {13,24,35}则G(E1)为度度的概念

定理1——握⼿定理

【定理1】握⼿定理

证明：每⼀条边对度数总和的贡献为2（每⼀条边对应两个顶点），由于共有q个边，故度数总和为2q。

推论1：握过奇数次数⼿的⼈为偶数个。

证明：将⼈分为两类，握奇数次⼿\(V_1\)和握偶数次⼿\(V_2\)，

那么，\(V_1\)与\(V_2\)中顶点的度数总和为偶数（2q），

同时，\(V_2\)的度数之和必然为偶数，

那么，\(V_1\)的度数之和必然为偶数（偶数-偶数=偶数），

同时，由于\(V_1\)中均是握奇数次⼿（\(V_1\)中各顶点度均为奇数），