图论 王树禾 答案

《离散数学》第四部分---图论练习题答案一、选择或填空1、设G是一个哈密尔顿图，则G一定是( )。

(1) 欧拉图(2) 树(3) 平面图(4) 连通图答：(4)2、下面给出的集合中，哪一个是前缀码？( )(1) {0，10，110，101111} (2) {01，001，000，1}(3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011}答：（2）3、一个图的哈密尔顿路是一条通过图中( )的路。

答：所有结点一次且恰好一次4、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( )。

答：以v为起点的边的条数，以v为终点的边的条数5、设G是一棵树，则G 的生成树有( )棵。

(1) 0 (2) 1 (3) 2 (4) 不能确定答：16、n阶无向完全图K n 的边数是( )，每个结点的度数是( )。

答：2)1(nn, n-17、一棵无向树的顶点数n与边数m关系是( )。

8、一个图的欧拉回路是一条通过图中( )的回路。

答：所有边一次且恰好一次9、有n个结点的树，其结点度数之和是( )。

答：2n-210、下面给出的集合中，哪一个不是前缀码( )。

(1) {a，ab，110，a1b11} (2) {01，001，000，1}(3) {1，2，00，01，0210} (4) {12，11，101，002，0011}答：(1)11、n个结点的有向完全图边数是( )，每个结点的度数是( )。

答：n(n-1),2n-212、一个无向图有生成树的充分必要条件是( )。

答：它是连通图13、设G是一棵树，n,m分别表示顶点数和边数，则(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。

答：（3）14、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。

答：215、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。

图论及其应用习题答案图论及其应用习题答案图论是数学的一个分支，研究的是图的性质和图之间的关系。

图是由节点和边组成的，节点表示对象，边表示对象之间的关系。

图论在计算机科学、电子工程、物理学等领域有着广泛的应用。

下面是一些图论习题的解答，希望对读者有所帮助。

1. 问题：给定一个无向图G，求图中的最大连通子图的节点数。

解答：最大连通子图的节点数等于图中的连通分量个数。

连通分量是指在图中，任意两个节点之间存在路径相连。

我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，统计连通分量的个数。

2. 问题：给定一个有向图G，判断是否存在从节点A到节点B的路径。

解答：我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，查找从节点A到节点B的路径。

如果能够找到一条路径，则存在从节点A到节点B的路径；否则，不存在。

3. 问题：给定一个有向图G，判断是否存在环。

解答：我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，同时记录遍历过程中的访问状态。

如果在搜索过程中遇到已经访问过的节点，则存在环；否则，不存在。

4. 问题：给定一个加权无向图G，求图中的最小生成树。

解答：最小生成树是指在无向图中，选择一部分边，使得这些边连接了图中的所有节点，并且总权重最小。

我们可以使用Prim算法或Kruskal算法来求解最小生成树。

5. 问题：给定一个有向图G，求图中的拓扑排序。

解答：拓扑排序是指将有向图中的节点线性排序，使得对于任意一条有向边(u, v)，节点u在排序中出现在节点v之前。

我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，同时记录节点的访问顺序，得到拓扑排序。

6. 问题：给定一个加权有向图G和两个节点A、B，求从节点A到节点B的最短路径。

解答：我们可以使用Dijkstra算法或Bellman-Ford算法来求解从节点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 点到其它各点的最短路径。

图论中最优树问题的Lingo求解树连通且不含圈的无向图称为树．常用T表示。

树中的边称为树枝，树中度为1的顶点称为树叶图1 树的示例在许多实际问题中，如在许多城市间建立公路网、输电网或通信网络，都可以归结为赋权图的最优树问题。

如在一个城市中，对若干个居民点要供应自来水，已经预算出连接各点间管道的造价，要求给出一个总造价最小的铺设方案。

图论中最优树的的求解通常有两种算法：Kruskal算法（或避圈法）和Prim算法（破圈法）. 这里我们给出利用LINGO求解最优树的方法。

总线性规划模型为：问题1 某有10个城镇见下图，它们之间的距离见表1。

城镇1处有一条河流，现需要从各城镇之间铺设管道，使城镇1处的水可以输送到各城镇，求铺设管道最少的设计方式。

表1 10个地区之间的距离（单位：公里）地区12345678910 10859121412161722 28091516811181422 359079117121217 4915703171071515 5121693081061515 6148111780914816 7121171010908611 81618127614801111 917141225158611010 102222171515161111100该问题实际上是求从点1出发的最优树问题。

Lingo实现程序为：! 最优树的Lingo程序; model:sets:point/1..10/:u;link(point,point):d,x; endsetsdata:d=0,8,5,9,12,14,12,16,17,22, 8,0,9,15,16,8,11,18,14,22, 5,9,0,7,9,11,7,12,12,17, 9,15,7,0,3,17,10,7,15,15,12,16,9,3,0,8,10,6,15,15,14,8,11,17,8,0,9,14,8,16,12,11,7,10,10,9,0,8,6,11,16,18,12,7,6,14,8,0,11,11,17,14,12,25,15,8,6,11,0,10,22,22,17,15,15,16,11,11,10,0; @text()=@writefor(link(i,j)|x(i,j) #GT#0:'x(',i,',',j,')=',x(i,j),' ');enddatamin=@sum(link(i,j)|i#ne#j:d(i,j)*x(i,j));n=@size(point);@sum(point(j)|j#gt#1:x(1,j))>=1;@for(point(i)|i#ne#1:@sum(point(j)|j#ne#i:x(j,i))=1); @for(link(i,j):@bin(x(i,j)));@for(link(i,j)|i#ne#j:u(i)-u(j)+n*x(i,j)<=n-1); !不构成圈;end结果为minZ=60x(1,2)=1 x(1,3)=1 x(3,4)=1 x(4,5)=1x(9,6)=1 x(3,7)=1 x(7,9)=1 x(5,8)=1x(9,10)=1故最优树(最佳铺设管道方式)见图.谢谢！。

离散数学习题解答 习题六 （第六章 图论）1．从日常生活中列举出三个例子，并由这些例子自然地导出两个无向图及一个向图。

[解] ①用V 代表全国城市的集合，E 代表各城市间的铁路线的集合，则所成之图G=（V ，E ）是全国铁路交通图。

是一个无向图。

②V 用代表中国象棋盘中的格子点集，E 代表任两个相邻小方格的对角线的集合，则所成之图G=（V ，E ）是中国象棋中“马”所能走的路线图。

是一个无向图。

③用V 代表FORTRAN 程序的块集合，E 代表任两个程序块之间的调用关系，则所成之图G+（V ，E ）是FORTRAN 程序的调用关系图。

是一个有向图。

2．画出下左图的补图。

[解] 左图的补图如右图所示。

3．证明下面两图同构。

a v 2 v 3 v 4图G图G ′[证] 存在双射函数ϕ:V →V ′及双射函数ψ : E →E ′ϕ (v 1)=v 1′ ϕ (v 1，v 2)=(v 1′，v 2′) ϕ (v 2)=v 2′ ϕ (v 2，v 3)=(v 2′，v 3′) ϕ (v 3)=v 3′ ϕ (v 3，v 4)=(v 3′，v 4′) ϕ (v 4)=v 4′ ϕ (v 4，v 5)=(v 4′，v 5) ϕ (v 5)=v 5′ ϕ (v 5，v 6)=(v 5′，v 6′) ϕ (v 6)=v 6′ϕ (v 6，v 1)=(v 6′，v 1′) ϕ (v 1，v 4)=(v 1′，v 4′) ϕ (v 2，v 5)=(v 2′，v 5′) ϕ (v 3，v 6)=(v 3′，v 6′)显然使下式成立：ψ (v i ，v j )=(v i ,v j ′)⇒ ϕ (v i )=v i ′∧ϕ (v j )=v j ′ (1≤i ·j ≤6) 于是图G 与图G ′同构。

4．证明（a ），（b ）中的两个图都是不同构的。

图G 中有一个长度为4的圈v 1v 2v 6v 5v 1，其各顶点的度均为3点，而在图G ′中却没有这样的圈，因为它中的四个度为3的顶点v 1'，v 5'，v 7'，v 3'不成长度的4的圈。

离散数学第二版最全课后习题答案详解离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、电气工程等领域都有着广泛的应用。

对于学习离散数学的同学们来说，课后习题的解答是巩固知识、加深理解的重要环节。

本文将为您提供离散数学第二版的最全课后习题答案详解，希望能对您的学习有所帮助。

在开始讲解具体的习题答案之前，让我们先简要回顾一下离散数学的主要内容。

离散数学包括集合论、数理逻辑、图论、代数结构等几个部分。

集合论是离散数学的基础，它研究集合的性质、运算和关系。

在集合论的习题中，常见的问题包括集合的表示、集合的运算（并集、交集、补集等）、集合的包含关系以及集合的基数等。

例如，有这样一道习题：设集合 A ＝｛1, 2, 3}，B ＝｛2, 3, 4}，求 A ∪ B 和A ∩ B。

答案是：A ∪ B ＝｛1, 2, 3, 4}，A ∩ B ＝｛2, 3}。

