4.6 试证明端数n大于4的连接图都是非平面图，并求n=2，3，4的全连接图为对偶图。 证明：设有n个端的全联接图为Kn因为K5是非平面图，而当n>5时K5是Kn的子图，从而Kn（n>5）均不是平面图。一下是对偶图（注意K4为自对偶图）。
第 16 页 共 33 页
4.7
?0?0C???0??0
100001001?0?? 1??0?
已知一个图的邻接矩阵如左，画出此图，并求各端之间的最小有向径长。
解：首先作出图形：
对所绘制图形的端点进行编号，得邻接矩阵。
v1
经计算：
??C?????
v2v3v41010?0010?
?0001??0000??0?0C2???0??0因而有
000010000??0?01?? C3??0??0??0??0000000001?0?? 0??0?第 17 页 共 33 页
d(v1,v2)?1
d(v1,v3)?2 d(v2,v4)?2
d(v1,v4)?1
d(v2,v3)?1 d(v3,v4)?1
其余有向径长均为 ∞，或不存在。
4.8 图有六个端，其无向距离矩阵如下：
v1v1v2v3v4v5v6
v2?0?1??2??3?2??1v3120110v4v5v6321?232??123??21012?32101??23120?1. 2. 3.
用P算法，求出最短树。 用K算法，求出最短树。
限制条件为两端间通信的转接次数不超过2的最短树。
解：
(1)P算法求解：
eeee?v1?????v1,v2?????v1,v2,v3?????v1,v2,v3,v6?????v1,v2,v3,v6,v5?
e????v1,v2,v3,v6,v5,v4?1223166534(2)K算法求解：
按最小边长顺序取得： e12?e23?e34?e45?e56?1此结果意味着最短树不唯一。
第 18 页 共 33 页
(3)原图有一个边长全为1的基本子图G1，要求转接次数小于等于2，若选取G1的任何4个连续顶点，vivi?1vi?2vi?3,作为基础，然后再按要求增加边，例如以v1v2v3v4为基础，增加v5v6，得到一个树长为7转接次数小于等于2的树T1，事实上，以任何4个连续顶点均可得到树长为7的转接次数小于等于2的树
4.9 图有六个端，端点之间的有向距离矩阵如下：
v1v2v3v4v5v6 解：
v1v2?09?10??2???????6??7?v3v4v5v613???4?7???0?1???5027?2805??2?20?(1)用D算法求V1到所有其他端的最短径长及其路径。 (2)用F算法求最短径矩阵和路由矩阵，并找到V2至V4和V1至V5的最短径长及路由。 (3)求图的中心和中点。
第 19 页 共 33 页
(1)D算法
V1 0
(2)F算法
最短路径矩阵及最短路由阵为W5，R5
V2 ∞ 9 9 8 8 8
V3 ∞ 1
V4 ∞ 3 3 3
V5 ∞ ∞ 2
V6 ∞ ∞ ∞ 7 7
指定 V1 V3 V5 V4 V6 V2
最短径长 W1＝0 W13＝1 W15＝2 W14＝3 W16＝7 W12＝8
v2?v1?v4有向距离为4
v1?v3?v5有向距离为2
第 20 页 共 33 页