哈工大集合和图论习题.docVIP

集合与图论习题 第一章 习 题 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个人的宴会上，每个人至少有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)，若p≡0，1，2(mod 4) (b) δ(G)·δ(GC)≤[(p-3)/2]·[(p+1)/2]，若p≡3(mod 4) 16．证明：每一个自补图有4n或4n+1个顶点。 17．构造一个有2n个顶点而没有三角形的三次图，其中n≥3。 18.给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有 degu+degv≥9 19．试求Kp中不同的哈密顿回路的个数。 20．试证：图四中的图不是哈密顿图。 21．完全偶图Km，n为哈密顿图的充分必要条件是什么？ 22．菱形12面体的表面上有无哈密顿回路？ 23．设G是一个p(p≥3)个顶点的图。u和v是G的两个不邻接的顶点，并且degu+degv≥p。证明：G是哈密顿图当且仅当G+uv是哈密顿图。 24．设G是一个有p个顶点的图。证明：若p2δ(G)，则有长至少为2δ(G)的路。 25．证明具有奇数顶点的偶图不是哈密顿图。 26．证明：若p为奇数，则Kp中有(p-1)/2个两两无公共边的哈密顿回路。 28．中国邮路问题：一个邮递员从邮局出发投递信件，然后返回邮局。若他必须至少一次走过他所管辖范围内的每条街道，那么如何选择投递路线，以便走尽可能少的路程。这个问题是我国数学家管梅谷于1962年首先提出的，国外称之为中国邮路问题。 (1)试将中国邮路问题用图论述语描述出来。 (2)中国邮路问题、欧拉图问题及最短路问题之间有何联系。 第三章 习 题 1．分别画出具有4、5、6个顶点的所有树(同构的只算一个)。 2．证明：每个非平凡树是偶图。 3．设G是一棵树且Δ(G)≥k，证明：G中至少有k个度为1的顶点。 4．令G是一个有p个顶点，k个支的森林，证明：G有p-k条边。 5．设T是一个k+1个顶点的树。证明：若图G的最小度δ(G)≥k，则G有一个同构于T的子图。 6．一棵树T有n2个度为2的顶点，n3个度为3的顶点，…，nk个度为k的顶点，则T有多少个度为1的顶点？ 7.设G是一个连通图。试证：G的子图G1是G的某个生成树的子图，当且仅当G1 没有回路。 8．证明：连通图的任一条边必是它的某个生成树的一条边。 9．设G是一个边带权连通图，G的每条边均在G的某个回路上。试证：若G的边e的权大于G的任一其他边的权，则e不在G的任一最小生成树中。 10. 设G=(V，E，w)是一个边带权连通图，对任意x∈E，w(x)≥0。试证：G的一个生成树T是G的最小生成树，当且仅当时G的任一与T的距离为1的生成树T′′满足条件：在T中而不在T′′中的边e的权w(e)不大于在T′′中而不在T中的边e′的权w(e′)。 11.某镇有1000人，每天他们中的每个人把昨天听到的消息告诉他认识的人。已知任何 消息，只要镇上有人知道，都会经这种方式逐渐地为全镇上所有人知道。试证：可选出90个居民代表使得只要同时向他们传达某一消息，经10天就会为全镇居民知道。 12.P个顶点的图中，最多有多少个割点？ 13．证明：恰有两个顶点不是割点的连通图是一条路。 14．证明：有一座桥的三次图中至少有10个顶点。 15．设v是图G的一个割点，证明v不是G的补图Gc的割点。 16．设v是图G的一个顶点。证明：v是G的割点当且仅当有邻接v的两个不同的顶点u和w，使得v在u与w间的每一条路上。