离散数学图论部分综合练习讲解.doc

离散数学图论单元测验题一、单项选择题(本大题共10小题，每小题2分，共20分)1、在图G ＝<V ,E >中，结点总度数与边数的关系是( )(A) deg(v i )=2∣E ∣ (B) deg(v i )=∣E ∣ (C)∑∈=V v E v 2)deg( (D) ∑∈=Vv E v )deg(2、设D 是n 个结点的无向简单完全图，则图D 的边数为( )(A) n (n －1) (B) n (n +1) (C) n (n －1)/2 (D) n (n +1)/23、 设G ＝<V ,E >为无向简单图，∣V ∣=n ，∆(G )为G 的最大度数，则有(A) ∆(G )<n (B)∆(G )≤n (C) ∆(G )>n (D) ∆(G )≥n4、图G 与G '的结点和边分别存在一一对应关系，是G ≌G '(同构)的( )(A) 充分条件 (B) 必要条件 (C)充分必要条件 (D)既非充分也非必要条件5、设},,,{d c b a V =，则与V 能构成强连通图的边集合是( )(A) },,,,,,,,,{><><><><><=c d b c d b a b d a E(B) },,,,,,,,,{><><><><><=c d d b c b a b d a E(C) },,,,,,,,,{><><><><><=c d a d c b a b c a E6、有向图的邻接矩阵中，行元素之和是对应结点的( )，列元素之和是对应结点的() (A)度数 (B) 出度 (C)最大度数 (D) 入度7、设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100000100则G 的边数为( )．A ．5B ．6C ．3D ．48、设m E n V E V G ==>=<,,,为连通平面图且有r 个面，则r ＝( )(A) m －n +2 (B) n －m －2 (C) n +m -2 (D) m +n +29、在5个结点的二元完全树中，若有4条边，则有 ( )片树叶。

离散数学图论部分期末复习辅导一、单项选择题 1．设图G ＝<V , E >，v V ，则下列结论成立的是 ( ) ．A ．deg(v )=2EB ．deg(v )=EC ．deg()2||v Vv E ∈=∑ D ．deg()||v Vv E ∈=∑解 根据握手定理（图中所有结点的度数之和等于边数的两倍）知，答案C 成立。

答 C2．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100100110， 则G 的边数为( )．A ．6B ．5C ．4D ．3解 由邻接矩阵的定义知，无向图的邻接矩阵是对称的．即当结点v i 与v j 相邻时，结点v j 与v i 也相邻，所以连接结点v i 与v j 的一条边在邻接矩阵的第i 行第j 列处和第j 行第i 列处各有一个1，题中给出的邻接矩阵中共有10个1，故有102=5条边。

答 B3．已知无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0111110101110001000111010，则G 有（ ）．A ．5点，8边B ．6点，7边C ．6点，8边D ．5点，7边解 由邻接矩阵的定义知，矩阵是5阶方阵，所以图G 有5个结点，矩阵元素有14个1，14÷2=7，图G 有7条边。

答 D4．如图一所示，以下说法正确的是 ( ) ． A ．{(a, e )}是割边 B ．{(a, e )}是边割集C ．{(a, e ) ,(b, c )}是边割集D ．{(d, e)}是边割集定义3.2.9 设无向图G =<V ,E >为连通图，若有边集E 1ÌE ，使图G 删除了E 1的所有边后，所得的子图是不连通图，而删除了E 1的任何真子集后，所得的子图仍是连通图，则称E 1是G 的一个边割集．若边割集为单元集{e }，则称边e 为割边（或桥）．解 割边首先是一条边，因为答案A 中的是边集，不可能是割边，因此答案A 是错误的．删除答案B 或C 中的边后，得到的图是还是连通图，因此答案B 、C 也是错误的．在图一中，删去(d , e )边，图就不连通了，所以答案D 正确． 答 D注：如果该题只给出图的结点和边，没有图示，大家也应该会做．如：若图G =<V , E >，其中V ={ a , b , c , d , e }，E ={ (a , b ), (a , c ) , (a , e ) , (b , c ) , (b , e ) , (c , e ) , (e , d )}，则该图中的割边是什么？5．图G 如图二所示，以下说法正确的是 ( )． A ．a 是割点 B ．{b, c}是点割集 C ．{b , d }是点割集 D ．{c }是点割集定义3.2.7 设无向图G =<V ,E >为连通图，若有点集V 1ÌV ，使图G 删除了V 1的所有结点后，所得的子图是不连通图，而删除了V 1的任何真子集后，所得的子图仍是连通图，则称V 1是G 的一个点割集．若点割集为单元集{v }，则称结点v 为割点．οοο ο a bc d图一 οe ο οο a b c d图二ο解 在图二中，删去结点a 或删去结点c 或删去结点b 和d 图还是连通的，所以答案A 、C 、D 是错误的．在图二中删除结点b 和c ，得到的子图是不连通图，而只删除结点b 或结点c ，得到的子图仍然是连通的，由定义可以知道，{b, c }是点割集．所以答案B 是正确的． 答 B6．图G 如图三所示，以下说法正确的是 ( ) ． A ．{(a, d )}是割边 B ．{(a, d )}是边割集C ．{(a, d) ,(b, d)}是边割集D ．{(b , d )}是边割集解 割边首先是一条边，{(a, d )}是边集，不可能是割边．在图三中，删除答案B 或D 中的边后，得到的图是还是连通图．因此答案A 、B 、D 是错误的．在图三中，删去(a,d )边和(b, d )边，图就不连通了，而只是删除(a, d )边或(b, d )边，图还是连通的，所以答案C 正确．7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是( )．图四A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的复习：定义3.2.5 在简单有向图中，若在任何结点偶对中，至少从一个结点到另一个结点可达的，则称图G 是单向（侧）连通的；若在任何结点偶对中，两结点对互相可达，则称图G 是强连通的；若图G 的底图，即在图G 中略去边的方向，得到的无向图是连通的，则称图G 是弱连ο ο ο a bcd图三ο通的．显然，强连通的一定是单向连通和弱连通的，单向连通的一定是弱连通，但其逆均不真．定理3.2.1一个有向图是强连通的，当且仅当G中有一个回路，其至少包含每个结点一次．单侧连通图判别法：若有向图G中存在一条经过每个结点至少一次的路，则G是单侧连通的。

第三篇图论第八章图图的基本知识内容提要8.1.1 图的定义及有关术语定义图（graph）G由三个部分所组成：（1）非空集合V(G)，称为图G的结点集，其成员称为结点或顶点（nodes or vertices）。

（2）集合 E(G)，称为图G的边集，其成员称为边(edges)。

I（3）函数ΨG：E(G)→(V(G)，V(G))，称为边与顶点的关联映射（associatve mapping）。

这里（V(G)，V(G)）称为VG的偶对集，其成员偶对（pair）形如（u，v），u，v为结点，它们未必不同。

ΨG(e) = (u,v)时称边e关联端点u，v。

当(u,v)用作序偶时(V(G)，V(G)) =V(G) ?V(G)，e称为有向边，e以u为起点,以v为终点, 图G称为有向图（directed graph）；当(u,v)用作无序偶对时，(u,v) = (v,u)，称e为无向边（或边），图G称为无向图（或图）。

图G常用三元序组< V(G)，E(G)，ΨG>,或< V，E，Ψ>来表示。

显然，图是一种数学结构，由两个集合及其间的一个映射所组成。

定义8. 2 设图G为< V，E，Ψ>。

（l）当V和E为有限集时，称G为有限图，否则称G为无限图。

本书只讨论有限图。

（2）当ΨG 为单射时，称G为单图；当ΨG为非单射时，称G为重图，又称满足Ψ(e1) = Ψ(e2)的不同边e1,e2,为重边,或平行边。

（3）当Ψ(e)＝(v,v)（或<v,v>）时，称e为环（loops）。

无环和重边的无向单图称为简单图。

当G为有限简单图时，也常用（n，m）表示图G，其中n = ?V ?，m = ?E ? 。

（4）Ψ为双射的有向图称为有向完全图；对每一(u，v)，u ? v，均有e使Ψ(e)＝(u,v)的简单图称为无向完全图，简称完全图，n个顶点的完全图常记作Kn。

（5）在单图G中，Ψ(e)＝(u,v)（或<u，v>）时，也用(u,v)(或<u,v>)表示边e，这时称u，v邻接e, u,v是e的端点（或称u为e的起点，v为e的终点）;也称e关联结点u , v 。

作业答案：图论部分P165:习题九1、 给定下面4个图（前两个为无向图，后两个为有向图）的集合表示，画出它们的图形表示。

（1）111,G V E =<>，112345{,,,,}V v v v v v =，11223343345{(,),(,),(,),(,),(,)}E v v v v v v v v v v = （2）222,G V E =<>，21V V =，11223344551{(,),(,),(,),(,),(,)}E v v v v v v v v v v = （3）13331,,,D V E V V =<>=31223324551{,,,,,,,,,}E v v v v v v v v v v =<><><><><> （4）24441,,,D V E V V =<>=31225523443{,,,,,,,,,}E v v v v v v v v v v =<><><><><> 解答： （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 是(2)n n ≥阶无向简单图，G 是它的补图，已知12(),()G k G k δ∆==，求()G ∆，()G δ。

解答：2()1G n k ∆=--；1()1G n k δ=--。

15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双射函数。

解答：（c ）不是同构，从点度既可以看出，一个点度序列为4，3，3，3，3而另外一个为4，4，3，3，1（d ）同构，同构函数为12()345x a x bf x x c x d x e=⎧⎪=⎪⎪==⎨⎪=⎪=⎪⎩ 16、画出所有3条边的5阶简单无向图和3条边的3阶简单无向图。

离散数学集合论部分综合练习本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次是集合论部分的综合练习。

一、单项选择题1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）．A．A⊂B，且A∈B B．A∈B，但A⊄BC．A⊂B，但A∉B D．A⊄B，且A∉B2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )．A．{a，{ a }}∈A B．{ a }⊆AC．{2}∈A D．∅∈A3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )．A．{a，{a}}∈A B．{2}⊆AC．{a}⊆A D．∅∈A4．若集合A={a，b，{1，2 }}，B={1，2}，则（）．A．B⊂ A，且B∈A B．B∈ A，但B⊄AC．B ⊂ A，但B∉A D．B⊄ A，且B∉A5．设集合A = {1, a }，则P(A) = ( )．A．{{1}, {a}} B．{∅,{1}, {a}}C．{∅,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }}6．若集合A的元素个数为10，则其幂集的元素个数为（）．A．1024 B．10 C．100 D．17．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={<x，y>|x+y=10且x, y∈A}，则R 的性质为（）．A．自反的B．对称的C．传递且对称的D．反自反且传递的8．设集合A = {1，2，3，4，5，6 }上的二元关系R ={<a , b>⎢a , b∈A , 且a +b = 8}，则R具有的性质为（）．A．自反的B．对称的C．对称和传递的D．反自反和传递的9．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．A．0 B．2 C．1 D．310．设集合A={1 , 2 , 3 , 4}上的二元关系R = {<1 , 1>，<2 , 2>，<2 , 3>，<4 , 4>}，S = {<1 , 1>，<2 , 2>，<2 , 3>，<3 , 2>，<4 , 4>}，则S 是R 的（ ）闭包．A ．自反B ．传递C ．对称D ．以上都不对11．设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系 的哈斯图如图一所示，若A 的子集B = {3 , 4 , 5}，则元素3为B 的（ ）．A ．下界B ．最大下界C ．最小上界D ．以上答案都不对12．设A ={1, 2, 3, 4, 5, 6, 7, 8}，R 是A 上的整除关系，B ={2, 4, 6}，则集合B 的最大元、最小元、上界、下界依次为 ( )．A ．8、2、8、2B ．无、2、无、2C ．6、2、6、2D ．8、1、6、113．设A ={a , b }，B ={1, 2}，R 1，R 2，R 3是A 到B 的二元关系，且R 1={<a ，2>, <b ，2>}，R 2={<a ，1>, <a ，2>, <b ，1>}，R 3={<a ，1>, <b ，2>}，则（ ）不是从A 到B 的函数．A ．R 1和R 2B ．R 2C ．R 3D ．R 1和R 3二、填空题1．设集合A 有n 个元素，那么A 的幂集合P (A )的元素个数为 ．2．设集合A ＝{a ，b }，那么集合A 的幂集是 ． 应该填写：{∅,{a ,b },{a },{b }}3．设集合A ={0, 1, 2, 3}，B ={2, 3, 4, 5}，R 是A 到B 的二元关系， },,{B A y x B y A x y x R ⋂∈∈∈><=且且则R 的有序对集合为 ．4．设集合A ={0, 1, 2}，B ={0, 2, 4},R 是A 到B 的二元关系，},,{B A y x B y A x y x R ⋂∈∈∈><=且且则R 的关系矩阵M R ＝．5．设集合A ={a ,b ,c }，A 上的二元关系R ={<a , b >,<c . a >}，S ={<a , a >,<a , b >,<c , c >}则(R •S )－1= ．6．设集合A =｛a ,b ,c ｝，A 上的二元关系R ={<a , b >, <b , a >, <b , c >, <c , d >}，则二元关系R 具有的性质是 ．7．若A ={1,2}，R ={<x , y >|x ∈A , y ∈A , x +y =10}，则R 的自反闭包为 ．8．设集合A ={1, 2}，B ={a , b }，那么集合A 到B 的双射函数是 ．5 图一9．设A ={a ，b ，c }，B ={1，2}，作f ：A →B ，则不同的函数个数为 ．三、判断说明题（判断下列各题，并说明理由．）1．设A 、B 、C 为任意的三个集合，如果A ∪B =A ∪C ，判断结论B =C 是否成立？并说明理由．2．如果R 1和R 2是A 上的自反关系，判断结论：“R -11、R 1∪R 2、R 1⋂R 2是自反的” 是否成立？并说明理由．3． 若偏序集<A ，R >的哈斯图如图一所示，则集合A 的最大元为a ，最小元不存在．4．若偏序集<A ，R >的哈斯图如图二所示，则集合A 的最大元为a ，最小元不存在．5．设N 、R 分别为自然数集与实数集，f ：N→R ，f (x )=x +6，则f 是单射．四、计算题 1．设集合A ＝{a , b , c }，B ={b , d , e }，求（1）B ⋂A ； （2）A ⋃B ； （3）A －B ； （4）B ⊕A ．2．设A ={{a , b }, 1, 2}，B ={ a , b , {1}, 1}，试计算（1）（A -B ） （2）（A ∪B ） （3）（A ∪B ）-（A ∩B ）．3．设集合A ={{1},{2},1,2}，B ={1,2,{1,2}}，试计算（1）（A -B ）； （2）（A ∩B ）； （3）A ×B ．4．设A ={0，1，2，3，4}，R ={<x ，y >|x ∈A ，y ∈A 且x +y <0}，S ={<x ，y >|x ∈A ，y ∈A 且x +y ≤3}，试求R ，S ，R •S ，R -1，S -1，r (R )．5．设A ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}，R 是A 上的整除关系，B ={2, 4, 6}．（1）写出关系R 的表示式； （2）画出关系R 的哈斯图；（3）求出集合B 的最大元、最小元．6．设集合A ＝{a , b , c , d }上的二元关系R 的关系图 如图三所示．（1）写出R 的表达式； （2）写出R 的关系矩阵； （3）求出R 2．7．设集合A ={1，2，3，4}，R ={<x , y >|x , y ∈A ；|x -y |=1或x -y =0}，试（1）写出R 的有序对表示； （2）画出R 的关系图；（3）说明R 满足自反性，不满足传递性．五、证明题1．试证明集合等式：A ⋃ (B ⋂C )=(A ⋃B ) ⋂ (A ⋃C )．2．试证明集合等式A ⋂ (B ⋃C )=(A ⋂B ) ⋃ (A ⋂C )．图一 图二 a d bc 图三3．设R 是集合A 上的对称关系和传递关系，试证明：若对任意a ∈A ，存在b ∈A ，使得<a , b >∈R ，则R 是等价关系．4．若非空集合A 上的二元关系R 和S 是偏序关系，试证明：S R ⋂也是A 上的偏序关系．参考解答一、单项选择题1．A 2．B 3．C 4．B 5．C 6．A 7．B8．B 9．B 10．C 11．C 12．B 13．B二、填空题1．2n2．{∅,{a ,b },{a },{b }}3．{<2, 2>，<2, 3>，<3, 2>}，<3, 3>4．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡0110000115．{<a . c >, <b , c >}6．反自反的7．{<1, 1>, <2, 2>}8．{<1, a >, <2, b >}，{<1, b >, <2, a >}9．8三、判断说明题（判断下列各题，并说明理由．）1．解：错．设A ={1, 2}，B ={1}，C ={2}，则A ∪B =A ∪C ，但B ≠C ．2．解：成立．因为R 1和R 2是A 上的自反关系，即I A ⊆R 1，I A ⊆R 2。

