判断图的强连通性

计算机专业（基础综合）模拟试卷105(总分130,考试时间90分钟)1. 单项选择题单项选择题1-40小题。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

1. 关于线性表的顺序存储结构和链式存储结构的描述正确的是( )。

Ⅰ．线性表的顺序存储结构优于其链式存储结构Ⅱ．链式存储结构比顺序存储结构可更方便地表示各种逻辑结构Ⅲ．如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构Ⅳ．顺序存储结构和链式存储结构都可以进行顺序存储A. 仅Ⅰ、Ⅱ、ⅢB. 仅Ⅱ、ⅣC. 仅Ⅱ、ⅢD. 仅Ⅲ、Ⅳ2. 相对于单向链表，使用双向链表存储线性表，其优点是( )。

Ⅰ．提高查找速度Ⅱ．节约存储空间Ⅲ．数据的插入和删除更快速A. 仅ⅠB. 仅Ⅰ、ⅢC. 仅ⅢD. 仅Ⅱ、Ⅲ3. 对于一个满二叉树，共有n个结点和m个叶子结点，且深度为h，则下列等式中正确的是( )。

Ⅰ．n=h+mⅡ．h+m=2nⅢ．m=2h-1Ⅳ．n=2h-1A. Ⅰ、Ⅱ、ⅢB. Ⅱ、ⅢC. Ⅱ、Ⅲ、ⅣD. Ⅲ、Ⅳ4. 设一棵二叉树是由森林转换而来的，若森林中有n个非终端结点，则二叉树中无右孩子的结点个数为( )。

A. n-1B. nC. n+1D. n+25. 若某完全二叉树的结点个数为100，则第60个结点的度为( )．A. 0B. 1C. 2D. 不确定6. 下列关于二叉树的说法中，错误的是( )。

A. 在二叉树的后序序列中最后一个结点一定是二叉树的根结点B. 在二叉树的中序序列中最后一个结点一定是二叉树的一个叶结点C. 在二叉树的前序序列中最后一个结点一定是二叉树的一个叶结点D. 在二叉树的层序序列中最后一个结点一定是二叉树的一个叶结点7. 已知一棵5阶B树有53个关键字，并且每个结点的关键字都达到最少状态，则它的深度是( )。

A. 3B. 4C. 5D. 68. 设图G=(V，E)，其中：V={V0，V1，V2，V3}E={(V0，V1)，(V0，V2)，(V0，V3)，(V1，V3)}则从顶点V0开始对图G的深度优先遍历序列总共有( )种。

连通图的割点、割边(桥)、块、缩点，有向图的强连通分量一、基本概念无向图割点：删掉它之后(删掉所有跟它相连的边)，图必然会分裂成两个或两个以上的子图。

块：没有割点的连通子图割边：删掉一条边后，图必然会分裂成两个或两个以上的子图，又称桥。

缩点：把没有割边的连通子图缩为一个点，此时满足任意两点间都有两条路径相互可达。

求块跟求缩点非常相似，很容易搞混，但本质上完全不同。

割点可以存在多个块中(假如存在k个块中)，最终该点与其他点形成k个块，对无割边的连通子图进行缩点后(假设为k个)，新图便变为一棵k个点由k-1条割边连接成的树，倘若其中有一条边不是割边，则它必可与其他割边形成一个环，而能继续进行缩点。

有割点的图不一定有割边，如：3是割点，分别与(1,2)和(4,5)形成两个无割点的块有割边的图也不定有割点,如：w(1,2)为割边，有向图强连通分量：有向图中任意两点相互可达的连通子图，其实也相当于无向图中的缩点二、算法无向图借助两个辅助数组dfn[],low[]进行DFS便可找到无向图的割点和割边，用一个栈st[]维护记录块和“缩点”后连通子图中所有的点。

dfn[i]表示DFS过程中到达点i的时间，low[i]表示能通过其他边回到其祖先的最早时间。

low[i]=min(low[i],dfn[son[i]])设 v,u之间有边w(v,u)，从v->u：如果low[u]>=dfn[v],说明v的儿子u不能通过其他边到达v的祖先，此时如果拿掉v,则必定把v的祖先和v的儿子u，及它的子孙分开，于是v便是一个割点，v和它的子孙形成一个块。

