离散数学-第十一章图

离散数学

第十一章

图2022/12/14211.1

图的基本概念定义11.1.1设A,B是任意集合.集合称为A和B的无序集,记为例若则定义11.1.2

图是一个二元组，其中

(1)

其元素称为顶点；

(2)E是或的多重子集,

其元素称为边若E是的多重子集,则称为无向图;若E是的多重子集,则称为有向图2022/12/14311.1

图的基本概念例11.1.1

无向图其中例11.1.1中图的图示如下

bacdef2022/12/14411.1

图的基本概念例11.1.3

有向图其中例11.1.3中图的图示如下bac2022/12/14511.1

图的基本概念定义11.1.4(1)

设是无向图，与v

关联的边数（每条自回路视为两条边）称为v的度，记为

(2)

设是有向图，以v为始点的边数称为v的出度，记为以v为终点的边数称为v的入度，记为称为v的度2022/12/14611.1

图的基本概念定理11.1.1设则推论11.1.1

任何图中度为奇数的顶点必为偶数个证设V1和V2分别为G中度数为奇数和偶数的顶点集合，那么有由为偶数知，为偶数，因而|V1|为偶数

2022/12/14711.1

图的基本概念定理11.1.2在有向图中有定义11.1.5

设图和

(1)

若且则称是G的子图,记为

(2)

若且或则称是G

的真子图，记为

(3)

若且则称是G

的生成子图

2022/12/14811.1

图的基本概念

(4)

若且是所有两端点都在中G的边组成的集合，则称是由导出的G之子图

(5)

若且是所有与关联的顶点组成的集合，则称是由导出的G之子图。定义11.1.6(1)

设是无向简单图,|V|=n,若G中任何两个顶点之间恰有一条边，则称G为无向完全图，记为Kn

2022/12/14911.1

图的基本概念(2)

设是有向简单图，|V|=n，若G中任何两个顶点之间恰有一条从u到v的边和一条从v到u的边，则称G为有向完全图，也可记为Kn。无向完全图Kn中有条边有向完全图Kn中有条边定义11.1.7设是简单图,

|V|=n,若且则称H为G的补图,

记为2022/12/141011.1

图的基本概念定义11.1.7设图和若存在双射使得对当且仅当并且与的重数相等，则称G与是同构的。下列两图是同构的

，

a1a2a3a4a5142532022/12/141111.1

图的基本概念两图同构的必要条件：

(1)结点数相同

(2)边数相同

(3)度数相同的结点数相等2022/12/141211.1

图的基本概念上述条件不是充分的例如下列两个图满足上述三个条件,但不是同构的2022/12/1413习题习题8.51,2,4

习题8.61,5习题11.1

1,2,32022/12/141411.2通路、回路和连通性定义11.2.1

给定图从顶点v0到vn的一条通路是图的一个顶点、边交替序列v0e1v1e2v2…envn,其中且是一条从到的边简单通路:

同一条边不出现两次的通路基本通路:

同一个顶点不出现两次的通路回路:

起点与终点相同的通路简单回路:同一条边不出现两次的回路基本回路:

通过各顶点不超过一次的回路2022/12/1415v2v1v5v4v3e4e7e8e6e3e1e5e211.2通路、回路和连通性例11.2.1定理11.2.1给定图若存在一条从u到v的通路，则存在一条从u到v的长度不超过n-1的通路2022/12/141611.2通路、回路和连通性证设是从u到v的通路,

其中

(1)若则结论成立

(2)若则故中至少有两个相等,不妨设则是一条长度为的通路重复此过程可得一条长度不超过n-1的通路

2022/12/141711.2通路、回路和连通性推论11.2.1给定图若存在一条从u到v的通路，则存在一条从u到v的长度不超过n-1的基本通路定理11.2.2给定图若存在一条从u到v的回路，则存在一条从u到v的长度不超过n的回路推论11.2.2给定图若存在一条从u到v的回路，则存在一条从u到v的长度不超过n的基本回路

