7.2第168页
1．画出K4的所有不同的子图，并说明其中哪些是生成子图，找出互为补图的生成子图。 解：
(1)(2)(3)
（4）
(5)(6)(7)
其中，（1）和（7），（2）和（6），（3）和（5），（4）中的后两个图可以构成互补的生产子图。
2．设G??V,E,??是完全有向图。证明：对于V的任意非空子集V?，
G[V?]是完全有向图。
证明：（1）当V?中只有一个结点时，G[V?]是完全有向图。
（2）当V?中有多于一个结点时，对其中任意两个结点Vi,Vj是V的子集，即Vi,Vj?V。因为图G是完全有向图，因此Vi,Vj间存在两条有向边eij和eji。G[V?]是由非空子集V?生成的子图，故eij,eji?G[V?]，即
G[V?]中任意两个结点间存在两条有向边，故G[V?]是完全有向图。
3．画出图7-15的两个图的交、并和环和。
v1e1v2e2v3e3e6e4e7v4e5v5v2v3e6e8e1e3v1v4a)b)
解：
交： 并：
v1v1e3e6e1v2e2e3e6e4e5v5e7v4e1v2v3v4
v3
环和：
v1e5v2e2v3e8v4e4e7v5
4．设G是任意6阶简单无向图，证明：G或G必有一个子图是3阶无向图。
证明：取G或G任意取三个点，取与这三个点相关联的变构成一个3阶的无向子图。
5．我们称与补图同构的简单无向图为自补图。证明：每个自补图的阶能够被4整除或被4整除余数为1。
n(n?1),由自补图的定义知该2n(n?1)图与其子图的边数相同（同构），故其边数为，由该数是整数
4n(n?1)得：?k，n?4korn?4k?1。故每个自补图的阶能够被4整除或
4证明：设图的顶点数为n，Kn的边数为
被4整除余数为1。
7.3第173页
1．考虑图7-21
（1）从A至F的路径有多少条？找出所有长度小于6的从A至F的路径。
解：A到F的路径有无数条。长度小于6的有24条。（c f h:4,c g h:4, c e i:4, b d e f h:2, b d e g h:2, b d i:4） （2）找出从A至F的所有简单路径。
解：12条。(c f h, c g h, c e I, b d e f h, b d e g h, b d i),还有一个自环，需乘以2.
（3）找出从A至F的所有基本路径。
解：6条。(c f h, c g h, c e I, b d e f h, b d e g h, b d i) （4）求出从A至F的距离。求出该图的直径。 解：距离为3。直径为3。 （5）找出该图的所有回路。
解：AaA, AbDdEeBcA, BeEiFhCgB; BgCfB; AbDdEiFhCgBcA;
BeEiFhCfB;
2．证明：图7-21中基本路径必为简单路径。
证明：基本路径要求途经的顶点不重复，简单路径要求途经的边不重复。在图7-21中，对于所有的基本路径，边不重复出现。所以基本路径必是简单路径。 3．考虑图7-22
（1）对于每个结点v，求R(v)。
解：R(v1)?R(v2)?R(v3)?R(v4)?{v1,v2,v3,v4,v5,v6}, R(v5)?{v5,v6},R(v6)?{v6},R(v7)?{v6,v7} R(v8)?{v6,v7,v8},R(v9)?{v9},R(v10)?{v10} （2）找出所有强分支、单向分支和弱分支。
解：强分支7个，分别是{v9},{v10},{v8},{v7},{v6},{v5},{v1,v2,v3,v4} 单项分支4个，分别是{v9},{v10},{v6,v7,v8},{v1,v2,v3,v4,v5,v6} 弱分支3个，分别是{v9},{v10},{v1,v2,v3,v4,v5,v6,v7,v8}
4．设v1v2v3是任意无向图（有向图）G的三个任意结点，以下三个公式是否成立？如果成立，给出证明；如果不成立，举出反例。 （1）d(v1,v2)?0，并且等号成立，当且仅当v1?v2。 解：成立。当v1?v2时，距离必定大于1。 （2）d(v1,v2)?d(v2,v1)
解：成立。因为无向图是无方向的。
5. 证明：有向图的每个结点和每条边恰处于一个弱分支中。 反证法：若任意结点V处于两个或两个以上的弱分支中，不妨设两个
弱分支为G1, G2, 则G1, G2是G的极大联通子图。设v?G1,v?G2，又G1,G2?G,故G1,G2联通。这与G1, G2是极大联通子图矛盾，故命题得证。
6. 有向图的每个结点（每条边）是否恰处于一个强分支中？是否恰处于一个单向分支中？
解：有向图中的每个结点处于一个强分支中，而边不一定。有向图的结点和边可能出现在两个单向分支中。图见书上（P141 图7-18） 7. 证明同阶的回路必同构。
证明：同阶表明两个图的顶点个数相同，设为V; 又联通二度正则图称为回路。即两个图的每个顶点的度数相同为2. 边数为2V/2 = V,相同。由于两个图的顶点数，边数相同，且每个顶点的度数均为2，故两个图同构。
?(v)?1,则G恰9. 设G是弱联通有向图，如果对于G的任意结点v, dG有一条有向回路。试给出证明。
证明：因为G是弱联通有向图，不妨设一条极大单向联通子图：
?(v)?1, 所以对Vk，?e??Vk,V?。若V?V1???Vk?1，则与极大联因为: dG通子图矛盾，故V必为V1???Vk?1之一。
又假设有两条以上的回路（反证法），不妨设有两条，则这两条回路上所有点的出度为1，而要使这两条回路联通，则至少其中有一个点
?(v)?1矛盾。故G恰有一条会向回路。 的出度大于1，这与dGV1V2Vk?1Vk
离散数学第二版(6-7章)