这是因为并集是包含两个集合中所有元素的集合，而交集是同时属于两个集合的元素组成的集合。

数理逻辑是研究推理和证明的工具，它包括命题逻辑和谓词逻辑。

在数理逻辑的习题中，需要掌握命题的符号化、逻辑公式的等价变换、推理规则的应用等。

比如，给出这样一个命题：“如果今天下雨，那么我就不去公园”，将其符号化。

我们可以设“今天下雨”为 P，“我去公园”为 Q，那么这个命题可以符号化为P → ¬Q。

图论是研究图的性质和应用的分支。

图的概念在计算机网络、交通运输等领域有着重要的应用。

图论的习题常常涉及图的表示、顶点的度、路径、连通性、图的着色等问题。

假设有这样一道题：一个无向图有 10 个顶点，每个顶点的度都为 6，求这个图的边数。

根据顶点度数之和等于边数的两倍这个定理，我们可以计算出边数为 30。

代数结构则包括群、环、域等概念，在这部分的习题中，需要理解和运用代数结构的定义和性质来解决问题。

接下来，我们具体来看一些习题的详细解答。

例 1：设集合 A ＝｛x ｜ x 是小于 10 的正奇数}，B ＝｛x ｜ x 是小于 10 的正偶数}，求 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 ＝<V , E >，则下列结论成立的是 ( )．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 )}是边割集ο ο ο ο οcab edο f图一图二C．{(a, e) ,(b, c)}是边割集D．{(d, e)}是边割集图三7．设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是( )．图四A．（a）是强连通的B．（b）是强连通的C．（c）是强连通的D．（d）是强连通的应该填写：D8．设完全图Kn 有n个结点(n≥2)，m条边，当（）时，Kn中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m 为偶数9．设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v ＋210．无向图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连通且边数比结点数少1 B．G连通且结点数比边数少1C ．G 的边数比结点数少1D ．G 中没有回路．二、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 集是 ．3．若图G=<V , E>中具有一条汉密尔顿回路， 则对于结点集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 ＝<V , E >是有6个结点，8条边的连通图，则从G 中删去 条边，可以确定图G 的一棵生成树．13．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 ，则该序列集合构成前缀码．三、判断说明题1．如图六所示的图G 存在一条欧拉回路．ο οο ο οca b e dο f 图四2．给定两个图G 1，G 2（如图七所示）：（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由． （2）若是欧拉图，请写出一条欧拉回路．图七3．判别图G (如图八所示)是不是平面图， 并说明理由．4．设G 是一个有6个结点14条边的连 通图，则G 为平面图．四、计算题1．设图G =<V ，E >，其中V ={a 1, a 2, a 3, a 4, a 5},E ={<a 1, a 2>，<a 2, a 4>，<a 3, a 1>，<a 4, a 5>，<a 5, a 2>}（1）试给出G 的图形表示； （2）求G 的邻接矩阵；（3）判断图G 是强连通图、单侧连通图还是弱连通图？ 2．设图G =<V ，E >，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 ，E >，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) }，试v 1v 2v 3v 4v 5v 6v 1v 2v 3v 5 d bae f ghn图六οοο ο οv 5v 1 v 2 v 4v 6 ο v 3图八（1）给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形．4．图G=<V, E>，其中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点到其它各点的最短路径。

