离散数学及应用课后习题答案【篇一：离散数学及其应用图论部分课后习题答案】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）我今天进城...
