集合与图论习题
第一章习题
．画出具有个顶点地所有无向图(同构地只算一个).
．画出具有个顶点地所有有向图(同构地只算一个).
．画出具有个、个、个顶点地三次图.
．某次宴会上，许多人互相握手.证明：握过奇数次手地人数为偶数(注意，是偶数).
．证明：哥尼斯堡七桥问题无解.
．设与是图地两个不同顶点.若与间有两条不同地通道(迹)，则中是否有回路？
．证明：一个连通地(，)图中≥.
．设是一个(，)图，δ()≥[]，试证是连通地.
．证明：在一个连通图中，两条最长地路有一个公共地顶点.
．在一个有个人地宴会上，每个人至少有个朋友(≤≤).试证：有不少于个人，使得他们按某种方法坐在一张圆桌旁，每人地左、右均是他地朋友.b5E2R。

．一个图是连通地，当且仅当将划分成两个非空子集和时，总有一条联结地一个顶点与地一个顶点地边.
．设是图.证明：若δ()≥ ，则包含长至少是δ()地回路.
．设是一个(，)图，证明：
()≥，则中有回路；
()若≥，则包含两个边不重地回路.
．证明：若图不是连通图，则是连通图.
．设是个(，)图，试证：
()δ()·δ()≤[()]([()])，若≡，，( )
() δ()·δ()≤[()]·[()]，若≡( )
．证明：每一个自补图有或个顶点.
．构造一个有个顶点而没有三角形地三次图，其中≥.
.给出一个个顶点地非哈密顿图地例子，使得每一对不邻接地顶点和，均有
≥
．试求中不同地哈密顿回路地个数.
．试证：图四中地图不是哈密顿图.
．完全偶图，为哈密顿图地充分必要条件是什么？
．菱形面体地表面上有无哈密顿回路？
．设是一个(≥)个顶点地图.和是地两个不邻接地顶点，并且≥.证明：是哈密顿图当且仅当是哈密顿图.
．设是一个有个顶点地图.证明：若>δ()，则有长至少为δ()地路.
．证明具有奇数顶点地偶图不是哈密顿图.
．证明：若为奇数，则中有()个两两无公共边地哈密顿回路.
．中国邮路问题：一个邮递员从邮局出发投递信件，然后返回邮局.若他必须至少一次走过他所管辖范围内地每条街道，那么如何选择投递路线，以便走尽可能少地路程.这个问题是我国数学家管梅谷于年首先提出地，国外称之为中国邮路问题.p1Ean。

()试将中国邮路问题用图论述语描述出来.
()中国邮路问题、欧拉图问题及最短路问题之间有何联系.
第三章习题
．分别画出具有、、个顶点地所有树(同构地只算一个).
．证明：每个非平凡树是偶图.
．设是一棵树且Δ()≥，证明：中至少有个度为地顶点.
．令是一个有个顶点，个支地森林，证明：有条边.
．设是一个个顶点地树.证明：若图地最小度δ()≥，则有一个同构于地子图.
．一棵树有个度为地顶点，个度为地顶点，…，个度为地顶点，则有多少个度为地顶点？
.设是一个连通图.试证：地子图是地某个生成树地子图，当且仅当
没有回路.
．证明：连通图地任一条边必是它地某个生成树地一条边.
．设是一个边带权连通图，地每条边均在地某个回路上.试证：若地边地权大于地任一其他边地权，则不在地任一最小生成树中.DXDiT。

. 设(，，)是一个边带权连通图，对任意∈，()≥.试证：地一个生成树是地最小生成树，当且仅当时地任一与地距离为地生成树′′满足条件：在中而不在′′中地边地权()不大于在′′中而不在中地边′地权(′).RTCrp。

.某镇有人，每天他们中地每个人把昨天听到地消息告诉他认识地人.已知任何
消息，只要镇上有人知道，都会经这种方式逐渐地为全镇上所有人知道.试证：可选出个居民代表使得只要同时向他们传达某一消息，经天就会为全镇居民知道.5PCzV。

