第10章 图
(2)从a到d的基本路2条：ad，abd。从a到d的简单路5条：ad，abd，adcbd，adead，adeabd。 (3)基本回路共3个abdea，adea，bdcb.简单回路共4个：abdea，adea，bdcb，adcbdea。 15.(1)若无向图G中只有两个奇数度结点，则这两个结点一定是连通的。 (2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗？
证明 (1)设无向图G中只有两个奇数度结点u和v。从u开始构造一条回路，即从u出发经关联结点
u的边e1到达结点u1，若d(u1)为偶数，则必可由u1再经关联u1的边e2到达结点u2，如此继续下去，每条
边只取一次，直到另一个奇数度结点为止，由于图G中只有两个奇数度结点，故该结点或是u或是v。如果是v，那么从u到v的一条路就构造好了。如果仍是u，该回路上每个结点都关联偶数条边，而d(u)是奇数，所以至少还有一条边关联结点u的边不在该回路上。继续从u出发，沿着该边到达另一个结点u1?，依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点v，这就是一条从u到v的路。
(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达不一定成立。下面有向图中，只有两个奇数度结点u和v，u和v之间都不可达。
16.若无向图G是不连通的，证明G的补图G是连通的。
证明 设无向图G是不连通的，其k个连通分支为G1、G2、?、Gk。任取结点u、v∈G，若u和v不在图G的同一个连通分支中，则[u，v]不是图G的边，因而[u，v]是图G的边；若u和v在图G的同一个连通分支中，不妨设其在连通分支Gi（1≤i≤k）中，在不同于Gi的另一连通分支上取一结点w，则[u，w]和[w，v]都不是图G的边，，因而[u，w]和[w，v]都是G的边。综上可知，不管那种情况，u和v都是可达的。由u和v的任意性可知，G是连通的。
17.完成定理10.11的证明。
证明 充分性：若连通图G中存在结点u和w，使得连接u和w的每条路都经过e，则在子图G－{e}中u和w必不可达，故e是G的割边。
必要性：若e是G的割边，则G－{e}至少有两个连通分支G1＝
uwve，即u和w之间的任意路必经过e。
18.完成定理10.16的证明。
证明 先证任一结点至少位于一个单向分图中。
任给一结点v，若v是孤立结点，则含v的平凡图即为单向分图。若v不是孤立结点，则必有一个结点u，使得u与v有一弧e与它们联结。此时若有单向分图G1??V1,E1?，|V1|≥3，使u，v∈V1，且e∈E1，那么结论成立；若不存在这样的G1，则由u，v和e就构成一个单向分图。因此，任何结点至少位于一个单向分图中。
其次证明，任何一条弧至少位于一个单向分图中。
5
第10章 图
任给一弧e，其关联的结点u和v。若存在一单向分图G1??V1,E1?，|V1|≥3，使u，v∈V1，且e∈E1，那么结论成立。否则，u，v和e就构成一个单向分图。综上可知，任一弧至少位于一个单向分图中。
19.完成定理10.17的证明。
证明 显然任一结点和任一弧都位于一个弱分图中。
假设有一结点v位于两个不同的弱分图G1??V1,E1?和G2??V2,E2?中，即v∈V1∩V2。由于略去弧的方向后，V1中所有结点与v可达，V2中所有结点也与v可达，故V1与V2中所有结点可达，这与
G1和G2为弱分图矛盾，故任一结点不可能包含于不同的弱分图中，即任一结点能且只能位于一个弱分图
中。
假设一弧e位于两个不同的弱分图中，该弧e所关联的两个结点也位于两个不同的弱分图中，这是不可能的，因此任一弧也只能位于一个弱分图中。
20.给出3个4阶有向简单图D1、D2、D3，使得D1为强连通图；D2为单向连通图但不是强连通图；D3是弱连通图但不是单向连通图，当然更不是强连通图。
解
（a） （b） （c）图中得（a）为强连通图；（b）为单向连通图但不是强连通图；（c）是弱连通图但不是单向连通图，当然更不是强连通图。
21.一个有向图D是单向连通图，当且仅当它有一条经过每一个结点的路。 证明 充分性。
给定有向图D＝
v2，?，vn?1，vn}，E＝{e1，e2，?，en?1}?E，边ei（1≤i≤n－1）以vi为起点，以vi?1为终点。任给
两个结点vl、vm∈V，不妨设l＜m，则vlelvl?1?em?1vm就是从结点vl到vm的路，故D是单向连通的。
必要性。
对结点数v进行归纳。
当v＝1或2时，单向连通图显然有一条经过每一个结点的路。
设v＝k时，有一条经过每一个结点的路v1v2?vp，其中结点可能有重复，这条路的下标只表示该路所经过结点的次序，显然k≤p。
当v＝k＋1时，取一结点u，在图中删去结点u，使D－{u}还是单向连通图。根据归纳假设，D－{u}有一条经过每一个结点的路v1v2?vp。令i＝max{s|vs到u有路}，j＝min{s|u到vs有路}。假如j＞
6
第10章 图
i＋1，则必有t满足i＜t＜j。由于图D是单向连通的，vt与u之间必有路。如果该路是从vt到u，则与i＝max{s|vs到u有路}矛盾。如果该路是从u到vt，则与j＝min{s|u到vs有路}矛盾。故而j＞i＋1不可能，只能是j≤i＋1。当j＝i＋1时，有经过每个结点的路v1v2?vi?u?vi?1vi?2?vp。当j≤i时，有经过每个结点的路v1v2?vj?vi?u?vj?vivi?1?vp。
22.设e为图G＝
若e不是Gi的割边，则Gi－e仍然连通，因而G的连通分支数不变，即
?(G)＝?(G－e) （1）
若e是Gi的割边，则Gi－e有且仅有两个连通分支，因而G－e比G多一个支连通分支，即
?(G)＋1＝?(G－e) （2）
由（1）和（2）可得?(G)≤?(G－e)≤?(G)＋1。
23.设G是n阶无向简单图，有m条边，p个连通分支，证明n－p≤m≤(n－p)(n－p＋1)/2。 证明 （1）首先证明n－p≤m。对边数m做归纳法。m＝0时，G为零图，p＝n，n－p＝0，此时结论显然成立。
设m＜k（k≥1）时结论成立，要证m≥3时结论成立。在G中找一个边割集，不妨设这个边割集中的边为e1，e2，?，el（l≥1），设G1＝G－{e1，e2，?，el}，则G1的连通分支数为p＋1，边数为m1＝m－l（l≥1），由归纳假设得n－（p＋1）≤m－l＝m－1，于是n－p≤m。
（2）再证m≤(n－p)(n－p＋1)/2。为证明此不等式，不妨设G的各连通分支都是完全图，因为在这种情况下边数最多。而在l－1个连通分支都是完全图的情况下，又以p－1个为K1（平面图），一个n－p＋1阶完全图Kn?p?1时边数最多，此时的边数为(n－p)(n－p＋1)/2。为此只需证明下面事实：设Kni和
Knj是G的两个连通分支（ni≥nj≥1）。用Kni?1和Knj?1分别代替Kni和Knj，所得图的结点数和连通分
支数没变，但边数增加了。证明如下：
(
1111ni(ni＋1)＋(nj－1)(nj－2))－(ni(ni－1)＋nj(nj－1))＝ni－nj＋1＞0 2222综上所述就证明了结论。
24.设G＝
证明 必要性。设G是强连通的，此时若从S到V－S没有有向边，则S中的任一结点u到V－S中的任一结点v均没有有向路，从而与G是强连通的矛盾。所以从S到V－S至少有一条有向边。故G是1边连通的。
充分性。设G是1边连通的。任意u、v∈V，{u}到V－{u}至少有一条边，设为uu1，而{u，u1}到V－{u，u1}至少有一条边uu2或u1u2。无论那种情况都有从u到u2的有向路。因G中结点有限，所以通过如
7
第10章 图
上递归地求解，一定有u到v的有向路。故G是强连通的。
25.证明在n个结点的连通图G中，至少有n－1条边。
证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。
设G中结点为v1、v2、?、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、?、vn中必存在与v1或v2相邻的结点，不妨设为
v3，将其连接得边e2，续行此法，vn必与v1、v2、?、vn?1中的某个结点相邻，得新边en?1，由此可见
G
中至少有n－1条边。
26.试给出|V|＝n，|E|＝(n－1)(n－2)的简单无向图G＝
27.一个n阶连通图G最少有几个割点？最多有几个割点？
解 一个n阶连通图G为树时割点最少，只有一个；为完全图时割点最多，有n－1个。 28.求完全图Kn中任两点之间长为k的路的数目。
解 设E为元素全为1的n阶矩阵，I为阶单位矩阵，于是Kn的邻接矩阵为A＝E－I。Kn中长度为k的路的数目由决定Ak。
由于A＝(E－I)＝
k
12k
?i?0kE(?I)k?iiCk＝(?1)I?Ek?i?1k1i＝(?1)kI?[(n?1)k?(?1)k]E (?1)k?ini?1Ckn(k)所以，aij1?(?1)k?[(n?1)k?(?1)k]i?j??n??。 1kk?[(n?1)?(?1)]i?j?n?29.有向图D如图10-51所示： (1)求D的邻接矩阵A。
(2)D中v1到v4长度为4的路有多少？ (3)D中v1到自身长度为3的回路有多少？ (4)D中长度为4的路数为多少？其中有几条回路？ (5)D中长度小于等于4的路有多少？其中有多少条回路？ (6)D是哪类连通图？
解 (1) 求D的邻接矩阵为：
?1??0A??0??0?210??010?
001??010?? 8