连通图名词解释

图连通性算法及应用图是计算机科学领域中常见的数据结构，用于表示对象之间的关系。

在图论中，图的连通性是一个重要的概念，指的是在图中任意两个顶点之间是否存在路径。

图连通性算法是为了判断图中的连通性而设计的算法，并且在实际应用中有着广泛的应用。

一、连通性的定义与分类在图论中，连通性有两种常见的定义方式：强连通性和弱连通性。

强连通性是指在有向图中，任意两个顶点之间存在互相可达的路径；弱连通性是指在有向图中，将其所有有向边的方向忽略后，剩下的无向图是连通的。

本文将重点介绍无向图的连通性算法及其应用。

二、连通性算法的原理1. 深度优先搜索（DFS）深度优先搜索是最常用的连通性算法之一。

它从图中的一个顶点开始，沿着一条未访问过的边深入图中的下一个顶点，直到无法深入为止，然后回溯至上一个顶点，继续深入其他未访问过的顶点。

通过深度优先搜索算法，我们可以得到一个图的连通分量，从而判断图是否连通。

2. 广度优先搜索（BFS）广度优先搜索同样是常用的连通性算法之一。

它从图中的一个顶点开始，沿着一条未访问过的边遍历与该顶点直接相邻的所有顶点，然后再以这些相邻顶点为起点，继续遍历它们的相邻顶点，直到遍历完所有连通的顶点。

通过广度优先搜索算法，我们可以得到一个图的层次遍历树，从而判断图是否连通。

三、连通性算法的应用1. 社交网络分析在社交网络分析中，连通性算法可以用来判断一个社交网络中是否存在分割成多个互不相连的社群。

通过判断社交网络的连通性，我们可以发现隐藏在社交网络背后的关系网络，从而更好地理解和分析社会关系。

2. 网络路由优化在计算机网络中，连通性算法可以用来判断网络节点之间的连通性。

通过分析网络的拓扑结构，我们可以选择合适的路由算法，从而实现快速且可靠的数据传输。

3. 图像分割在计算机视觉和图像处理中，连通性算法可以用来判断图像中的连通区域。

通过判断图像的连通性，我们可以对图像进行分割和提取，从而实现目标检测和图像识别等应用。

《管理科学》名词解释复习第1章 绪论1．管理科学：从广义上来讲，管理科学是指以科学方法应用为基础的各种管理决策理论和方法的统称。

具体地说，管理科学是一门应用多学科与多领域理论、方法、技术和知识的综合性交叉学科，其目的是研究人类利用有限资源实现组织目标的管理活动方面的动态、复杂和创新的社会行为及其规律。

从狭义上讲，管理科学是指，运用科学方法尤其是数学方法，从定量分析的角度，在解决资源不充分的情况下，如何最好地设计和运行一个系统的科学决策方法。

第2章 线性规划2．线性规划的基:对线性规划的约束系数矩阵A 进行分块处理，把每一列当成一个列向量，则由最大的线性无关的列向量所构成的子矩阵，称为线性规划的一个基。

线性规划的基一般具有这么几个特征：（1）它是线性规划模型约束系数矩阵中最大线性无关的列向量所构成的子矩阵；（2）是一个方阵；（3）基决定着基变量和线性规划问题的基本解。

3．基本解:基本解是线性规划中的一个重要概念。

