哈工大图论习题

《哈工大图论习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章习题1．画出具有4个顶点的所有无向图(同构的只算一个)。2．画出具有3个顶点的所有有向图(同构的只算一个)。3．画出具有4个、6个、8个顶点的三次图。4．某次宴会上，许多人互相握手。证明：握过奇数次手的人数为偶数(注意，0是偶数)。5．证明：哥尼斯堡七桥问题无解。6．设u与v是图G的两个不同顶点。若u与v间有两条不同的通道(迹)，则G中是否有回路？7．证明：一个连通的(p，q)图中q≥p-1。8．设G是一个(p，q)图，δ(G)≥[p/2]，试证G是连通的。9．证明：在一个连通图中，两条最长的路有一个公共的顶点。10．在一个有n个人的宴会上，每个人至少

2、有m个朋友(2≤m≤n)。试证：有不少于m+1个人，使得他们按某种方法坐在一张圆桌旁，每人的左、右均是他的朋友。11．一个图G是连通的，当且仅当将V划分成两个非空子集V1和V2时，G总有一条联结V1的一个顶点与V2的一个顶点的边。12．设G是图。证明：若δ(G)≥2，则G包含长至少是δ(G)+1的回路。13．设G是一个(p，q)图，证明：(a)q≥p，则G中有回路；(b)若q≥p+4，则G包含两个边不重的回路。14．证明：若图G不是连通图，则Gc是连通图。15．设G是个(p，q)图，试证：(a)δ(G)·δ(GC)≤[(p-1)/2]([(p+1)/2]+1

3、)，若p≡0，1，2(mod4)(b)δ(G)·δ(GC)≤[(p-3)/2]·[(p+1)/2]，若p≡3(mod4)16．证明：每一个自补图有4n或4n+1个顶点。17．构造一个有2n个顶点而没有三角形的三次图，其中n≥3。18.给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有degu+degv≥919．试求Kp中不同的哈密顿回路的个数。20．试证：图四中的图不是哈密顿图。21．完全偶图Km，n为哈密顿图的充分必要条件是什么？22．菱形12面体的表面上有无哈密顿回路？23．设G是一个p(p≥3)个顶点的图。u和v是G的两个不邻接的

4、顶点，并且degu+degv≥p。证明：G是哈密顿图当且仅当G+uv是哈密顿图。24．设G是一个有p个顶点的图。证明：若p>2δ(G)，则有长至少为2δ(G)的路。25．证明具有奇数顶点的偶图不是哈密顿图。26．证明：若p为奇数，则Kp中有(p-1)/2个两两无公共边的哈密顿回路。28．中国邮路问题：一个邮递员从邮局出发投递信件，然后返回邮局。若他必须至少一次走过他所管辖范围内的每条街道，那么如何选择投递路线，以便走尽可能少的路程。这个问题是我国数学家管梅谷于1962年首先提出的，国外称之为中国邮路问题。(1)试将中国邮路问题用图论述语描述出来。(2)中国邮

5、路问题、欧拉图问题及最短路问题之间有何联系。5/5第二章习题1．画出具有4个顶点的所有无向图(同构的只算一个)。2．画出具有3个顶点的所有有向图(同构的只算一个)。3．画出具有4个、6个、8个顶点的三次图。4．某次宴会上，许多人互相握手。证明：握过奇数次手的人数为偶数(注意，0是偶数)。5．证明：哥尼斯堡七桥问题无解。6．设u与v是图G的两个不同顶点。若u与v间有两条不同的通道(迹)，则G中是否有回路？7．证明：一个连通的(p，q)图中q≥p-1。8．设G是一个(p，q)图，δ(G)≥[p/2]，试证G是连通的。9．证明：在一个连通图中，两条最长的路有一个公

6、共的顶点。10．在一个有n个人的宴会上，每个人至少有m个朋友(2≤m≤n)。试证：有不少于m+1个人，使得他们按某种方法坐在一张圆桌旁，每人的左、右均是他的朋友。11．一个图G是连通的，当且仅当将V划分成两个非空子集V1和V2时，G总有一条联结V1的一个顶点与V2的一个顶点的边。12．设G是图。证明：若δ(G)≥2，则G包含长至少是δ(G)+1的回路。13．设G是一个(p，q)图，证明：(a)q≥p，则G中有回路；(b)若q≥p+4，则G包含两个边不重的回路。14．证明：若图G不是连通图，则Gc是连通图。15．设G是个(p，q)图，试证：(a)δ(G)·δ(

7、GC)≤[(p-1)/2]([(p+1)/2]+1)，若p≡0，1，2(mod4)(b)δ(G)·δ(GC)≤[(p-3)/2]·[(p+1)/2]，若p≡3(mod4)16．证明：每一个自补图有4n或4n+1个顶点。17．构造一个有2n个顶点而没有三角形的三次图，其中n≥3。18．在图1.4.5中，一只车从位置A出发，在半张棋盘上走，每步走一格，走了若干步后到了位置B。证明：至少有一个格点，没有车走过，或被走过不至一次。19.给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有degu+degv≥920．试求Kp中不同的哈密顿回路的个数

8、。21．完全偶图Km，n为哈密顿图的充分必要条件是什