2022/12/141811.2通路、回路和连通性定义11.2.2

给定图若存在一条从u到v的通路，则称u到v是可达的定义11.2.3

设是无向图，若对u到v是可达的,

则称G是连通图;

否则称G是非连通图G之一个极大连通子图称为G的一个连通分支

2022/12/141911.2通路、回路和连通性定义11.2.4

设是有向图，

(1)

若u和v相互可达，则称G是强连通图。

(2)

若u和v至少有一个可达另一个，则称G是单向连通图

(3)

若G的底图是连通的，则称G是弱连通图。2022/12/142011.2通路、回路和连通性有向图的极大强连通（单向连通、弱连通）子图称为G之强连通（单向连通、弱连通）分支定理11.2.3

有向图是强连通的当且仅当G中存在经过每一个顶点至少一次的回路定义11.2.5设图若u可达v，则称从u到v的长度最短的通路为u与v之间的短线程，其长度称为u到v的距离，记为d(u,v)

2022/12/142111.3

图的矩阵表示定义11.3.1

设是有向图,

则G的邻接矩阵其中是从到的边的条数例11.3.1图11.17的邻接矩阵为v1v2v3v4v5图11.172022/12/142211.3

图的矩阵表示定理11.4.1

设是有向图,

G的邻接矩阵则为从到的长度为t的通路数。证对t用归纳法当t=1时，定理显然正确假设当t=m时，定理正确当t=m+1时,由知,

2022/12/142311.3

图的矩阵表示由归纳假设知为从到的长度为m的通路数，而为从到的长度为1的通路数故

为从到的长度为m+1的通路数令则为从到的长度不超过t的通路数。2022/12/142411.3

图的矩阵表示例11.3.2

求图11.17中顶点到其它顶点的长度为3的通路数解v1v2v3v4v5图11.172022/12/142511.3

图的矩阵表示定义11.3.2设是有向图，则G的可达性矩阵其中令2022/12/142611.3

图的矩阵表示例11.3.3

图11.17的可达矩阵为类似地可以定义无向图的邻接矩阵和可达性矩阵v1v2v3v4v5图11.172022/12/142711.3

图的矩阵表示例11.3.5

图11.19的邻接矩阵A与可达性矩阵P分别为图11.19v1v2v3v4v5

2022/12/142811.4

欧拉图和哈密尔顿图定义11.4.1给定图经过G中每条边一次且仅一次的通路(回路)称为欧拉通路(回路)

，存在欧拉回路的图称为欧拉图定理11.4.1

一个无向连通图中存在欧拉通路(回路)当且仅当G中有两个(零个)奇次数的顶点定理11.4.2

一个有向连通图G中存在欧拉通路当且仅当除了两个顶点之外，G的每个顶点的入度等于它的出度,这两个顶点中一个顶点的入度比出度大1,另一个顶点的出度大于入度.2022/12/142911.4

欧拉图和哈密尔顿图推论11.4.2

一个有向连通图G中存在欧拉回路当且仅当G的每个顶点的入度等于它的出度例一笔画问题2022/12/143011.4

欧拉图和哈密尔顿图哈密尔顿通路：经过图中每个顶点一次且仅一次的通路。哈密尔顿回路：经过图中每个顶点一次且仅一次的回路。哈密尔顿图：具有哈密尔顿回路的图定理11.4.3设简单无向图若对任意不相邻的顶点都有则G中存在哈尔顿通路2022/12/143111.4

欧拉图和哈密尔顿图证首先证明G是连通的若G不连通，则G至少存在两个连通分支G1和G2

设G1和G2分别有n1和n2个顶点，u和v分别为G1和G2中的顶点，则有与假设矛盾下面证G中存在哈密尔顿通路用反证法2022/12/143211.4

欧拉图和哈密尔顿图若G中不存在哈密尔顿通路,令为G中最长的基本通路,

则且与v1和邻接的顶点都在L上下面证明G中有经过顶点的基本回路①若v1与邻接,

