离散数学(第23讲习题课4)

冯伟森Email：fws365@Tel:1380819227505二月2023离散数学计算机学院2023/2/5计算机学院2主要内容习题课四2023/2/5计算机学院3基本要求（第六章）掌握函数、单射、满射和双射的概念会正确判断一个函数是否为单射、满射和双射掌握置换、循环和循环的积、复合函数、逆函数等基本概念掌握双射和逆函数、复合函数的关系掌握集合的基数、等势的基本概念掌握可数集、不可数集的定义了解Cantor定理掌握可数集、不可数集的基本性质2023/2/5计算机学院4第十章理解与图的定义有关的诸多概念，以及它们之间的相互关系深刻理解握手定理及其推论的内容，并能熟练地应用它们深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图等概念及其它们的性质和相互关系，并能熟练地应用它们深刻理解道路、简单道路、基本道路与回路、圈的定义，掌握道路与回路的各种表示方法2023/2/5计算机学院5深刻理解无向图的连通性，连通分支等概念深刻理解无向图的点割集和边割集、点连通度、边连通度等概念及其之间的关系，并能熟练地求出给定的较为简单的图的点割集和边割集、点连通度与边连通度深刻理解有向图连通性的概念及其分类，掌握判断有向连通图类型的方法深刻理解有向图的邻接矩阵、可达矩阵的基本概念2023/2/5计算机学院6熟练掌握用有向图的邻接矩阵及各次幂求图中通路与回路数的方法熟练掌握用有向图的邻接矩阵及Warshall算法求有向图的所有强分图的方法了解关联矩阵的基本概念及其基本性质2023/2/5计算机学院7例1

解：{v2,v3}是个基本点割集,而G的点割集必须含有点v2和v3,因为它们中每一个都与图中除其自身外的各顶点邻接.故{v2,v3}是该图唯一的基本点割集.求出下图G中的全部基本点割集和基本边割集.v1v5v4v3v2aedcbfgh2023/2/5计算机学院8

每一个基本边割集把连通图分成恰好2个连通分支，因而导出图的顶点集的一个分成两组的划分(同一个连通分支中的顶点组成一个划分块)。本题中，顶点集V是个5元集,正整数5分成两个数的划分有1+4和2+3。V的“1+4”的划分有C15=5个。如下表所列,表中还列出了相应的边割集:边割集 顶点集V的划分 {a,b} {{v1},{v2,v3,v4,v5}} {a,c,d,f} {{v2},{v1,v3,v4,v5}} {b,c,e,h} {{v3},{v1,v2,v3,v5}} {d,e,g} {{v4},{v1,v2,v3,v4}} {f,g,h} {{v5},{v1,v3,v3,v4}} 2023/2/5计算机学院9V的“2+3”的划分有C25=10个,其中7个可以由基本边割集导出,如下表所示:

基本边割集 顶点集V的划分 {b,c,d,f} {{v1,v2},{v3,v4,v5}} {a,c,e,h} {{v1,v3},{v2,v4,v5}} {a,c,e,f,g} {{v1,v3,v5},{v2,v4}} {a,c,d,g,h} {{v1,v3,v4},{v2,v5}} {b,c,d,g,h} {{v1,v2,v5},{v3,v4}} {b,c,e,f,g} {{v1,v2,v4},{v3,v5}} {d,e,f,h} {{v1,v2,v3},{v4,v5}}而V的以下3个“2+3”的划分不能由基本边割集导出:{{v2,v3},{v1,v4,v5}},{{v1,v4},{v2,v3,v5}},{{v1,v5},{v2,v3,v4}})。所以该图的基本边割集有12个。 2023/2/5计算机学院10例2证明:在一个连通图中,任意两条最长的基本道路有一个公共顶点。证：（反证法）v0u0vjukvpupL2023/2/5计算机学院11

设Γ1=v0v1…vp和Γ2=u0u1…up是G的两条最长的基本道路(长为p)，且无公共顶点。因为G是连通图.v0与u0之间有道路L.设vj是从v0出发沿L前进的最后一个和Γ1相交的顶点.而uk是道路L第一次与Γ2相交的结点。当j≥p/2(这时在基本道路Γ1上v0…vj的一段不比vj…vp的一段短)且k≥p/2时(这时在基本道路Γ2上u0…vk的一段不比uk…up的一段短)。2023/2/5计算机学院12构造一条新的路Γ′,它从v0出发,沿Γ1到vj,然后沿L从vj到uk，最后沿Γ2从uk到u0，该道路是一条基本道路(点不重复.答图中红粗线所示),其长度≥j+1+k≥p+1>p,这与L1,L2是最长的基本道路相矛盾,所以Γ1和Γ2有公共顶点.对j,k的其他情况讨论类似(分别在Γ1和Γ2上取分别被顶点vi和uk截出的两段路径中较长的一段,加上L上被顶点vi和uk截出的一段,构成一条比Γ1和Γ2都较长的基本道路)。2023/2/5计算机学院13例3