离散数学习题解答 习题六 （第六章 图论）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的圈。

习题十1. 设G 是一个(n ，m)简单图。

证明：，等号成立当且仅当G 是完全图。

证明：（1）先证结论：因为G 是简单图，所以G 的结点度上限 max(d(v)) ≤ n-1, G 图的总点度上限为 max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。

根据握手定理，G 图边的上限为 max(m) ≤ n(n-1)/2,所以。

（2） =〉G 是完全图 因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。

所以，G 的每个结点的点度都为n-1，G 为完全图。

G 是完全图 =〉 因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数 。

■2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。

证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。

与题设m = n+1，矛盾。

因此，G 中存在顶点u ，d （u ）≥3。

■3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5）解：除序列（1）不是图序列外，其余的都是图序列。

因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。

可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。

最后，将奇数序列对应的点两两一组，添加连线即可。

下面以（2）为例说明：(6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5}每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)v 1v 5v 3v 4v 2将奇数3，3 对应的结点v 2,v 3一组，画一条连线其他序列可以类式作图，当然大家也可以画图其它不同的图形。

离散数学形考任务2图论部分概念及性质
单项选择题
●如图所示，以下说法正确的是( )．答案是：e是割点
●如图一所示，以下说法正确的是( ) ．答案是：{(d, e)}是边割集
●若G是一个汉密尔顿图，则G一定是( )．答案是：连通图
●若G是一个欧拉图，则G一定是( )．答案是：连通图
●设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．答案是：e－v＋2
●设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵
生成树．答案是：m-n+1
●设图G＝<V, E>，vV，则下列结论成立的是( )
●设无向图G的邻接矩阵为则G的边数为( )．答案是：7
●设无向图G的邻接矩阵为则G的边数为( )．答案是：7
●设有向图（a）、（b）、（c）与（d）如图所示，则下列
结论成立的是( )．答案是：（a）是强连通的
●设有向图（a）、（b）、（c）与（d）如图所示，则下列
结论成立的是( )．答案是：（d）只是弱连通的
●图G如图三所示，以下说法正确的是( )．答案是：{b, c}是点割集
●图G如图四所示，以下说法正确的是( ) ．答案是：{(a, d) ,(b, d)}是边割
集。