则是这样的一条基本回路②否则，设则不妨设v1与L中的邻接

至少与之一邻接若不然，则有2022/12/143311.4

欧拉图和哈密尔顿图不妨设与邻接，所以是经过顶点的基本回路

由知,

必有某顶点v不在该回路上，但与回路上某顶点邻接，这样可得一长为的基本通路，与假设矛盾2022/12/143411.4

欧拉图和哈密尔顿图定理11.4.4设简单无向图若对任意不相邻的顶点都有则G中存在哈密尔顿回路例11.4.3下图中的G1和G2均是哈密尔顿图,但不满足定理11.4.4的条件2022/12/1435习题例若无向简单图中恰有两个度为奇数的顶点u和v，则存在从u到v的通路.

证用反证法若u,v之间不存在通路.则u,v分属两个不同的连通分支和于是图恰有一个度为奇数的顶点,与推论11.1.1矛盾

2022/12/143611.4

欧拉图和哈密尔顿图定义11.4.3

设是无向简单图，若存在不相邻的顶点使得则在u,v之间添加一边，这样继续下去，直至这种加边过程终止，所得到的图称为G的闭包，记为C(G)例11.4.2下列左边图的闭包如右图所示2022/12/143711.4

欧拉图和哈密尔顿图引理11.4.1设是无向简单图，u,v是G中不相邻的顶点，且则G是哈密尔顿图的充要条件是是哈密尔顿图。定理11.4.5设是无向简单图，则G是哈密尔顿图的充要条件是C(G)是哈密尔顿图。2022/12/143811.4

欧拉图和哈密尔顿图定理11.4.6

若是哈密尔顿图，则对V的每个非空子集S都有

证设C是G的一条哈密尔顿回路对V的每个非空子集S都有2022/12/143911.4

欧拉图和哈密尔顿图例11.4.3

图11.31不是哈密尔顿图2022/12/1440习题习题11.1

123习题11.212022/12/1441习题11.23

11.3122022/12/144211.5偶图和匹配定义11.5.1

若无向图的顶点集V可以划分成两个非空子集V1和V2,即有使得G中每一条边的一个端点在V1中，另一个端点在V2中，则称G为偶图或二分图，记为若V1中的每个顶点与V2中的每个顶点有且仅有一条边相关联，则称偶图G为完全偶图。当|V1|=m，|V2|=n时，则记完全偶图为Km,n。2022/12/144311.5偶图和匹配定理11.5.1一个图G是偶图当且仅当G中没有奇数长度的回路。证必要性若是偶图对G中任一个回路C=(v0,v1,v2,…,vk,v0),不妨设那么故k必为奇数于是C中有k+1条边，即C中有偶数条边充分性若G中没有奇数长度的回路设G为连通图。任取定义2022/12/144411.5偶图和匹配

对任有一条从v0到vi的长度为奇数的最短路径P1,有一条从v0到vj的长度为奇数的最短路径P2

若存在边(vi,vj)，那么由路径P1、P2和边(vi,vj)便构成一条长度为奇数的回路，与假设矛盾，不可

故对任

不存在边(vi,vj).

同理可证，V2中任意两点之间没有边这就证明了G是一个偶图2022/12/144511.5偶图和匹配例11.5.1下图不是偶图2022/12/144611.5偶图和匹配定义11.5.2

给定偶图若M中的边无公共端点，则称M为偶图G的一个匹配，边数最多的匹配称为G的最大匹配。若则称M是一个完备匹配；若则称M是一个完美匹配例11.5.22022/12/144711.5偶图和匹配例11.5.3现有4项任务分配给4个人并且能胜任能胜任能胜任能胜任试找出一种方案,使每项任务均由能胜任此任务的人来完成.

解2022/12/144811.5偶图和匹配定义11.5.3

设M是偶图的一个匹配,若如果G中的一条基本通路由不属于匹配M和属于M中的边交替组成，且该通路的起点和终点不是M中边的端点，那么称此通路为关于匹配M的交替链例11.5.4