图论及应用习题答案图论及应用习题答案图论是数学中的一个分支，研究的是图的性质和图之间的关系。

图论在现实生活中有着广泛的应用，涵盖了许多领域，如计算机科学、通信网络、社交网络等。

本文将为读者提供一些关于图论及应用的习题答案，帮助读者更好地理解和应用图论知识。

1. 图的基本概念题目：下面哪个不是图的基本概念？A. 顶点B. 边C. 路径D. 线段答案：D. 线段。

图的基本概念包括顶点、边和路径。

线段是指两个点之间的连线，而在图论中，我们使用边来表示两个顶点之间的关系。

2. 图的表示方法题目：以下哪个不是图的表示方法？A. 邻接矩阵B. 邻接表C. 边列表D. 二叉树答案：D. 二叉树。

图的表示方法包括邻接矩阵、邻接表和边列表。

二叉树是一种特殊的树结构，与图的表示方法无关。

3. 图的遍历算法题目：以下哪个不是图的遍历算法？A. 深度优先搜索B. 广度优先搜索C. 迪杰斯特拉算法D. 克鲁斯卡尔算法答案：D. 克鲁斯卡尔算法。

图的遍历算法包括深度优先搜索和广度优先搜索，用于遍历图中的所有顶点。

迪杰斯特拉算法是用于求解最短路径的算法，与图的遍历算法有所不同。