北京科技大学远程教育学院《离散数学》综合练习(一)参考答案数理逻辑一、判断下列句子是否是命题，若是命题判断真值，并将其符号化。

1、今天天气真好！解：不是命题。

2、王华和张民是同学。

解：是命题。

真值视实际情况而定。

p：王华和张民是同学。

3、我一边吃饭，一边看电视。

解：是命题。

真值视实际情况而定。

p：我吃饭。

q：我看电视。

p∧q 4、没有不呼吸的人。

解：是命题。

真值为1。

M(x)：x是人。

F(x)：x呼吸。

∀x(M(x)→F(x))二、求命题公式的真值表和成真赋值、成假赋值。

p→∧qr∧→(p])[(r)解：成真赋值：000，001，010，011，101，111；成假赋值100，110三、用真值表、等值演算两种方法判别公式类型。

1、r q q p →∧→])[( 解：rq q p r q q q p r q q p rq q p r q q p r q q p ∨⌝∧⌝∨⇔∨⌝∨⌝∧⌝∨⇔∨⌝∨⌝∧⇔∨⌝∨∨⌝⌝⇔∨∧∨⌝⌝⇔→∧→])[()]()[()()(])[(])[(可满足式2、))((p q p q ∧∨⌝⌝∨ 解：))((p q p q A ∧∨⌝⌝∨=1)()()())((⇔∨⌝∨∨⌝⌝⇔⌝∨∨⌝⌝∨⇔∧∨⌝⌝∨q p q p p q p q p q p q永真式四、求命题公式的主析取范式和成真赋值、成假赋值。

)(r q p →→ 解：∑=→→），，，，，，7543210()(r q p 成真赋值：000，001，010，011，100，101，111；成假赋值110 五、解释I 如下：D 是实数集，特定元素a =0；特定函数f (x ，y )=x -y ；特定谓词F (x ，y )：x<y 。

在解释I 下判别公式真、假。

1、)])(([x y x f F y x ，，⌝∀∀ 解：)])[()])(([)]([)])(([x y x y x x y x y x x y x F y x x y x f F y x ≥-∀∀⇔<-⌝∀∀⇔-⌝∀∀⇔⌝∀∀，，，真值为假2、)]()([)({z y f z x f F y x F z y x ，，，，→∀∀∀ 解：)]()()[()]}()([)({z y z x y x z y x z y f z x f F y x F z y x -<-→<∀∀∀⇔→∀∀∀，，，，真值为真 六、1、求前束范式)()(y x yG x xF ，∀→⌝∃ 解：)]()([)()()()()()(y t G x F y x y t yG x xF y x yG x xF y x yG x xF ，，，，∨∀∃⇔∀∨∃⇔∀∨∃⇔∀→⌝∃2、证明：B x xA B x A x →∀⇔→∃)())(( 证明：Bx xA Bx xA B x A x B x A x B x A x →∀⇔∨⌝∀⇔∨⌝∃⇔∨⌝∃⇔→∃)()()())(())((七、写出下面推理的证明，要求写出前提、结论，并注明推理规则。

离散数学习题三参考答案第三节图论1.画出所有4个顶点的简单图。

解：本题这考虑连通图的情况。

共有5个不同构的图。

2.在某次宴会上，许多人互相握手，证明奇数次握手的人一定是偶数个。

解：设每个人看成一个顶点，两人握手看成两顶点间的一条边，每人握手的次数就是该顶点的度数，由定理1的推论2马上可得结论。

3.设图G＝（V，E）中有12条边，已知G中3度顶点的有3个，其余顶点的度数均小于3，问G中至少有多少个顶点？为什么？解：如图G不是连通图，那么12条边最多的顶点数是12×2=24；一个顶点的度数是3，则要减去2个顶点数，所以3度顶点的有3个，就要减去2×3-6个顶点；同样一个顶点的度数是2，则要减去1个顶点数；为了使顶点数最小，图必须是连通图，所以顶点数为2的顶点的个数是（12×2-3×3）÷2的整数部分等于7个，有一个顶点的度数是1，所以G中至少有的顶点数是3+7+1=11（个）。

4.n个运动队之间安排一项比赛，已赛完了n+1场，求证：一定存在这样一个队，它已经至少参加了3场比赛。

解：如果每个运动队都只赛了2场，则共赛了2n÷2=n<n+1，所以一定存在这样一个队，它已经至少参加了3场比赛。

5.下图表示用堤埂分割成很多小块的水稻田。

为了用水灌溉需要挖开一些堤埂（不能挖堤埂的交点）。

问最少要挖开多少条堤埂，才能使水浇灌到每小块稻田？第五题解：把每块田看成顶点，相邻的田同一条边连接，这题就是最小生成树问题。

因为有12块田地，所以最少要挖开11条堤埂，才能使水浇灌到每小块稻田。

（见上右图）6在下列图中，求一条欧拉通路。

解：略2，其中m为图的边数，n为图的顶7.证明：若G=〈V，E〉是简单图，则m≤Cn点数。

（7，9一样）解：顶点数相同的情况下，简单图的边数一定小于完全图的边数。

8.设G是一个连通图，不含奇数点，证明：从G中任意去掉一条边，得到的图仍是连通图。

离散数学图论部分综合练习辅导本次活动是本学期的第二次活动(2008.11.18)，主要是针对第二单元图论的重点学习内容进行辅导，方式是通过讲解一些典型的综合练习题目，帮助大家进一步理解和掌握图论的基本概念和方法。

图论作为离散数学的一部分，主要介绍图论的基本概念、理论与方法。

教学内容主要有图的基本概念与结论、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等。

本次综合练习主要是复习这一部分的主要概念与计算方法，与集合论一样，也安排了五种类型，有单项选择题、填空题，判断说明题、计算题、证明题。

这样的安排也是为了让同学们熟悉期末考试的题型，能够较好地完成这一部分主要内容的学习。

下面分别讲解。

一、单项选择题1．设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡010*******000011100000100 则G 的边数为( )．A ．5B ．6C ．3D ．4正确答案：D上学期的作业中，有的同学选择答案B 。

主要是对邻接矩阵的概念理解不到位。

我们复习定义：定义3.3.1 设G =<V ，E >是一个简单图，其中V ={v 1，v 2，…， v n }，则 n 阶方阵A （G ）=（a ij ）称为G 的邻接矩阵．其中各元素⎪⎩⎪⎨⎧==ji v v v v a j i j i ij 不相邻或与相邻与01 而当给定的简单图是无向图时，邻接矩阵为对称的．即当结点v i 与v j 相邻时，结点v j 与v i 也相邻，所以连接结点v i 与v j 的一条边在邻接矩阵的第i 行第j 列处和第j 行第i 列处各有一个1，题中给出的邻接矩阵中共有8个1，故有8÷2=4条边。

2．设图G ＝<V , E >，则下列结论成立的是 ( )．A ．deg(V )=2∣E ∣B ．deg(V )=∣E ∣C ．E v V v 2)deg(=∑∈D ．E v Vv =∑∈)deg(正确答案：C该题主要是检查大家对握手定理掌握的情况。

《离散数学》图论部分习题《离散数学》图论部分习题1.已知⽆向图G有12条边，6个3度顶点，其余顶点的度数均⼩于3，问G⾄少有⼏个顶点？并画出满⾜条件的⼀个图形. （24-3*6）/2 +6=92.是否存在7阶⽆向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.不存在；7阶⽆向简单图G中最⼤度≤63.设d1、d2、…、d n为n个互不相同的正整数. 证明：不存在以d1、d2、…、d n为度序列的⽆向简单图.Max{d1，d2，…，dn}≥n，n阶⽆向简单图G中最⼤度≤n-14.求下图的补图.5.1)试画⼀个具有5个顶点的⾃补图2)是否存在具有6个顶点的⾃补图，试说明理由。

对于n阶图，原图与其补图同构，边数应相等，均为(n*(n-1)/2)/2，即n*(n-1)/4且为整数，n=4k或n=4k+1，不存在6阶⾃补图。

6.设图G为n(n>2且为奇数)阶⽆向简单图，证明：G与G的补图中奇度顶点个数相等.n(n>2且为奇数)，奇度点成对出现7.⽆向图G中只有2个奇度顶点u和v，u与v是否⼀定连通.给出说明或证明。

只有2个奇度顶点u和v，如果不连通，在u和v在2个连通分⽀上，每个分⽀上仅有⼀个奇度顶点，与握⼿引理相⽭盾。

8.图G如下图所⽰：1)写出上图的⼀个⽣成⼦图.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.说明：δ(G)=min{ d(v) | v V } ；κ(G)=min{ |V’| |V’是图G的点割集} ；λ(G)=min{ |E’| |E’是图G的边割集} 9.在什么条件下⽆向完全图K n为欧拉图？n为奇数时10.证明：有桥的图不是欧拉图.假设是欧拉图：桥的端点是u和v，并且图各顶点度均为偶数；桥为割边，删除桥，图不再连通，u和v应该在2各不同的连通分⽀上；且u和v度数变为奇数；由于其他顶点度数均为偶数，则u和v所在的连通分⽀上只有⼀个奇度顶点，与握⼿引理⽭盾。