求下图中关于匹配的一条交替链

2022/12/144911.5偶图和匹配定理11.5.4

偶图G的匹配M是最大匹配的充要条件是G不含关于M的交替链证必要性若M是最大匹配.

下面证明G不含关于M的交替链用反证法若G含有一条关于M的交替链P

为G之一个边数为|M|+1的匹配这与M是最大匹配的假设矛盾2022/12/145011.5偶图和匹配

充分性若G不含关于M的交替链.下面证M是最大匹配用反证法若M不是最大匹配存在最大匹配使得设为由所生成的子图的每个连通分支或是一条边交替地属于M和的长度为偶数的回路,

或是一条边交替地属于M和的通路由于故中至少有一个连通分支P中所包含中的边多于M中的边,

故P是一条关于M的交替链与假设矛盾2022/12/145111.5偶图和匹配G中关于匹配M的交替链可用下列标记法找出:

首先将X中所有不是M中边的顶点用(*)标记,然后交替地进行以下过程1、2

1.

选一个X中新标记过的顶点,譬如说xi

,用(xi

)标记不通过M中的边与xi

邻接且未标记过的Y的所有顶点.对所有X的新标记过的顶点重复这一过程

2.选一个Y中新标记过的顶点,譬如说yi

,用(yi

)标记通过M中的边与yi

邻接且未标记过的X的所有顶点.对所有Y的新标记过的顶点重复这一过程

2022/12/145211.5偶图和匹配

直到标记到一个Y的不与M中任何边邻接的顶点,或者已不可能标记更多的顶点为止.出现前一种情况,说明找到了一条关于M的交替链出现后一种情况,说明G中已不存在交替链2022/12/145311.5偶图和匹配例11.5.5

求下面的二部图的最大匹配x1x2x3x4y1y2y3y42022/12/1454习题习题11.4

3

5习题11.522022/12/145511.6

平面图定义11.6.1设无向图如果能把它图示在平面上，使得任意两条边除了在顶点处外，互不相交，则称G为可平面图。可平面图G在平面上的一个嵌入称为平面图例K4是一个可平面图2022/12/145611.6

平面图例K33不是可平面图一个平面图G可把平面划分为若干个连通区域，每一个区域称为一个面，若面的面积是有限的，则称为有限面，否则称为无限面2022/12/145711.6

平面图定理11.6.1

设是有k个面的连通平面图,

则证对边数用归纳法当m=0时,

G为一个孤立顶点,

这时n=1,m=0,k=1

定理成立假设定理对m=r成立,下面证明定理对m=r+1也成立分下列两种情况讨论

2022/12/145811.6

平面图

(1)

G中有度数为1的顶点v

将v从G中删除得而是一个具有r条边的平面图，中有n-1个顶点,

r条边,

k个面由归纳假设知定理对成立，于是有

(2)G中没有度数为1的顶点易知G中有基本回路从G中删除基本回路上的一条边e得中有n个顶点，r条边，k-1个面2022/12/145911.6

平面图由归纳假设知定理对成立，于是有这就归纳地证明了欧拉公式定理11.6.3

设是连通简单平面图，且则证因为G是简单图,G的每个面的边界至少由三条边所组成,故各个面的边界上的总边数大于或等于3k

又因为每条边至多在两个面的边界上，所以各个面的边界上的总边数小于或等于2m，因此有

2022/12/146011.6

平面图

代入欧拉公式得：例K5不是可平面图解对于K5,n=5,m=10

若K5是可平面图,

则由定理11.6.3知,应有不可2022/12/1461

11.6

平面图定理设是连通简单平面图，且每个面用四条边或更多条边围成,

则证因为G的每个面的边界至少由四条边所组成,故各个面的边界上的总边数大于或等于4k

又因为每条边至多在两个面的边界上，所以各个面的边界上的总边数小于或等于2m，因此有

2022/12/146211.6

平面图