如果low[u]>dfn[v]时，则说明u不仅不能到达v的祖先，连v也不能通过另外一条边直接到达，从而它们之间的边w(v,u)便是割边，求割边的时候有一个重边的问题要视情况处理，如果v,u之间有两条无向边，需要仍视为割边的话，则在DFS的时候加一个变量记录它的父亲,下一步遇到父结点时不扩展回去，从而第二条无向重边不会被遍历而导致low[u]==dfn[v] ,而在另外一些问题中，比如电线连接两台设备A,B 如果它们之间有两根电线，则应该视为是双连通的，因为任何一条电线出问题都不会破坏A和B之间的连通性，这个时候，我们可以用一个used[]数组标记边的id,DFS时会把一条无向边拆成两条有向边进行遍历,但我们给它们俩同一个id号，在开始遍历v->u前检查它的id是否在上一次u->v 时被标记，这样如果两点之间有多条边时，每次遍历都只标记其中一条，还可以通过其他边回去，形成第二条新的路求割点的时候，维护一个栈st 每遍历到一个顶点v则把它放进去，对它的子孙u如果dfn[u]为0，则表示还没有遍历到则先DFS(u),之后再判断low[u]和dfn[v]，如果low[u]>=dfn[v],则把栈中从栈顶到v这一系列元素弹出，这些点与v 形成一个块，如果u的子孙x也是一个割点，这样做会不会错把它们和v，u放在一起形成一个块呢，这种情况是不会发生的，如果发现x是一个割点，则DFS 到x那一步后栈早就把属于x的子孙弹出来了，而只剩下v,u的子孙，它们之间不存在割点，否则在回溯到v之前也早就提前出栈了！画一个图照着代码模拟一下可以方便理解。

图的连通性图的连通性2010-07-23 21 ：02 图的连通性第十三章图的基本概念第三节图的连通性一.连通性概念图中两点的连通：如果在图G中u、v 两点有路相通，则称顶点u、v 在图G中连通。

连通图(connected graph) ：图G中任二顶点都连通。

图的连通分支(connected brch,component) ：若图G 的顶点集V(G)可划分为若干非空子集V 1,V 2, ⋯,V w, 使得两顶点属于同一子集当且仅当它们在G 中连通，则称每个子图G为图G的一个连通分支(i=1,2, ⋯,w) 。

注：(1) 图G的连通分支是G的一个极大连通子图。

(2)图G连通当且仅当w=1。

例13.5 设有2n 个电话交换台，每个台与至少n 个台有直通线路，则该交换系统中任二台均可实现通话。

证明：构造图G如下：以交换台作为顶点，两顶点间连边当且仅当对应的两台间有直通线路。

问题化为：已知图G有2n 个顶点，且δ(G) ≥n，求证G连通。

事实上，假如G不连通，则至少有一个连通分支的顶点数不超过n。

在此连通分支中，顶点的度至多是n–1。

这与δ(G)≥n 矛盾。

证毕例13.6 若图中只有两个奇度顶点，则它们必连通。

证明：用反证法。

假如u与v 不连通，则它们必分属于不同的连通分支。

将每个分支看成一个图时，其中只有一个奇度顶点。

这与推论13.1 矛盾。

证毕在连通图中，连通的程度也有高有低。

例如后面将定义一种参数来度量连通图连通程度的高低。

二.割点定义13.2 设v∈V(G)，如果w(G–v)w(G) ，则称v 为G的一个割点。

( 该定义与某些著作有所不同，主要是在有环边的顶点是否算作割点上有区别) 。

例如定理13.3 如果点v 是图G的一个割点，则边集E(G)可划分为两个非空子集E 1和E 2，使得G[E 1]和G[E 2]恰好有一个公共顶点v。

推论13.2 对连通图G，顶点v 是G的割点当且仅当G–v 不连通。

