第10章 图
图中。
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）为强连
（a） （b） （c）通图；（b）为单向连通
图但不是强连通图；（c）是弱连通图但不是单向连通图，当然更不是强连通图。
21.一个有向图D是单向连通图，当且仅当它有一条经过每一个结点的路。 证明 充分性。
给定有向图D＝
，?，vn?1，vn}，E＝{e1，e2，?，en?1}?E，边ei（1≤i≤n－1）以vi为起点，以vi?1为终点。任给
elvl?1两个结点vl、vm∈V，不妨设l＜m，则vl必要性。
对结点数v进行归纳。
?em?1vm就是从结点vl到vm的路，故D是单向连通的。
当v＝1或2时，单向连通图显然有一条经过每一个结点的路。 设v＝k时，有一条经过每一个结点的路v1所经过结点的次序，显然k≤p。
当v＝k＋1时，取一结点u，在图中删去结点u，使D－{u}还是单向连通图。根据归纳假设，D－{u}有一条经过每一个结点的路v1i＋1，则必有tv2v2?vp，其中结点可能有重复，这条路的下标只表示该路
?vp。令i＝max{s|vs到u有路}，j＝min{s|u到vs有路}。假如j＞
满足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时，有
6
第10章 图
经过每个结点的路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。为此只需证明下面事实：设Kn和Knji是G的两个连通分支（ni≥nj≥1）。用Kn?1和Knj?1分别代替Kn和Knj，所得图的结点数和连通分支数
ii没变，但边数增加了。证明如下：
(
12ni(ni＋1)＋(nj－1)(nj－2))－(
2112ni(ni－1)＋
12nj(nj－1))＝ni－nj＋1＞0
综上所述就证明了结论。
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中结点有限，所以通过如上递归地求解，一定有u到v的有向路。故G是强连通的。
25.证明在n个结点的连通图G中，至少有n－1条边。
证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。
设G中结点为v1、v2、?、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），
7
第10章 图
连接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＝
21解 下图满足条件但不连通。
27.一个n阶连通图G最少有几个割点？最多有几个割点？
解 一个n阶连通图G为树时割点最少，只有一个；为完全图时割点最多，有n－1个。 28.求完全图Kn中任两点之间长为k的路的数目。
解 设E为元素全为1的n阶矩阵，I为阶单位矩阵，于是Kn的邻接矩阵为A＝E－I。Kn中长度为k的路的数目由决定Ak。
由于A＝(E－I)＝?E(?I)kk
kk?iiCkk＝(?1)kI?E?i?1(?1)k?ini?1Cki＝(?1)kI?1n[(n?1)?(?1)]Ekk
i?0所以，aij(k)1?kkk(?1)?[(n?1)?(?1)]??n??1kk?[(n?1)?(?1)]?n?i?ji?j。
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?200011010??0??1?0??
且有
?1??0??0??0?200030101??1??0?01???1??03A??0??0?200041013??1??0??04A? ??10???00???200060104??1??0?1??A2
8
第10章 图
(4)(2)由A4中a14?4可知，D中v1到v4长度为4的路有4条，分别为：e1e1e4e6、e4e6e7e6、e1e2e5e6、
e1e3e5e6。
?1可知，D中v1到自身长度为3的回路只有1条，为e1e1e144(3)(3)由A3中a11。
(4)(4)D中长度为4的路总数为??aiji?1j?1?16，其中对角元素之和为3，说明长度为4的回路为3条。
(5)D中长度小于等于4的路总数为A、A2、A3、A4中全体元素之和：7＋10＋13＋16＝46，其中回路数为：1＋3＋1＋3＝8。
?4??0??0??0?8000142228??2??2?2??(6)由B4?A?A?A?A234可知，D是单向连通图。
30.有向图G如图10-52所示，试求： (1)求G的邻接矩阵A。
(2)求出A2、A3和A4，v1到v4长度为1、2、3和4的路有多少？
(3)求出ATA和AAT，说明ATA和AAT中的第(2，2)元素和第(2，3)元素的意义。 (4)求出可达矩阵P。 (5)求出强分图。
解 (1)求G的邻接矩阵为：
?0??0A??0??0?101101001??1??1?0??v4v1v3v2图10-52
(2)由于
?0??0??0??0?121010111??1??1?1???0??03A??0??0?212212102??2??2?1???0??0??0??0?343121223??3??3?2??A2 A4
所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。 (3)由于
?0??0TAA??0??0?030201110??2??2??1T? AA??12???13???121021221??0?? 1?1??再由定理10.19可知，所以ATA的第(2，2)元素为3，表明那些边以v2为终结点且具有不同始结点的
9
第10章 图
数目为3，其第(2，3)元素为0，表明那些边既以v2为终结点又以v3为终结点，并且具有相同始结点的数目为0。AAT中的第(2，2)元素为2，表明那些边以v2为始结点且具有不同终结点的数目为2，其第(2，3)元素为1，表明那些边既以v2为始结点又以v3为始结点，并且具有相同终结点的数目为1。
?0??0??0??0?101101001??1??1?0???0?0+??0??0?121010111??1??1?1???0?0+??0??0?212212102??2??2?1???0?0+??0??0?343121223??0??3??0???30???02???777444431??7??7?4??(4)因为B4?A?A?A?A234，所以
求可达矩阵为
?0??0P??0??0?111??111??。 111?111???0??0??0??0?111111111??0??1??1?∧?11???11???011101110??1??1?1???0?0＝??0??0?011101110??1??1?1??(5)因为P?PT，所以{v1}，{v2，v3，v4}构成G的强分图。
31.画一个无向欧拉图，使它具有： (1)偶数个顶点，偶数条边。 (2)奇数个顶点，奇数条边。 (3)偶数个顶点，奇数条边。 (4)奇数个顶点，偶数条边。
解 (1)n（n为偶数，且n≥2）阶圈都是偶数个顶点，偶数条边的无向欧拉图。 (2)n（n为奇数，且n≥1）阶圈都是奇数个顶点，奇数条边的无向欧拉图。
(3)在(1)中的圈上任选一个顶点，在此顶点处加一个环，所得图为偶数个顶点，奇数条边无向欧拉图。 (4)在(3)中的圈上任选一个顶点，在此顶点处加一个环，所得图为奇数个顶点，偶数条边无向欧拉图。 32.画一个无向图，使它是： (1)既是欧拉图，又是哈密尔顿图。 (2)是欧拉图，但不是哈密尔顿图。 (3)是哈密尔顿图，但不是欧拉图。 (4)既不是欧拉图，也不是哈密尔顿图。
解 (1)n（n≥3）阶圈，它们都是欧拉图，又是哈密尔顿图。
(2)给定k（k≥2）个长度大于等于3的初级回路，即圈C1，C2?，Ck。将C1中某个顶点和C2中的某个顶点重合，但边不重合，C2中某个顶点和C3中的某个顶点重合，但边不重合，续行此法，直到将Ck?1中某个顶点和Ck中的某个顶点重合，但边不重合，设最后得到的连通图为G，则G是欧拉图，但不是哈密尔顿图。
(3)在n（n≥4）阶圈中，找两个不相邻的顶点，在它们之间加一条边，所得图是哈密尔顿图，但不是欧拉图。
10