代入欧拉公式得：例K3,3不是平面图解对于K3,3,n=6,m=9

若K3,3是可平面图,

则由上述定理知,应有不可

2022/12/1463

11.6

平面图定理11.6.4

设是连通简单平面图，则G中至少有一个顶点的度不超过5

证若对任都有那么有不可

2022/12/146411.6

平面图定义11.6.2

图G1和G2称为同胚(或称在2度顶点内同构的),

若G1和G2是同构的，或者通过反复插入或删除2度顶点，它们能变成同构的例11.6.1下图中的左图和右图是同胚的2022/12/146511.6

平面图定理11.6.5

一个图是可平面图当且仅当G中不含与K3,3或K5同胚的子图例下列图是否可平面图2022/12/146611.6

平面图2022/12/146711.6

平面图设是平面图,

通过以下过程得到的图G*称为G的对偶图

(1)

在的每个面Di内作一个且仅作一个顶点vi*；

(2)

当且仅当面Di与Dj的边界有公共边ei时，作一条边ei*=(vi*,vj*)；

(3)

当且仅当边ei仅为面Di的边界上的边时，作一条自回路ei*=(vi*,vi*)。2022/12/146811.6

平面图平面图G的对偶图G*的顶点数与G的面数相同,G*的边数等于G的边数,

且G*也是平面图2022/12/146911.6.5

图的着色定义11.6.4若能对图G的每个顶点指定k种颜色的一种颜色着色，使得任何两个邻接的顶点着不同的颜色，则称G是k-可着色的。若G是k-可着色的，不是(k-1)-可着色的，则称k为G之色数定理11.6.6任何平面图都是5-可着色的证对图的顶点数n用归纳法当时，定理显然正确假设定理对n-1个顶点的图正确，下面证明定理对n个顶点的图也正确2022/12/147011.6.5

图的着色由定理11.6.4知,

G中存在一个顶点v0,使得令由归纳假设知,

用五种颜色可以对H正常着色。再把v0添加回去,

有下面两种可能：

(1)

若或但与v0邻接顶点只用了至多4种颜色。则总可选择一种颜色对v0进行着色，使其与相邻顶点的颜色不同

(2)且与v0邻接顶点用了5种颜色下面分两种情况讨论：2022/12/147111.6.5

图的着色①v1和v3属于红黄集导出的子图的两个不同的分图中,

这时将

v1所在的分图中的红黄色对调,

然后将v0着上红色②v1和v3属于红黄集导出的子图的同一个分图中,那么在v1和v3

之间存在一条路径P,于是回路(v0,v1,P,v3,v0)将v2和v4划分在属于黑白集导出的子图的两个不同的分图中,

这时按照①的情形可以得到一个对G的正常着色v0v2白v3

黄v4

黑v5

蓝v1红

2022/12/1472习题习题11.61342022/12/147311.7

树定义11.7.1

不含简单回路的连通无向图称为无向树,简称树,树中度为1的顶点称为树叶,其它顶点称为分支点,每个连通分支都是树的无向图称为森林定理11.7.1

设是简单无向图,

则下列命题是等价的：

(1)G是不含简单回路的连通无向图(G是树)

(2)有唯一的一条从u到v的基本通路

(3)

G是连通的且m=n-1(4)G无简单回路且m=n-1

2022/12/147411.7

树(5)G无简单回路,

但在G中任何两个不相邻的顶点之间增加一条边得到唯一的一条基本回路证因为G是连通的,

所以G的任何两个顶点u,v之间存在基本通路.

若u,v之间存在两条基本通路,

则G中存在基本回路,

与假设矛盾,不可显然G是连通的.

下面证明m=n-1

对n用归纳法当n=1时,

m=0,结论正确

2022/12/147511.7

树假设结论对n=k时正确,下面证明结论对n=k+1也正确取则从G中去掉后G变为两个连通分支和由归纳假设知于是

2022/12/147611.7

树

只需证G无简单回路对n用归纳法当n=1时,

