《(完整word版)离散数学图论部分经典试题及答案.pdf》由会员分享，可在线阅读，更多相关《(完整word版)离散数学图论部分经典试题及答案.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 离散数学图论部分综合练习一、单项选择题1设图 G 的邻接矩阵为0101010010000011100100110则 G 的边数为()A6 B5 C4 D3 2已知图 G 的邻接矩阵为，则 G 有（）A5 点，8 边B6 点，7 边C6 点，8 边D5 点，7 边3设图 G，则下列结论成立的是()Adeg(V)=2 EBdeg(V)=ECEvVv2)deg(DEvVv)deg(4图 G 如图一所示，以下说法正确的是()A(a,d)是割边B(a,d)是边割集C(d,e)是边割集D(a,d),(a,c)是边割集5如图二所示，以下说法正确的是()Ae 是割点Ba,e 是点割集C b,e是点割集Dd
2、是点割集6如图三所示，以下说法正确的是()A(a,e)是割边B(a,e)是边割集C(a,e),(b,c)是边割集D(d,e)是边割集cabedf图一图二2 图三7设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是()图四A（a）是强连通的B（b）是强连通的C（c）是强连通的D（d）是强连通的应该填写：D 8设完全图 Kn有 n 个结点(n2)，m 条边，当（）时，Kn中存在欧拉回路Am 为奇数Bn 为偶数Cn 为奇数Dm 为偶数9设 G 是连通平面图，有v个结点，e 条边，r 个面，则 r=()Aev2 Bve2 Cev2 Dev2 10无向图 G 存在欧拉通路，当且仅当()
3、AG 中所有结点的度数全为偶数BG 中至多有两个奇数度结点CG 连通且所有结点的度数全为偶数DG 连通且至多有两个奇数度结点11设 G 是有 n 个结点，m 条边的连通图，必须删去G 的()条边，才能确定 G 的一棵生成树A1mnBmnC1mnD1nm12无向简单图 G 是棵树，当且仅当()AG 连通且边数比结点数少1 BG 连通且结点数比边数少1 CG 的边数比结点数少1 DG 中没有回路二、填空题1已知图 G 中有 1 个 1 度结点，2 个 2 度结点，3 个 3 度结点，4 个 4 度结点，则 G 的边数是2设给定图 G(如图四所示)，则图 G 的点割cabedf图四文档编码:CK4N
4、9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1
5、J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9
6、Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK
7、4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4
8、K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10
9、U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:
10、CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P73 集是3若图 G=中具有一条汉密尔顿回路，则对于结点集 V 的每个非空子集 S，在 G 中删除 S 中的所有结点得到的连通分支数为W，则 S中结点数|S|与 W 满足的关系式为4无向图 G 存在欧拉回路，当且仅当G 连通且5设有向图 D 为欧拉图，则图 D 中每个结点的入度应该填
11、写：等于出度6设完全图 Kn有 n 个结点(n 2)，m条边，当时，Kn中存在欧拉回路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，0
12、01，01，10，0，若去掉其中的元素，则该序列集合构成前缀码三、判断说明题1如图六所示的图G 存在一条欧拉回路2给定两个图 G1，G2（如图七所示）：（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由（2）若是欧拉图，请写出一条欧拉回路v1v2v3v5v4dbacefghn图六文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q
13、6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4
14、N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K
15、1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U
16、9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:C
17、K4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS
18、4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP1
19、0U9Q6B7P74 图七3判别图 G(如图八所示)是不是平面图，并说明理由4设G是一个有 6个结点 14条边的连通图，则 G 为平面图四、计算题1设图 GV，E，其中 Va1,a2,a3,a4,a5,Ea1,a2，a2,a4，a3,a1，a4,a5，a5,a2（1）试给出 G 的图形表示；（2）求 G 的邻接矩阵；（3）判断图 G 是强连通图、单侧连通图还是弱连通图？2设图 G=，V=v1，v2，v3，v4，v5，E=(v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)，试（1）画出 G 的图形表示；（2）写出其邻接矩阵；（2）求出每
20、个结点的度数；（4）画出图 G 的补图的图形3设 G=，V=v1，v2，v3，v4，v5，E=(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)，试（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.用 Dijkst
21、ra 算法求右图中 A 点到其它各点的最短路径。6设有一组权为 2,3,5,7,11,13,17,19,23,29,31,试（1）画出相应的最优二元树；（2）计算它们的权值7给出右边所示二元有序树的三种遍历结果v1 v2 v3 v4 v5 v6 v5 v1 v2 v4 v6 v3 图八a b d c e g f i h 文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2
22、 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3
23、ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文
24、档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3
25、Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L
26、3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P
27、7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7
28、Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P75 五、证明题1若无向图 G 中只有两个奇数度结点，则这两个结点一定是连通的2设 G 是一个 n 阶无向简单图，n 是大于等于 2 的奇数证明图 G 与它的补图G中的奇数度顶点个数相等3设连通图 G 有 k 个奇数度的结点，证明在图 G 中至少要添加2k条边才能使其成为欧拉图参考解答一、单项选择题1B 2D 3C 4C 5A 6D 7D 8C 9A 10D 11A 12A 二、填空题115 2 f，c，e 3W|S|4所有结点的度数全为偶数5等于出度6n 为奇数7v-e+r=2 83 9e=v-1 104 115123 130 三、判断
29、说明题1解：正确因为图 G 为连通的，且其中每个顶点的度数为偶数2解：（1）图 G1是欧拉图因为图 G1中每个结点的度数都是偶数图G2是汉密尔顿图因为图 G2存在一条汉密尔顿回路（不惟一）：a(a,b)b(b,e)e(e,f)f(f,g)g(g,d)d(d,c)c(c,a)a 问题：请大家想一想，为什么图G1不是汉密尔顿图，图G2不是欧拉图。（2）图 G1的欧拉回路为：（不惟一）：v1(v1,v2)v2(v2,v3)v3(v3,v4)v4(v4,v5)v5(v5,v2)v2(v2,v6)v6(v6,v4)v4(v4,v1)v13解：图G是平面图因为只要把结点 v2与 v6的连线(v2,v6)拽
30、到结点 v1的外面，把把结点v3与 v6的连线v5 v1 v2 v4 v6 v3 图九文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E
31、7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7
32、E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6
33、B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N
34、9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1
35、J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9
36、Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P76(v3,v6)拽到结点 v4,v5的外面，就得到一个平面图，如图九所示4解：错误不满足“设 G 是一个有 v 个结点 e条边的连通简单平面图，若v3，则 e3v-6”四、计算题
37、1解：（1）图 G 是有向图：（2）邻接矩阵如下：,0001010000000010100000010)(DA（3）图 G 是单侧连通图，也是弱连通图2解：（1）图 G 如图十（2）邻接矩阵为图十0110010110110110110100110（3）deg(v1)=2 deg(v2)=3 deg(v3)=4 deg(v4)=3 deg(v5)=2（4）补图如图十一图十一3解：（1）G 的图形如图十二a1 a2 a3 a4 a5 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7
38、Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E
39、6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B
40、7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9
41、E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J
42、7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q
43、6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4
44、N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P77（2）邻接矩阵：图十二0110010110110110110000100（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2（4）补图如图十三：图十三4解：（1）G 的图形表示如图十四：图十四（2）邻接矩阵：0111110110110011100110110（3）粗线表示最小的生成树，如图十五文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3
45、ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文
46、档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3
47、Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L
48、3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P
49、7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7
50、Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E