离散数学及应用课后习题答案【篇一:离散数学及其应用图论部分课后习题答案】p165:习题九1、给定下面4个图(前两个为无向图,后两个为有向图)的集合表示,画出它们的图形表示。(1)g1??v1,e1?,v1?{v1,v2,v3,v4,v5},e1?{(v1,v2),(v2,v3),(v3,v4),(v3,v3),(v4,v5)}(2)g2??v2,e2?,v2?v1,e1?{(v1,v2),(v2,v3),(v3,v4),(v4,v5),(v5,v1)}(3)d1??v3,e3?,v3?v1,e3?{?v1,v2?,?v2,v3?,?v3,v2?,?v4,v5?,?v5,v1?}(4)d2??v4,e4?,v4?v1,e3?{?v1,v2?,?v2,v5?,?v5,v2?,?v3,v4?,?v4,v3?}解答:(1)(2)10、是否存在具有下列顶点度数的5阶图?若有,则画出一个这样的图。(1)5,5,3,2,2;(2)3,3,3,3,2;(3)1,2,3,4,5;(4)4,4,4,4,4解答:(1)(3)不存在,因为有奇数个奇度顶点。14、设g是n(n?2)阶无向简单图,g是它的补图,已知?(g)?k1,?(g)?k2,求?(g),(g)。解答:?(g)?n?1?k2;?(g)?n?1?k1。15、图9.19中各对图是否同构?若同构,则给出它们顶点之间的双射函数。解答:(c)不是同构,从点度既可以看出,一个点度序列为4,3,3,3,3而另外一个为4,4,3,3,1(d)同构,同构函数为1?2??f(x)??34???5解答:(1)三条边一共提供6度;所以点度序列可能是x?ax?bx?cx?dx?e16、画出所有3条边的5阶简单无向图和3条边的3阶简单无向图。①3,3,0,0,0,0;②3,2,1,0,0,0;③3,1,1,1,0,0;④2,2,2,0,0,0;⑤2,2,1,1,0,0;⑥2,1,1,1,1,0;⑦1,1,1,1,1,1;由于是简单图,①②两种情形不可能图形如下:(2)三条边一共提供6度,所以点度序列可能为①3,3,0;②3,2,1;③2,2,2由于是简单图,①②两种情形不可能21、在图9.20中,下述顶点序列是否构成通路?哪些是简单通路?哪些是初级通路?哪些是回路?哪些是简单回路?哪些是初级回路?(1)a,b,c,d,b,e;(2)a,b,e,d,b,a;(3)a,d,c,e,b;(4)d,b,a,c,e;(5)a,b,c,d,e,b,d,c;(6)a,d,b,e,c,b,d;(7)c,d,a,b,c;(8)a,b,c,e,b解答:(1)构成通路,且为初级通路,因为点不重复(2)构成了回路,但是不为简单回路和初级回路,因为有重复的边(a,b)(3)构成了初级通路,因为点不重复;(4)不构成通路,因为边(a,c)不存在;(5)构成通路,但是不为简单通路和初级通路,因为有重复的边(d,c)(6)构成了回路,但是不为简单回路和初级回路,因为有重复的边(d,b)(7)构成了初级通路;(8)简单通路,但是不为初级通路,有重复边。23、用dijkstra标号法求图9.22中各图从顶点v1到其余各点的最短路径和距离。v1到v2最短路为v1?v2,路长为6;v1到v3最短路为v1?v3,路长为3;v1到v4最短路为v1?v3?v4,路长为5;v1到v5最短路为v1?v3?v4?v5,路长为6;v1到v6最短路为v1?v2?v6,路长为12;v1到v7最短路为v1?v3?v4?v5?v7,路长为7;v1到v8最短路为v1?v3?v4?v5?v7?v8,路长为10;(2)略。25、图9.23中各图有几个连通分支?给出它们所有的连通分支。解答:(a)有两个连通分支:aec和bdf;(b)有三个连通分支:abd、c和ef;(c)连通图,只有一个连通分支;(d)两个连通分支:afbgd和ech。38、写出图9.27的关联矩阵。11000000??10?111000???00?1000?1?解答:?0??0000?11?11????0?1100?110??【篇二:离散数学及其应用(课后习题)】出下列命题是原子命题还是复合命题。(3)大雁北回,春天来了。(4)不是东风压倒西风,就是西风压倒东风。(5)张三和李四在吵架。解:(3)和(4)是复合命题,(5)是原子命题。习题1.21.指出下列命题的真值:(1)若2?2?4,则太阳从西方升起。解:该命题真值为t(因为命题的前件为假)。(3)胎生动物当且仅当是哺乳动物。解:该命题真值为f(如鸭嘴兽虽是哺乳动物,但不是胎生动物)。2.令p:天气好。q:我去公园。请将下列命题符号化。(2)只要天气好,我就去公园。(3)只有天气好,我才去公园。(6)天气好,我去公园。解:(2)p?q。(3)q?p。(6)p?q。习题1.32.将下列命题符号化(句中括号内提示的是相应的原子命题的符号表示):(1)我去新华书店(p),仅当我有时间(q)。(3)只要努力学习(p),成绩就会好的(q)。(6)我今天进城...