参考答案试卷一一、选择填空1.C2.A3.D4.D5.A6.A7.B8.C9.D 10.B二、填空1.主合取范式)()(q p q p ⌝∨∧∨⌝.前束范式))()((x G x F x →∀或))()((y G x F y x →∀∀ 2. n-k,93.=)(A ρ{Φ,{1}，{2}，{1，2}}，B A ⨯={〈1,a 〉,<1,b>,<2,a>,<2,b>}4. [b]R ={1,2,3}, X/R={{1,2,3},{4},{5}}.5． ,,G y x ∈∀ )()()(y f x f y x f *= 。

6.=-)(1R r { <2,1>,< 4,2>,<1,1>,<3,3>,<2,2>}，=S R {<1,4>,<2,2>}。

7.15，12.8. =τσ⎪⎪⎭⎫ ⎝⎛42134321 =(132) =-1στ⎪⎪⎭⎫ ⎝⎛41324321=(123) 9．0, 45 10．2,0三 1.× 2.√ 3. √ 4.× 5.×四.1．一棵树具有3个2度结点，2个3度结点，2个4度结点，其余为叶。

试求其共有多少个结点？多少片叶？解: 设该树其有x 片叶,则顶点数为x+7, 根据树的性质知,该树有x+6边,由握手定理有:3*2+2*3+2*4+x*1=2(x+6), 得x=8故该树共有15个结点,8 片叶 .2.已知X={a,b,c},给出X 上的所有等价关系。

解:X 的划分其有五种:S 1={{a,b,c}}, S 2={{a,b},{c}}, S 3={{a,c},{b}}, S 4={{a},{b,c}},S 5={{a},{b},{c}},因为X 上划分与等价关系一一对应,故x 上共有五个等价关系，它们是：R 1＝{<a,b>,<b,a>,<a,c><c,a>,<b,c>,<c,b>}X I ⋃R 2＝{<a,b>,<b,a>}X I ⋃, R 3＝{<a,c><c,a>}X I ⋃R 4＝{<b,c>,<c,b>}X I ⋃, R 5＝X I3.．画一棵权为2，3，3，4，5，6，7，8 的最优二叉树，并计算出它的树权。

图的点连通度边连通度总结点连通度的定义：一个具有N个点的图G中，在去掉任意k-1个顶点后（1<=k<=N ）, 所得的子图仍然连通，去掉K个顶点后不连通，则称G是K连通图，K称作图G的连通度，记作K（G）。

独立轨：A, B是图G （有向无向均可）的两个顶点，我们称为从A到B的两两无公共内顶点的轨为独立轨，其最大的条数记作p（A,B）。

在上图中有一个具有7个定点的连通图，从顶点1到顶点3有3条独立轨，即p（1,3）=3;1 —2 —3 , 1 —7—3 , 1 —6 —5—4 —3如果分别从这3条独立轨中，每条轨抽出一个内点，在G图中删掉，则图不连通。

若连通图G的两两不相邻顶点间的最大独立轨数最小的P（A，B）值即为K （G）。

若G为完全图（两两点可达），则K（G）=n-1 ，即完全把某个点的所有边删掉后才不连通。

既然独立轨是只能经过一次的边，那么可以构造网络流模型，其中每条边的容量为1，就可以限制只经过一次。

构建网络流模型：若G为无向图：（1）原G图中的每个顶点V变成N网中的两个顶点V'和V'',顶点V'至V''有一条弧容量为1 ；（2）原图G中的每条边e=UV，在N网中有两条弧e'=U''V',e''=V''U' 与之对应，e'与e''容量均为无穷；（3 ）以A''为源点，B'为汇点，求最大流。

若G为有向图（1 ）原G图中的每个顶点V变成N网中的两个顶点V'和V'',顶点V'至V''有一条容量为1的弧；（2）原G图中的每条弧e=UV变成一条有向轨U'U''V'V'', 其中轨上的弧U''V'的容量为无穷；（3 ）以A''为源点，B'为汇点求最大流。

离散数学图论部分经典试题及答案离散数学图论部分综合练习⼀、单项选择题1．设图G 的邻接矩阵为0101010010000011100100110则G 的边数为( )．A ．6B ．5C ．4D ．32．已知图G 的邻接矩阵为，则G 有（）．A ．5点，8边B ．6点，7边C ．6点，8边D ．5点，7边3．设图G ＝，则下列结论成⽴的是 ( )．A ．deg(V )=2∣E ∣B ．deg(V )=∣E ∣C ．E v Vv 2)deg(=∑∈ D ．E v Vv =∑∈)deg(4．图G 如图⼀所⽰，以下说法正确的是 ( ) ． A ．{(a , d )}是割边 B ．{(a , d )}是边割集 C ．{(d , e )}是边割集 D ．{(a, d ) ,(a, c )}是边割集5．如图⼆所⽰，以下说法正确的是 ( )． A ．e 是割点 B ．{a, e }是点割集 C ．{b , e }是点割集 D ．{d }是点割集6．如图三所⽰，以下说法正确的是 ( ) ．A ．{(a, e )}是割边B ．{(a, e )}是边割集C ．{(a, e ) ,(b, c )}是边割集D ．{(d , e )}是边割集οοοοοca b edο f图⼀图⼆图三7．设有向图（a ）、（b ）、（c ）与（d ）如图四所⽰，则下列结论成⽴的是 ( )．图四A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的应该填写：D8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（）时，K n 中存在欧拉回路．A ．m 为奇数B ．n 为偶数C ．n 为奇数D ．m 为偶数 9．设G 是连通平⾯图，有v 个结点，e 条边，r 个⾯，则r = ( )．A ．e －v ＋2B ．v ＋e －2C ．e －v －2D ．e ＋v ＋2 10．⽆向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中⾄多有两个奇数度结点C ．G 连通且所有结点的度数全为偶数 D ．G 连通且⾄多有两个奇数度结点11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的⼀棵⽣成树．A ．1m n -+B ．m n -C ．1m n ++D ．1n m -+ 12．⽆向简单图G 是棵树，当且仅当( )．A ．G 连通且边数⽐结点数少1B ．G 连通且结点数⽐边数少1C ．G 的边数⽐结点数少1D ．G 中没有回路．⼆、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是． 2．设给定图G (如图四所⽰)，则图G 的点割οοοοc a b f集是．3．若图G=中具有⼀条汉密尔顿回路，则对于结点集V 的每个⾮空⼦集S ，在G 中删除S 中的所有结点得到的连通分⽀数为W ，则S 中结点数|S|与W 满⾜的关系式为．4．⽆向图G 存在欧拉回路，当且仅当G 连通且．5．设有向图D 为欧拉图，则图D 中每个结点的⼊度．应该填写：等于出度6．设完全图K n 有n 个结点(n 2)，m 条边，当时，K n 中存在欧拉回路．7．设G 是连通平⾯图，v , e , r 分别表⽰G 的结点数，边数和⾯数，则v ，e 和r 满⾜的关系式．8．设连通平⾯图G 的结点数为5，边数为6，则⾯数为． 9．结点数v 与边数e 满⾜关系的⽆向连通图就是树．10．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去条边后使之变成树．11．已知⼀棵⽆向树T 中有8个结点，4度，3度，2度的分⽀点各⼀个，T 的树叶数为．12．设G ＝是有6个结点，8条边的连通图，则从G 中删去条边，可以确定图G 的⼀棵⽣成树．13．给定⼀个序列集合{000，001，01，10，0}，若去掉其中的元素，则该序列集合构成前缀码．三、判断说明题1．如图六所⽰的图G 存在⼀条欧拉回路．2．给定两个图G 1，G 2（如图七所⽰）：（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由．（2）若是欧拉图，请写出⼀条欧拉回路．v 123图六图七3．判别图G (如图⼋所⽰)是不是平⾯图，并说明理由．4．设G 是⼀个有6个结点14条边的连通图，则G 为平⾯图．四、计算题1．设图G =，其中V ={a 1, a 2, a 3, a 4, a 5},E ={，，，，}（1）试给出G 的图形表⽰；（2）求G 的邻接矩阵；（3）判断图G 是强连通图、单侧连通图还是弱连通图？2．设图G =，V ={ v 1，v 2，v 3，v 4，v 5}，E ={ (v 1, v 2)，(v 1, v 3)，(v 2, v 3)，(v 2, v 4)，(v 3, v 4)，(v 3, v 5)，(v 4, v 5) }，试（1）画出G 的图形表⽰；（2）写出其邻接矩阵；（2）求出每个结点的度数；（4）画出图G 的补图的图形． 3．设G =，V ={ v 1，v 2，v 3，v 4，v 5}，E ={ (v 1,v 3)，(v 2,v 3)，(v 2,v 4)，(v 3,v 4)，(v 3,v 5)，(v 4,v 5) }，试（1）给出G 的图形表⽰；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形． 4．图G =，其中V ={ a , b , c , d , e }，E ={ (a , b ), (a , c ), (a , e ), (b , d ), (b , e ), (c , e ), (c , d ), (d , e ) }，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G 的图形；（2）写出G 的邻接矩阵；（3）求出G 权最⼩的⽣成树及其权值．5.⽤Dijkstra 算法求右图中A 点到其它各点的最短路径。

7_1对于图题7.1（P235）的无向图，给出：（1）表示该图的邻接矩阵。

（2）表示该图的邻接表。

（3）图中每个顶点的度。

解：（1）邻接矩阵：0111000100110010010101110111010100100110010001110（2）邻接表：1：2----3----4----NULL;2: 1----4----5----NULL;3: 1----4----6----NULL;4: 1----2----3----5----6----7----NULL;5: 2----4----7----NULL;6: 3----4----7----NULL;7: 4----5----6----NULL;（3）图中每个顶点的度分别为：3，3，3，6，3，3，3。

7_2对于图题7.1的无向图，给出：（1）从顶点1出发，按深度优先搜索法遍历图时所得到的顶点序（2）从顶点1出发，按广度优先法搜索法遍历图时所得到的顶点序列。

（1）DFS法：存储结构：本题采用邻接表作为图的存储结构，邻接表中的各个链表的结点形式由类型L_NODE规定，而各个链表的头指针存放在数组head中。

数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边，e中结点形式由类型E_NODE规定。

visit[i]数组用来表示顶点i是否被访问过。

遍历前置visit各元素为0，若顶点i被访问过,则置visit[i]为1.算法分析：首先访问出发顶点v.接着，选择一个与v相邻接且未被访问过的的顶点w访问之，再从w 开始进行深度优先搜索。

每当到达一个其所有相邻接的顶点都被访问过的顶点，就从最后访问的顶点开始，依次退回到尚有邻接顶点未曾访问过的顶点u,并从u开始进行深度优先搜索。

这个过程进行到所有顶点都被访问过，或从任何一个已访问过的顶点出发，再也无法到达未曾访问过的顶点，则搜索过程就结束。

另一方面，先建立一个相应的具有n个顶点,m条边的无向图的邻接表。