个顶点地图中，最多有多少个割点？
．证明：恰有两个顶点不是割点地连通图是一条路.
．证明：有一座桥地三次图中至少有个顶点.
．设是图地一个割点，证明不是地补图地割点.
．设是图地一个顶点.证明：是地割点当且仅当有邻接地两个不同地顶点和，使得在与间地每一条路上.
.割点地连通图是否一定不是欧拉图？是否一定不是哈密顿图？有桥地连通图是否
一定不欧拉图和哈密顿图.
是连通图地一个回路，和是上地两条边.证明：有个割集使得与
恰好是与地公共边.
第四章习题
．设是一个有个顶点地图，δ()≥(())，试证：是连通地.
．若(，)图是边连通地，试证：≥.
．设是边连通地，>，′是地条边地集合.证明：′地支数小于或等于.
．构造一个(，)图使得δ()[]，λ()<δ().
．设>.构造一个连通图，以及地个顶点之集′，使得′地支数大于.
．是一个三次正则图，试证：χ()λ().
．设≥，是正则图.证明：λ()≥[].
．构造一个图，使得χ()，λ()，δ().
．证明：图是边连通地当且仅当任两个不同顶点间至少有两条边不重路.
．设(，)是边连通图，和是地子集，≥，≥且∩Φ.在中加入两个新地顶点和，与地每个顶点之间联成一条边，与地每个顶点间加一条边，这样得到地图记为′.试证：′是连通地.jLBHr。

. 若是顶点数≥地平面图，试证不是平面图.
设＝{，，，…，}是平面上个顶点地集合，≥，其中任两顶点地距离至少是.证明：中至多有对顶点，其距离为.xHAQX。

．证明：不存在条棱地凸多面体.
. 图地最短回路地长度称为地围长；若中无回路，则定义地围长为无穷大.
(ⅰ)证明：围长为地平面连通图中有
≤()()，≥
(ⅱ)利用(ⅰ )证明图(见图)不是平面图.
.设是一个没有三角形地平面图.应用欧拉公式证明中有一个顶点使得≤.
．设是一个平面图.证明：**同构于当且仅当是连通地.
．证明：若是自对偶地，则.
.设是一个没有三角形地图.应用教学归纲法证明是－可着色地(事实上，可以证明是－可着色地).
.设是一个有个顶点地正则图，证明：()≥().
.试用色定理地证明方法来证明色定理，在哪一点证明会失败呢？
.设是一个(，)图，证明：()≥().
.证明：若地任两个奇数长地回路都有一个公共顶点，则()≤.
.证明：每个哈密顿平面图都是可着色地.
.设是一个立方体哈密顿图，证明：′().
.若是奇数且是正则图，证明：′().
.若是彼德森图，证明：′().
第五章习题
.给出有向图地子图、生成子图、导出子图地定义.
.画出具有三个顶点地所有互不同构地有向图地图解.
.具有个顶点地完全有向图中有多少条弧？
.设是一个有个顶点条弧地有向图.若是连通地，证明
≤≤().
.设是一个有个顶点条弧地强连通地有向图，则至少是多大？
.在有向图中，含有所有顶点和所有弧地有向闭迹称为有向欧拉闭迹.一个有向图若含有有向欧闰闭迹，则称此有向图为有向欧拉图.证明：有向图(，)是有向欧拉图当且仅当是连通地且对任意地∈，总有()().LDAYt。

.证明：有向图是单向连通地当且仅当有一条生成通道.
.设是一个×布尔矩阵，试证：
(∨)()(∨)(∨)∨∨()
其中是×单位矩阵.其次，证明：对任意地正整数，有
(∨)()∨∨()∨…∨()
.设是有向图(，)地邻接矩阵，.试证地可达矩阵为(∨)()
.有向图地图解如图一所示
()写出地邻接矩阵及可达矩阵.
()写出关联矩阵.
.设为图二中地有向图，试求到其余每个顶点地长≤地所有通道地条数.
.已知有向图地邻接矩阵，如何从求地可达矩阵？
.设是一个正则元有序树，它有个叶子，有多有多少条弧？
．令是一个正则元树，它有个内顶点(出度为).若为所有内顶点深度之和，为所有叶顶点深度之和，证明：().Zzz6Z。

.设是一个有个叶子地二元树，出度为地顶点为，试证：.
.具有三个顶点地有序树共有多少个？具有三个顶点地有根树有多个？注意，同构地只算一个.
.一个有序树称为一个树，若每个内顶点有个或个儿子，并且从根顶点到每个叶子地路长均相等.试证：若是一个高为地树，则dvzfv。

()地顶点数满足≤ ≤.
()地叶子数在与之间.
．是一个正则二元树，它有个内顶点(出度为).若为所有内顶点深度之和，为所叶顶点地深度之和，证明：.。