图论试题浙师大

思考练习

第一章

1对任意图，证明。

证：，故。

2 在一次聚会有个人参加，其中任意6个人中必有3个人互相认识或有3个人互不认识。举例说明，将6个人改成5个人，结论不一定成立。

证：构图如下：图的顶点代表这6个人，两个顶点相邻当且仅当对应的两个人互相认识。则对于图中任意一个点或。不妨设及它的3个邻点为。若中有任意两个点，不妨设为，相邻，则对应的3个人互相认识；否则，中任意两个点不邻，

即它们对应的3个人互不认识。

若这5个人构成的图是5圈时，就没有3个人互相认识或有3个人互不认识。

3 给定图

画出下列几个子图:

(a) ；

(b);

(c)

解：(a)

(b)

(c)

第二章

1设是一个简单图，。证明：中存在长度至少是的路。

证：选取的一条最长路，则的所有邻点都在中，所以

，即中存在长度至少是的路。

2证明：阶简单图中每一对不相邻的顶点度数之和至少是，则是连通

图。

证：假设不连通，令、是的连通分支，对，有

，与题设矛盾。故连通。

3设是连通图的一个回路，，证明仍连通。

证：，中存在路，

1、若，则是中的路；

2、若，则是中的途径，从而中存在

路。

故连通。

4图的一条边称为是割边，若。证明的一条边是割边当且仅当不含在的任何回路上。

证：不妨设连通，否则只要考虑中含的连通分支即可。

必要性：假设在的某一回路上，则由习题2.13有连通，，

与是割边矛盾。故不在回路中。

充分性：假设不是割边，则仍连通，存在路，则就是含的一个回路，与不在回路中矛盾。故是割边。

5证明：若是连通图，则。

证：若是连通图，则。

第三章

1 证明：简单图是树当且仅当中存在一个顶点到中其余每个顶点有且

只有一条路。

证：必要性：由定理

充分性：首先可见连通。否则，设有两个连通分支、，且，则到中的顶点没有路，与题设矛盾。

其次，中无回路。否则，若有回路。由于连通，到上的点有路，