结论显然正确假设结论当n=k时正确,下面证明结论对n=k+1时也正确由于G有m=n-1条边,故G中有一个度为1的结点v,将v

及其关联边从G中删除,得到具有k个顶点,k-1条边的连通图G1,由归纳假设知G1无简单回路,因而G也无简单回路2022/12/147711.7

树

先证G连通用反证法若G不连通,

则G有r

个连通分支由G无回路知,Gi无回路,故Gi是树,于是有与m=n-1的假设矛盾,不可2022/12/147811.7

树

设u

,v是不相邻的顶点.

由于G是连通的,故u到v存在基本通路L,若在u

,v之间添加一条边(u,v)后,

通路L与边(u,v)便构成G之一条基本回路若u

,v之间添加边(u,v)后,有两条不同的基本回路,则删除边(u,v)后,

可得G中的一条基本回路,与假设矛盾只需证G连通若G不连通,

则G中至少有两个连通分支G1和G2.

任取G1中的顶点u和G2中的顶点v,添加边(u,v)后,

G

中无回路,与假设矛盾2022/12/147911.7

树定理11.7.2

设是树,

则T中至少有两片树叶证因为T连通,所以T中每个顶点的度至少为1

设度为1的点的个数为k,则有于是有2022/12/148011.7

树定义11.7.2

给定一个无向图G,若G的一个生成子图T是树,则称T为G的生成树定理11.7.3任何连通无向图至少有一棵生成树定义11.7.3设是赋权连通无向图,T是G的生成树,

T中树枝的权之和定义为T的权,记为

所有生成树中具有最小权的生成树称为最小生成树2022/12/148111.7

树求最小生成树的算法

1.

避圈法

2.

破圈法例11.7.12124111856109732124111856109732022/12/148211.7

树定义11.7.4满足以下条件的有向图是有向树：

(1)

有且仅有一个顶点的入度为0(称之为树根)

(2)除树根外，每一顶点的入度为1

(3)从树根到任何顶点都有一条有向通路树叶:

入度为1,出度为0的顶点内点:入度为1,出度大于0的顶点分支点:树根和内点m元树:分支点至多有m个儿子的有向树m元正则树:分支点恰有m个儿子的有向树2022/12/148311.7

树定义11.7.5

设二元正则树T有t片树叶分别带权称

为T的权,

其中是从树根到树叶vi的通路的长度.

在所有带权的t片树叶的二元正则树中，权最小的树称为带权的最优二元树2022/12/148411.7

树定理11.7.4

带权的最优二元树中,

必有T使得带权w1和w2的两片叶子v1和v2是兄弟证设T0是一棵带权的最优二元树，a是T0中从树根到a的通路最长的分支点.

设其儿子为vx和vy,它们分别带权wx和wy,那么有不妨设将顶点与、与及其权互换得到新树T,并且2022/12/148511.7

树所以，T也是一棵带权的最优二元树，且带权的叶子是兄弟。2022/12/148611.7

树定理11.7.5设T1是带权的最优二元树,其中在T1中，让带权的树叶产生两片分别带权w1和w2的树叶，则得到带权的最优二元树T

2022/12/148711.7

树证设是带权的最优二元树,

且带权w1和w2的叶子v1和v2是兄弟.

又设是在中删除v1与v2,并使其父亲的权为的树,则并且于是有因此T是带权的最优二元树

2022/12/148811.7

树例11.7.3

求带权3,4,5,6,12的一棵最优二元树47345611356125612734122022/12/148911.7

树73456111812734561118122022/12/149011.7

树定义11.7.6

设是长为n的字符串，称为的长度为k的前缀.设为一符号串的集合,若对和互不为前缀,

则称A为前缀码；若中只出现0,1这两个符号,则称A为二元前缀码例11.7.4{010,011,11,10}是前缀码,{010，111，11，01}不是前缀码2022/12/149111.7

树例11.7.6