4. 最小生成树题目：以下哪个算法不是用于求解最小生成树？A. 克鲁斯卡尔算法B. 普里姆算法C. 弗洛伊德算法D. 公交车换乘算法答案：D. 公交车换乘算法。

最小生成树是指包含图中所有顶点的一棵树，使得树的边的权重之和最小。

克鲁斯卡尔算法和普里姆算法是常用的求解最小生成树的算法，而弗洛伊德算法是用于求解最短路径的算法，与最小生成树问题有所不同。

5. 图的应用题目：以下哪个不是图的应用？A. 社交网络分析B. 路径规划C. 图像处理D. 数字逻辑电路设计答案：D. 数字逻辑电路设计。

图的应用广泛存在于社交网络分析、路径规划和图像处理等领域。

数字逻辑电路设计虽然也涉及到图的概念，但与图的应用有所不同。

总结：图论是一门重要的数学分支，具有广泛的应用价值。

通过本文提供的习题答案，读者可以更好地理解和应用图论知识。

二、应用题题0 : (1996年全国数学联赛)有n (n_6)个人聚会，已知每个人至少认识其中的［n/2］个人，而对任意的［n/2］个人，或者其中有两个人相互认识，或者余下的n-［n/2］个人中有两个人相互认识。

证明这n个人中必有3个人互相认识。

注：［n/2］表示不超过n/2的最大整数。

证明将n个人用n个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G。

由条件可知，G是具有n个顶点的简单图，并且有(1)对每个顶点x, N G(X)工［n/2］;(2)对V的任一个子集S,只要S = ［n/2］, S中有两个顶点相邻或V-S中有两个顶点相邻。

需要证明G中有三个顶点两两相邻。

反证，若G中不存在三个两两相邻的顶点。

在G中取两个相邻的顶点X i和y i,记N G(X I)={y i,y2, ,y t}和N G(y i)={x i,X2, ,X k},贝U N G(X I)和N G(y i)不相交，并且N G(X I) (N G(y i)) 中没有相邻的顶点对。

情况一；n=2r:此时［n/2］=「，由(i)和上述假设，t=k=r 且N G(y i) = V-N G(X I)，但N G(X I)中没有相邻的顶点对，由(2), N G(y i)中有相邻的顶点对，矛盾。

情况二；n=2r+i:此时［n/2］= r,由于N G(X I)和N G(y i)不相交，t亠r,k ",所以r+i 亠t,r+i 丄k。

若t=r+i,则k=r，即N G(y i)=r, N G(X I)= V-N G(y i)，由(2), N G(X I)或N G(y i)中有相邻的顶点对，矛盾。

故k z r+i，同理r+i。

所以t=r,k=r。

记w^V- N G(X I) U N G(y i),由(2), w 分别与N G(X I)和N G(y i)中一个顶点相邻，设wx io，E, wy jo，E。

若X io y jo・E,则w , X io, y jo两两相邻，矛盾。

图论第一次作业By byh|E(G)|,2|E(G)|2G υυ⎛⎫≤ ⎪⎝⎭⎛⎫ ⎪⎝⎭1.1 举出两个可以化成图论模型的实际问题略1.2 证明其中是单图证明：（思路）根据单图无环无重边的特点，所以 最大的情形为任意两个顶点间有一条边相连，即极端情况为。