设图G中有从顶点u到v的两条不同的简单道路,证明G中有圈。证：设P1和P2是从u到v的两条不同的简单通路。设w是P1和P2的公共顶点使得随后的顶点是不同的,再设w′是继w后第一个P1和P2的公共顶点(注意到u和v是P1和P2上的公共顶点,这样的顶点w是存在的,否则P1和P2是相同的;这样的顶点w′也是存在的,因为继w后P1和P2有公共顶点v)。uww′vP1P22023/2/5计算机学院14

那么在w和w′之间P1和P2的子通路除了w和w′之外没有公共顶点,因此这两条子通路构成一个圈(顶点不重复的回路)。2023/2/5计算机学院15例4

证明:任意一场聚会,至少有两个人与相同数目的人握过手。证：即证明非平凡的简单无向图必有两个顶点的度相等。设简单无向图G有n个结点，则每个结点的度数最多为n-1，而每个结点都不可能为孤立结点，所以，任何结点的度均大于等于1,小于等于n−1,由鸽巢原理知,这样的n个数中至少有两个是相同的。所以必有两个顶点的度相等。2023/2/5计算机学院16例5

证明空间中不可能存在有奇数个面且每个面都有奇数条棱的多面体。证：（反证法）若存在某个具有奇数个面,且每个面均有奇数条棱的多面体V。不妨设V有r(r为奇数)个面,设为R1，R2，…,Rr，s1，s2，…，sr

分别为它们的棱数，均为奇数。作无向图G如下：在V的每个面中放一个顶点vi，i=1，2，…，r。且两个面Ri与Rj

有公共棱就连边。若存在这样的无向图G，则d(vi)均为奇数si。2023/2/5计算机学院17

由握手定理：但因r，si(i=1,2,…,n)均为奇数，上面等式不可能成立。故不存在这样的无向图G，从而也不存在满足要求的多面体。2023/2/5计算机学院18习题讲解习题六10、证：

2023/2/5计算机学院1915、证：2023/2/5计算机学院20习题十1、解：2023/2/5计算机学院214、证：2023/2/5计算机学院226、证明简单二部图G满足,其中

n是顶点数,m是边数。证：令V1,V2是G的两个互补顶点集合,|V1|=n1,|V2|=n2

G的边数m小于等于完全二部图的边数n1n2，而

2023/2/5计算机学院2315、若u与v是G中仅有的两个奇数度结点，证明u和v必是连通的。证：（反证法）设v与u不连通∴G={V1，V2}，v与u分别属于V1，V2二个子图∵v与u是G中仅有的二个奇数度结点∴v与u即是V1与V2中仅有的一个奇数度结点，与握手定理的推论相矛盾，故v与u必连通。2023/2/5计算机学院2417、设(n,m)简单图G满足

,证明G必是连通图。构造一个

的非连通简单图。证：（归纳法，对n进行归纳）

n=2时,∵m>0∴二个结点至少有一条边，即G是连通图2023/2/5计算机学院25设n=k时，结论成立,即时，G是连通图证n=k+1时，结论成立，即时，G是连通图（用反证法）如果G是非连通图，必存在一个结点v，使1≤d(v)<k(否则，如d(v)=0，则G-{v}是一个有k个结点的简单图，其边数与矛盾；如d(v)=k,则G是一个完全图，与假设矛盾）2023/2/5计算机学院26∴从G中删除该结点v所得子图

G′=G-v=（m′,k)其边数

由归纳假设，G′=G-v的结点数为k，所以G′是连通图，∵G=G′+{v}，而v至少有一条边，∴G连通故由归纳法，结论成立2023/2/5计算机学院27vw2023/2/5计算机学院28证：（反证法）设结论不成立，即存在

因为G是连通的，所以G-v的每个分支都至少有一个点与v相邻接，而且存在一个分支，其与v相邻接的点w只有一条边与v相连（因为如每个分支中有二个以上