假设某系统的通信中使用5个字符A,B,C,D和E,其出现频率分别为0.08,0.12,0.20,0.28和0.32.试设计一个最佳前缀码,使通信中出现的二进制数字尽可能的少2022/12/1492习题习题11.679习题11.713452022/12/1493习题习题8.23

I上的二元运算*定义为：试证是群证(1)封闭性：

(2)

结合律：

(3)单位元：2(4)逆元：2022/12/1494习题习题8.26.试证单位元为群中唯一的幂等元证显然单位元是一个幂等元,即有e2=e

若有,则有即有

10.试求中所有的子群解所求的子群为

2022/12/1495习题11.试证:除单位元外的元素的阶都是2的群是交换群证由a2=e知于是对由和知

2022/12/1496习题习题8.33.设是群,令试证证由知由得2022/12/1497习题习题8.37.

设G是群,

作证明:f是G的自同构当且仅当G是交换群.

证必要性若f是G的自同构,

充分性:若G是交换群,

易知f是G的自同构

2022/12/1498习题习题8.43.试求出8阶循环群(a)的所有生成元和所有子群解生成元为a,a3,a5,a7

所有子群为

(a),(a2),(a4),(e)

2022/12/1499习题习题8.4

6

设G是循环群,试证也是循环群证设G的生成元为a,同态映射为f

下面证明是由f(a)所生成的循环群对所以是由f(a)所生成的循环群习题8.65证明:指数为2的子群必为正规子群证设H为G之指数为2的子群.

2022/12/14100习题习题8.52考虑n次对称群Sn,H是所有保持1不变的n阶置换构成的置换群,求

H在Sn中的所有左陪集解由|H|=(n-1)!知,H在Sn中的左陪集共有n个,其为

H和

4设H和K是群G的有限子群,且|H|与|K|互质.试证：证由是H和K的子群知,整除|H|和|K|

2022/12/14101习题习题8.61

求出4次交代群A4中的左、右陪集,

并验证H是A4的不变子群解H的左陪基为由上面可知,对所以H是A4的不变子群2022/12/14102习题习题11.11.证明在n个顶点的简单图中,至少有两个顶点的度数相等.

证分两种情况讨论:(1)有度为n-1的顶点这时n个顶点的度取值范围为{1,2,…,n-1},故必有两个顶点的度相同.(2)没有度为n-1的顶点这时n个顶点的度取值范围为{0,1,…,n-2},故必有两个顶点的度相同.2022/12/14103习题2.设无向图|E|=12.已知有6个3度顶点,其他顶点的度均小于3,问G中至少有多少个顶点?

解设G有n个顶点,则有

3.证明:

2022/12/14104习题习题11.23.

证明令为G中最长的基本通路,

则v1与邻接.故是一基本回路.

若有则C中有度大于或等于3的顶点不可.所以C包含G之所有的顶点,

即G=C.2022/12/14105课堂习题5.

设为无向简单图，证明：若则G是连通图.

证用反证法.

若G不连通，则G可以分为两个不连通的子图G1和G2，设其顶点数分别为n1和n2，则有与假设矛盾.2022/12/14106习题例判断彼得森图是否平面图2022/12/14107习题11.43

判断下图是否哈密尔顿图2022/12/14108习题例判断下图是否哈密尔顿图2022/12/14109习题11.6

1.

设是连通的简单平面图，面数为k，证明：证因为G是简单图,G的每个面的边界至少由三条边所组成,故各个面的边界上的总边数大于或等于3k

又因为每条边至多在两个面的边界上，所以各个面的边界上的总边数小于或等于2m，因此有2022/12/14110习题代入欧拉公式得：

3.

设G是顶点数的简单图.证明：G或为非平面图。证用反证法。若G和均为平面图，设他们分别有m1和m2

条边，则有

m1+m2=n(n-1)/22022/12/14111习题由和知即但当时，矛盾。2022/12/14112习题4.

设G是边数m小于30的简单平面图.证明：G中存在顶点v,

证

用反证法。若每个顶点的都大于或等于5，则有