假设B 为线性规划问题的基，对约束系数矩阵A ，决策向量X 进行分块处理，则有：),(N B A =，T N B X X X ),(=，其中N 表示非基矩阵，B X 表示基变量所构成的子向量，N X 表示非基变量所构成的子向量，由,b AX =得到：b NX BX X X N B AX N B T N B =+==),)(,(，由此式解出B X ，并令非基变量的取值等于零，得到T b B X )0,(1-=，则称X 为基B 下的基本解。

4．可行解:由约束条件和变量取值限制围成的公共区域中的每一个点称为线性规划问题的可行解。

5．大M 法：通过引进人工变量，构造一个辅助的线性规划问题，然后由辅助的线性规划问题找出原问题的第一个初始可行基，在此基础上，利用单纯形法求出原问题的最优解。

其辅助问题为：⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=++++=++++=++++----+++=++++++0,,,max 21211222122121111212111212211n m m n n mn m m n n n n n n mn n n n n x x x b x x a x a x a b x x a x a x a b x x a x a x a Mx Mx Mx x c x c x c z6．影子价格:线性规划对偶问题的对偶解，称之为影子价格。

名词解释1，管理：就是管理者运用各种资源达到某即定目标的过程。

2，可行解：满足全部约束条件的决策变量。

3，最优解：使目标函数最大（或最小）的可行解4，大M法：若系数矩阵不含单位矩阵，通过加人工变量M，构成一个系数矩阵含有单位矩阵的新的线性规划，然后用单纯形法求出最优解。

5，影子价格：规划中各资源分别增加一个单位时总利润增加多少6，灵敏度分析：就是分析系数A，b，C的变化对已得到的最优解有何影响。

7，非线性规划问题：目标或约束中含有非线性函数的优化问题称为非线性规划问题。

8，梯度：若f(X)在X0的邻域内有连续的一阶偏导数，则称f(X)在X0点对n个变元的偏导数组成的向量为f(X)在X0的梯度，记为▽f(X0)9，海赛阵：若f(X)在X0的邻域内有连续的二阶偏导数，则称f(X)在X0点对n个变元两两组合的二阶偏导数组成的向量为f(X)在X0的海赛阵，记为Hf(X0),或简记为H（X0）10，凸规划：在非线性规划模型（NLP）中，若目标函数f(X)是凸函数，不等式约束函数gj（X）, 等式约束函数hi（X）为仿射函数，则称（NLP）为一个凸规划。

11，罚函数法：基本思想是将约束与目标组合在一起，化为无约束极值问题求解。

分为外点法和内点法。

12，目标排序法：把目标按重要性排序。

设给出的重要性序列为f1（X），f2（X）.........fp（X），然后按这种排序逐步进行一系列单目标优化，最后求出满意解。

13，两点之间不带箭头的联线称为边，带箭头的联线称为弧。

若一个图有点和边构成称为无向图，由点和弧构成成为有向图。

14，连通图：若任何两个点之间有一条链，称为连通图。

15，赋权图：对于一个无向图G的每一条边，或对于有向图D的每一条弧，相应有一个权数Wij（或Cij），则称这样的图为赋权图。

16，网络：一般是指一个弧上有某种所谓“流转物”流动的有向图。

17，树：一个无圈的连通图。

18，支撑树：设图T是图G的支撑自图，若图T是一个树兔，则称T是G的一个支撑树。

图论_连通_连通分量 强连通图 : 强连通分量就是本⾝ 有向图 ---> ⾮强连通图 : 多个强连通分量图---> 连通图 : 连通分量就是本⾝ ⽆向图 ---> ⾮连通图 : 多个连通分量路径 : 顾名思义.路径长度 : 路径上边的数量.路径 : 顾名思义.路径长度 : 路径上边的数量.连通 : ⽆向图顶点A可以到顶点B,则称A,B连通.强连通 : 有向图中，两个顶点间⾄少存在⼀条互相可达路径，则两个顶点强连通连通图 : 图中任意两点都连通的图.强连通图 : 有向图的任意两点都强连通.连通分量 : ⽆向图的极⼤连通⼦图称为连通分量.连通图只有⼀个连通分量,即⾃⾝强连通分量: 强连通图有向图的极⼤强连通⼦图.强连通图的强连通分量只有⼀个,即强连通图本⾝.基图 : 将有向图的所有边替换成⽆向边形成的图.弱连通图 : 基图是连通图的有向图.(即,连通的有向图)求图的连通分量的⽬的，是为了确定从图中的⼀个顶点是否能到达图中的另⼀个顶点，也就是说，图中任意两个顶点之间是否有路径可达。

求强连通分量有多种算法.我⽤的Tarjan算法. 复杂度O(V+E)这两个博客写得不错:https:///reddest/p/5932153.htmlhttps:///shadowland/p/5872257.htmlint dfn[16]; // 时间戳int dfn_num = 0; // 时间int low[16]; // 节点u所能访问到的最⼩时间戳int inSt[16]; // 节点u是否在栈中.int st[16];int top = 0;// 我们维护的信息.int col[16]; // 给节点染⾊, 同⼀个连通块的节点应该是同⼀个颜⾊的.int col_num = 0; // 颜⾊值.int size[16]; // 每个颜⾊值所拥有的块数./*第⼀步: 访问当前节点的所有⼦节点: ⼦节点有三种第⼀种: 未访问过的, 我们对它进⾏访问, 同时设置它的时间戳dfn[u]和low[u]为++ndfn_num,以及进栈.第⼆种: 访问过的,并且在栈中,我们直接更新我们当前节点的low[] --> 注意应该⽤low[u] 和 dfn[v]⽐较.第三种: 访问过的,并且不在栈中的, 我们直接跳过.因为这个时候,所以它已经染⾊了,属于⼀个连通块了.第⼆步: 如果dfn[u] == low[u] 说明已经找到⼀个连通块了.这时候我们要将栈顶元素弹出,直到当前节点. 记得也要修改inSt, 同时维护我们需要的信息.*/void Tarjan(int u) {int v, i;dfn[u] = low[u] = ++dfn_num; //添加时间戳.st[++top] = u; // 进栈inSt[u] = true; // 标⽰在栈for (i=head[u]; i; i=edge[i].lst) {v = edge[i].to;if (!dfn[v]) {Tarjan(v);low[u] = min(low[u], low[v]);} else if (inSt[v]) {low[u] = min(low[u], dfn[v]);}}if (dfn[u] == low[u]) {col_num++;do {inSt[st[top]] = false;col[st[top]] = col_num;size[col_num]++;} while (st[top--] != u);}}View Code加上2个板⼦题./problem/1332/题⽬很简单: 要你求出最⼤的强连通块,如果有多个则输出字典序最⼩的⼀个.#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 5e4+500;struct Edge {int lst;int to;}edge[maxn<<1];int head[maxn];int qsz = 1;inline void add(int u, int v) {edge[qsz].lst = head[u];edge[qsz].to = v;head[u] = qsz++;}int dfn[maxn]; // 时间戳int dfn_num = 0; // 时间int low[maxn]; // 节点u所能访问到的最⼩时间戳int inSt[maxn]; // 节点u是否在栈中.int st[maxn];int top = 0;// 我们维护的信息.int col[maxn]; // 给节点染⾊, 同⼀个连通块的节点应该是同⼀个颜⾊的.int col_num = 0; // 颜⾊值.int size[maxn]; // 每个颜⾊值所拥有的块数.int id[maxn];void Tarjan(int u) {int v, i;dfn[u] = low[u] = ++dfn_num; //添加时间戳.st[++top] = u; // 进栈inSt[u] = true; // 标⽰在栈for (i=head[u]; i; i=edge[i].lst) {v = edge[i].to;if (!dfn[v]) {Tarjan(v);low[u] = min(low[u], low[v]);} else if (inSt[v]) {low[u] = min(low[u], dfn[v]);}}if (dfn[u] == low[u]) {col_num++;id[col_num] = u;do {inSt[st[top]] = false;col[st[top]] = col_num;size[col_num]++;id[col_num] = min(id[col_num], st[top]);} while (st[top--] != u);}}int main(){memset(id, 0x3f, sizeof(id));int n, i, u, v, m, t;scanf("%d%d", &n, &m);for (i=1; i<=m; ++i) {scanf("%d%d%d", &u, &v, &t);add(u, v);if (t==2) add(v, u);}for (i=1; i<=n; ++i)if (!dfn[i]) Tarjan(i);int mm = 0, tcol = -1;for (i=1; i<=col_num; ++i)if (mm < size[i]) {mm = size[i];tcol = i;} else if (m == size[i]) {if (id[tcol] > id[i])tcol = i;}// printf("%d \n", tcol);printf("%d\n", mm);for (i=1; i<=n; ++i)if (col[i] == tcol) printf("%d ", i);printf("\n");return0;}View Codehttps:///problem/HYSBZ-1051题⽬: 求出所有⽜都欢迎的⽜的个数. 我们可以把所有连通块求出,然后把⼀个连通块看成⼀个点,即缩点. 然后找到出度为零的点(连通块), 如果有且只有⼀个,那么连通块的点数就是答案,否则答案为零.#include <cstdio>#include <algorithm>using namespace std;struct Edge {int lst;int to;}edge[50500];int head[10100];int qsz = 1;inline void add(int u, int v) {edge[qsz].lst = head[u];edge[qsz].to = v;head[u] = qsz++;}int dfn[10100]; // 时间戳int dfn_num = 0; // 时间int low[10100]; // 节点u所能访问到的最⼩时间戳int inSt[10100]; // 节点u是否在栈中.int st[10100];int top = 0;// 我们维护的信息.int col[10100]; // 给节点染⾊, 同⼀个连通块的节点应该是同⼀个颜⾊的.int col_num = 0; // 颜⾊值.int size[10100]; // 每个颜⾊值所拥有的块数./*第⼀步: 访问当前节点的所有⼦节点: ⼦节点有三种第⼀种: 未访问过的, 我们对它进⾏访问, 同时设置它的时间戳dfn[u]和low[u]为++ndfn_num,以及进栈.第⼆种: 访问过的,并且在栈中,我们直接更新我们当前节点的low[] --> 注意应该⽤low[u] 和 dfn[v]⽐较. 第三种: 访问过的,并且不在栈中的, 我们直接跳过.因为这个时候,所以它已经染⾊了,属于⼀个连通块了. 第⼆步: 如果dfn[u] == low[u] 说明已经找到⼀个连通块了.这时候我们要将栈顶元素弹出,直到当前节点. 记得也要修改inSt, 同时维护我们需要的信息.*/void Tarjan(int u) {int v, i;dfn[u] = low[u] = ++dfn_num; //添加时间戳.st[++top] = u; // 进栈inSt[u] = true; // 标⽰在栈for (i=head[u]; i; i=edge[i].lst) {v = edge[i].to;if (!dfn[v]) {Tarjan(v);low[u] = min(low[u], low[v]);} else if (inSt[v]) {low[u] = min(low[u], dfn[v]);}}if (dfn[u] == low[u]) {col_num++;do {inSt[st[top]] = false;col[st[top]] = col_num;size[col_num]++;} while (st[top--] != u);}}bool ou[10010];int main(){// freopen("E:\\input.txt", "r", stdin);int n, i, j, u, v, m;scanf("%d%d", &n, &m);for (i=1; i<=m; ++i) {scanf("%d%d", &u, &v);add(u, v);}for (i=1; i<=n; ++i)if (!dfn[i])Tarjan(i);// 缩点操作int cnt = 0, res = 0;for (i=1; i<=n; ++i) {if (ou[col[i]]) continue;for (j=head[i]; j; j=edge[j].lst) {v = edge[j].to;if (col[i] != col[v]) {ou[col[i]] = true;break;}}}for (i=1; i<=col_num; ++i) {if (!ou[i]) {res = size[i];cnt++;}if (cnt > 1) {res = 0;break;}}printf("%d\n", res);return0;}View Code。

什么是图的基本概念和特征图是一种数学结构，用于表示多个对象之间的关系。

图由节点（vertex）和边（edge）组成，节点表示对象，边表示节点之间的关系。

图的基本概念和特征包括节点的度、路径、连通性、连通分量等。

1. 节点的度：节点的度是指与该节点相连的边的数量。

对于有向图来说，节点的度分为入度和出度，分别表示指向该节点的边的数量和由该节点指出的边的数量。

节点的度可以用来描述节点的重要性和连接的紧密程度。

2. 路径：路径是指由边连接的一系列节点的序列。

路径的长度是指路径中包含的边的数量。

最短路径是指连接两个节点之间具有最少边数的路径。

路径可以用来描述节点之间的关系和节点之间的可达性。

3. 连通性：图的连通性表示图中任意两个节点之间是否存在路径。

如果图中任意两个节点之间都存在路径，那么图被称为连通图；如果存在某些节点之间不存在路径，那么图被称为非连通图。

连通性可以用来描述图的整体连接情况。

4. 连通分量：连通分量是指图中的最大连通子图。

一个连通分量包含一组相互可达的节点，并且在该连通分量内部的任意两个节点之间都存在路径，而与该连通分量外的节点之间不存在路径。

图可以由多个连通分量组成。

图有以下几种常见的特征：1. 有向图和无向图：根据边的有向性，图可以分为有向图和无向图。

在无向图中，边没有方向，表示节点之间的双向关系；而在有向图中，边有方向，表示节点之间的单向关系。

2. 权重：图的边可以带有权重，用来表示节点之间的距离、成本等。

带权重的图被称为带权图，而不带权重的图被称为无权图。

3. 稀疏图和稠密图：如果图中的边数接近节点数的平方，那么图被称为稠密图；如果图中的边数相对较少，那么图被称为稀疏图。

稠密图和稀疏图在算法设计和空间复杂度上有不同的考虑。

4. 循环和非循环图：如果图中存在一个节点可以通过一系列边回到自身，那么图被称为循环图；如果图中不存在这样的节点，那么图被称为非循环图（也称为无环图）。

5. 连通图和非连通图：根据连通性，图可以分为连通图和非连通图。

三、连通性3.1 连通性和Whitmey定理定义V’真包含于V(G)，G[V(G)-V’]不连通，而G是连通图，则称V’是G的顶剖分集。

最小顶剖分集中顶的个数，记成κ(G)，叫做G的连通度；规定κ(Kv)=υ-1；κ(不连通图)= κ(平凡图)=0。

由一个顶组成的顶剖分集叫割顶。

没有割顶的图叫做块，G中的成块的极大子图叫做G的块。

定义E’包含于E(G)，G为连通图，而G-E’(从G中删除E’中的边)不连通，则称E’为G的边剖分集，若G中已无边剖分集E″，使得|E″|<|E’|,则称|E’|为G的边连通度，记成κ’(G)。

|E’|=1时，E’中的边叫做桥。

规定κ’(不连通图)=0，κ’(Kv)= υ-1。

定义κ(G)>=k时，G叫做k连通图；κ’(G)>=k时，G称为k边连通图。

k连通图，当k>1时，也是k-1连通图。

k边连通图，当k>1时，也是k-1边连通图。

上面就是顶连通与边连通的概念，好象不指明的就是指顶连通了。

定理1 κ(G)=<κ’(G)=<δ(可以复习一下第一章的1.2：δ=min{d(v i)})证：设d(v)=δ，则删除与v边关联的δ条边后，G变不连通图，所以这δ条边形成一个边剖分集，故最小边剖分集边数不超过δ，即κ’(G)=<δ。

下证κ=<κ’。

分情形讨论之。

若G中无桥，则有κ’>=2条边，移去它们之后，G变成不连通图。

于是删除这κ’条中的κ’-1条后，G变成有桥的图。

设此桥为e=uv，我们对于上述κ’-1条删去的每条边上，选取一个端点，删除这些(不超过κ’-1个)端点，若G变得不边能，则κ=<κ’-1；若仍连通，则再删去u或v，即可使G变得不连通，于是κ=<κ’。

证毕。

这个定理很好理解，图论中的一些定理常以这种“友好”的面目出现。

下面就是Whitmey定理定理2(Whitney,1932) υ>=3的图是2连通图的充要条件是任二顶共圈(在一个圈上)。

要连通具有n个顶点的有向图,至少需要
图论是数学一门重要的分支学科，是求解计算机，信号和通信系统中的复杂问题的基础理论。

图论中，连通图是一种研究对象，其中有n个顶点和若干边构成，使得所有顶点都是连接的，这样的图也称作完全图。

首先，通常需要n(n-1)/2条边来连接n个顶点，以使得图中任意两个顶点都是相连接的，这叫做完全图。

显然，只有连通了所有顶点的有向图才能称为完全图。

考虑一个包含n个顶点的有向图，需要至少n条边，以保证n个顶点之间的连通性。

在
有向图中，每条边必须指向另一个节点，即任意一个节点的入度和出度必须各为n-1，以
保证图中所有点都能够相互连接，因此需要至少n条边。

另一种方法是采用最小生成树的技术，它能够构造出n个顶点之间的最短路径。

即使这里
用最小生成树算法连接n个顶点也仍然需要至少n-1条边，因为采用最小生成树算法时，
每个顶点的出度只能有一条边，因此也就需要至少n-1条边来实现完全连通。

综上所述，要使得具有n个顶点的有向图完全连通，至少需要n条边，或者使用最小生成树算法，至少需要n-1条边。

因此，可以得出结论，要想实现n个顶点有向图的完全连通，至少需要n条边。

二部图定义：图),(E V G =称为二部图(bipartite graph)，如果V 是两个互不相交的集合21,V V 的开集，且1V 和2V 中的顶点互不相邻. 这样的二部图也常称为),(21V V -二部图.定义：图G 的匹配是由G 中没有公共顶点构成的集合，与匹配M 中的边关联的顶点称为是被M -浸润的(saturated by M)，其余的顶点称为未被M -浸润的(M-unsaturated). 图G 的一个完美匹配(perfect matching)是浸润的所有顶点的匹配. 图G 的边数最多的匹配称为一个最大匹配(maximum matching).例如在上图中，粗边给出了一个匹配1M ，显然两条细边给出了一个最大匹配2M . 定义：设M 是图G 的一个匹配. 如果路径P 的边交替出现在M 和不出现在M 中，则称P 是一条M -交错路径(M-alternating path). 两个顶点都未被M -浸润的交错路径称为M -增广路径(M-augmenting path).在上例中存在1M -增广路径，2M 是最大匹配，而不存在2M -增广路径，这不是偶然的. 因为可以让（留作习题）：图G 的一个匹配M 是最大匹配⇔G 中无M -增广路径. 定义：图G 的一个顶点覆盖(covering)是一些顶点构成的集合)(G V ⊆κ，使得G 的任何一边都有一个顶点含于κ. 一个顶点覆盖κ称为最小顶点覆盖，是指不存在覆盖'κ，使得κκ<'.设κ是G 的一个顶点覆盖，M 是G 的一个匹配，显然M ≥κ. 我们关心对于最大匹配的最小顶点覆盖来说，等式是否成立. 在图1(a)中，等式成立，而图1(b)中最小顶点覆盖大小为3，而最大匹配大小为2. 注意图1(a)为二部图，图1(b)为有5条边的圈，从而不是二部图（可以一个图G 是二部图⇔G 中不含奇数边的图，证明留作习题）.对于二部图，我们有下面一般的结论：定理：设G 是),(Y X -二部图，则G 的最大匹配的大小等于G 的最小顶点覆盖的大小(könig 1931).证明：设M 是G 的最大匹配，而Q 是M 的最小顶点覆盖，要证Q M =. 显然M Q ≥，故只需证明存在G 的M 个顶点的覆盖（则Q M ≥），对于M 中每一条边，如果存在未被M -浸润的X 中顶点出发的交错路径可达这条边，则选择此边在Y 中的顶点；否则选择此边在X 中的顶点，这样就选了M 个顶点，记为U .设E xy ⊂，Y y X x ∈∈,，只需证明x 或U y ∈，或M xy ∈，则由U 的定义得证.下证之：设M xy ∉. 又由M 是最大匹配，故M y x ∈∃11（其中Y y X x ∈∈11,）且1x x =或1y y =. 若1y y =（此时M x ∉），由于xy 是M -交错路径，故U y ∈.下设1x x =，如果U x ∉，则U y ∈1，由U 的定义：某条交错路径可达1y . 则存在交错路径'P 可达y ；或Py （若P x ∈1）；或y x Py 11. 这样就出现了M -增广路径，与M 是最大匹配矛盾，故U x ∈.对于),(Y X -二部图，若存在一个浸润X 的匹配，则显然X ⊆∀κ，至少在Y 中存在κ个顶点与κ中的顶点相邻. 我们用)(κN 表示与κ中顶点相邻的顶点构成的集合，下面的定理说明“κκκ≥⊆∀)(,N X ”这个显然的必要条件也是充分的定理(1935)：),(Y X -二部图中存在浸润X 的匹配⇔κκκ≥⊆∀)(,N X .证明：“⇐”由könig 定理，只需证明对每个顶点覆盖z ，有X z ≥. 令X z X s ⋂-=，则s 的点都不在X 中，因此)(s N 中的点都在z 中（由顶点覆盖定义），故X s X z s N X z z =+⋂≥+⋂≥)(，证毕.图的连通性因为连通与否与图是否含环无关，故本小节假定所有图都不含环，且1)(>G n .定义1：图G 的一个点割(vertex cut)是一个集合)(G V S ⊆，使得S G -的连通分量多于一个G 的连通度(connectivity)，)(G κ是使得S G -不连通或只有一个顶点的顶点集合S 大小的最小值. 如果G 的连通度最少是κ，则称G 是κ-连通的(κ-connected).由定义，显然可知：①连通图都是1-连通的；②G 是不连通的⇔G 的连通度为0；③顶点数大于2的图的连通度为1⇔它是连通的且有一个割点.若图G 的连通度为κ，则κδ≥)(G ，故G 中至少有⎥⎥⎤⎢⎢⎡2n κ条边（见习题１）. 我们关心是否可以给出n 个顶点的κ-连通图且有⎥⎥⎤⎢⎢⎡2n κ条边（即下界是否可以取到）.习题１给出了肯定的回答.定义2：图G 中的边割(edge cut)是一顶点在S 中，一顶点在S G V -)(中的G 中所有边构成的集合，记为],[S S （)(G V S ⊆）. 若使得],[S S G -不连通的],[S S 边数最小值为κ，则称G 是κ-边连通的，κ称为G 的边连通度，记为)('G κ.在下图G 中粗线标出的边割是G 的最小边割，因此2)('=G κ，G 是2-边连通的. 图G 中还标出了一个只含一个顶点的点割，故G 是1-连通的.定理3(Whitney 1932)：设G 是简单图，则)()(')(G G G δκκ≤≤.证明：设)}(:)(min{)(G V x x d v d ∈=，即)()(G v d δ=，则与v 关联的所有边构成一个边割，故)()('G G δκ≤，下证)(')(G G κκ≤.显然1)()(-≤G n G κ，设],[S S 为G 的最小边割，若S 中的顶点与S 中的顶点都邻接，则)(1)(],[G G n S S S S κ≥-≥=，命题得证. 下设存在S y S x ∈∈,.则y x ,不相邻，构造集合T ：T 包含S 中x 的相邻顶点；T 包含{x}-S 中的所有与S 中顶点有相邻顶点的顶点（或}{{)}(:{x S v E V xv S v T -∈⋃∈∈=：存在S u ∈使得)}(E vu ∀∈）. 因为每条y x ,路径都通过T ，因此T 是一个点割，故)(G T κ≥. 在],[S S 中选T 条边：T v ∈∀，若S v ∈，则选边xv ；若}{x S v -∈，则任意选取一条边],[S S vu ∈，这样选取的T 条边都是不同的，因此[])(,)('G T S S G κκ≥≥=下面给出2-连通图的特征.定理4(Whitney 1932)：图)3)((≥G n G 是2-连通的⇔)(,G V v u ∈∀，在G 中存在内部不相交的(internally-disjoint)v u ,-路径（即两条路径没有公共的内顶点）.证明：“⇐”删除一个顶点不能使一对任意顶点不可达，故G 是2-连通的.“⇒”对),(v u d 用数学归纳法证明.1),(=v u d ，uv G -是连通的（因为2)()('=≥G G κκ）.uv G -中的v u ,-路径与边uv 构成了内部不相交的两条v u ,-路径．假设-),(κ≤v u d .令w 是某条最短u ,-路径上的前一顶点，则1. 由归纳假设，G 有内部不相交w u ,路径Q P ,. 若)()(Q V P V v ⋃∈，则在圈Q P ⋃上可以找两条内部不相交路径. 若)()(Q V P V v ⋃∉，由于G 是2-连通的，故w G -连通，所以w G -中含有一条v u ,-路径R . 若R 不含P 或Q 的内部顶点，则完成了证明. 如若不然，不妨设R 与P 的内部顶点相交，设z 是这些交点中在P 上与v 最近的一个顶点，则P 上的z u ,-路径合并R 上的v z .-路径就得到一条与wv Q ⋃内部不相交路径练习中给出2-连通图的其它特征. 定理4可以推广到一般的κ-连通图.证明较繁，我们这里略去，有兴趣的读者可参见D.B. West,Introduction to Graph Theory,2nd 2001.或J.A. Bondy,U.S.R. Murty,Graph Theory with Applications,1976.习题．1.图G 的连通度为κ且n G =，则G 至少有⎥⎥⎤⎢⎢⎡2n κ条边. 2.证明下图中4)(=G κ，从而满足⎥⎥⎤⎢⎢⎡=2)(n G E κ3.设3)(≥G V ，则G 是2-连通的⇔G 是连通的且G 无割点 ⇔)(,G V y x ∈∀，存在经过y x ,的环 ⇔1)(>G δ且G 的每一对边均位于一个公共环上。

数据结构名词解释归纳（2）数据结构名词解释归纳线性表的顺序存储：是用一组地址连续的存储单元依次存储现行表的数据元素。

顺序表就是现行表的顺序存储的实现。

顺序表：将线性表中的元素相继存放在一个连续的存储空间中。

可利用一维数组描述存储结构。

特点：逻辑上相邻的数据元素，其物理存储位置也是相邻的。

单链表：用一组任意的存储单元来依次存储线性表中的各个数据元素，这些存储单元可以是连续的，也可以是不连续的。

每个结点只有一个链域的链表称为单链表。

循环链表：循环链表是单链表的变形。

最后一个结点的link 指针不为 NULL，而是指向了表的前端，使整个链表形成一个循环结构。

双向链表：双向链表是指在前驱和后继方向都能游历（遍历）的线性链表。

静态链表：为数组中每一个元素附加一个链接指针，就形成静态链表结构。

每个结点由两个数据成员构成：data域存储数据，link域存放链接指针。

栈：限制为仅仅能在表的一端插入和删除的线性表。

允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。

特点：后进先出。

递归：若一个对象部分地包含它自己，或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。

队列：队列是只允许在一端删除，在另一端插入的线性表。

允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。

循环队列：队列存放数组被当作首尾相接的表处理。

串(字符串)：是由零个或多个字符构成的有限序列。

Made by zxj子串：串中任意个连续字符组成的子序列称为该串的子串。

主串：包含子串的串相应地称为主串。

数组：是n(n>1)个相同类型的数组元素a1,a2,…an构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。

一维数组：数组是相同类型的数据元素的集合，而一维数组的每个数组元素是一个序对，由下标和值组成。

多-维数组：多-维数组是一维数组的推广。