•1.4 画出不同构的一切四顶单图•0条边：1条边：•2条边：3条边：•4条边：5条边：•6条边：1.10G≅H当且仅当存在可逆映射θ:V G→V H，使得uv∈E G⇔θuθv∈E H，其中G和H是单图。

（证明充分性和必要性）•必要性•若G≅H，由定义可得，存在可逆映射θ:V G→V Hφ:E G→E(H)当且仅当ψG e=uv时，ψHφe=θuθ(v)，所以uv∈E G⇒θuθv∈E H•充分性•定义ϕ:E G→E(H)，使得uv∈E G和θuθv∈E(H)一一对应，于是ϕ可逆，且ψe=uv的充要条件是ψHφe=θuθv，得G≅HG1.12求证(a)ϵK m,n =mn，(b)G是完全二分图，则ϵG≤14v G2•(a)对于K m,n ，将顶集分为X和Y，使得X∪Y=V Km,n，X∩Y=∅，X=m，Y=n，对于X中的每一顶点，都和Y中所有顶点相连，所以ϵKm,n=mn•(b)设G的顶划分为X,Y，X=m,Y=v−m，则ϵG≤•ϵK m,v-m =v−m m≤v24•证明：•(a)第一个序列考虑度数7,第二个序列考虑6,6,1•(b)将顶点v分成两部分v’和v’’•v’ = {v|v= v i, 1≤ i≤ k},•v’’ = {v|v= v i, k< i≤ n}•以v’点为顶的原图的导出子图度数之和小于•然后考虑剩下的点贡献给这k个点的度数之和最大可能为•1.37：证明无环图G 含二分生成子图H ，使得d H v ≥12d G v 对每个v ∈V(G)成立。

•证明：•任取X, Y 满足X U Y = V(G)，X ∩ Y = ø，且令X,Y 中的顶两两不相邻，所得的图是H 且是二分子图，令H 是G 边数最多的二分生成子图，若存在v ϵV(G)，使得d H (v) < d G (v)，不妨设v ϵX ，则将v 所连的边取消，换成d G (v) -d H (v) 条边，且将v 加入Y 中，于是H 的边数增加了d G (v) -2d H (v)条，与H 边数最多矛盾，故原命题成立。

第6-7章一．选择/填空1、设图G 的邻接矩阵为0101010010000011100000100，则G 的边数为( D )． A ．5 B ．6 C ．3 D ．42、设有向图（a ）、（b ）、（c ）与（d ）如下图所示，则下列结论成立的是( A )．A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的3、给定无向图G 如下图所示，下面给出的结点集子集中，不是点割集的为（ B ）．A ．{b , d }B ．{d }C ．{a , c }D ．{b , e }4、图G 如下图所示，以下说法正确的是 ( D ) ．A ．{(a , c )}是割边B ．{(a , c )}是边割集C ．{(b , c )}是边割集D ．{(a, c ) ,(b, c )}是边割集5、无向图G 存在欧拉通路，当且仅当(D )．A ．G 中所有结点的度数全为偶数B ．G 中至多有两个奇数度结点C ．G 连通且所有结点的度数全为偶数D ．G 连通且至多有两个奇数度结点6、设G 是有n 个结点，m 条边的连通图，必须删去G 的( A )条边，才能确定G 的一棵生成树．A ．1m n −+B ．m n −C ．1m n ++D ．1n m −+7、已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为（B ）．A ．8B ．5C ．4D ．38、已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 9、连通无向图G 有6个顶点9条边，从G 中删去 4 条边才有可能得到G 的一棵生成树T ．10、如右图 相对于完全图K 5的补图为（A ）。

11、给定无向图，如下图所示，下面哪个边集不是其边割集（ B ）。

A 、；B 、{<v1,v4>,<v4,v6>};C 、；D 、。

12、设D 是有n 个结点的有向完全图,则图D 的边数为( A ) (A))1(−n n (B))1(+n n (C)2/)1(+n n (D)2/)1(−n n 13、无向图G 是欧拉图,当且仅当( C )(A) G 的所有结点的度数都是偶数 (B)G 的所有结点的度数都是奇数(C)G 连通且所有结点的度数都是偶数 (D) G 连通且G 的所有结点度数都是奇数。