2013四川师范大学 图论期末考试复习题

2013四川师范大学 图论考试复习题

关于图论中的图，以下叙述不正确的是

A．图中点表示研究对象，边或有向边表示研究对象之间的特定关系。 B．图论中的图，画边时长短曲直无所谓。

C．图中的边表示研究对象，点表示研究对象之间的特定关系。

D．图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系。

一个图中最长的边一定不包含在最优生成树内。

下面哪个图形不与完全二分图K3,3同构？ A． B． C． D．

有10条边的5顶单图必与K5同构。

完全二分图Km,n的边数是 A．m B．n C．m?n D．mn

无向完全图Kn的边数为 A．n B．n2 C．n(n?1) D．n(n?1)/2

若一个无向图有5个顶点，如果它的补图是连通图，那么这个无向图最多有 条边。

对于两个图，如果顶点数目相等，边数相等，次数相等的顶点数目也相等，则这两个图同构。

有15个顶的单图的边数最多是 A．105 B．210 C．21 D．45

图G如右，则dacbeb

A．是G中的一条道路 baB．是G中的一条道路但不是行迹

gef C．是G中的一条行迹但不是轨道

dcD．不是G的一条道路

图G如右，则befcdef A．是G的一个圈 baB．是G的一条道路但不是行迹

gefC．是G的一条行迹但不是轨道

dcD．是G的一条轨道但不是圈

图G如右图所示，则??(G)?

A．1 B．2

C．7 D．8

下列图形中与其补图同构的是 A． B． C． D．

求下图中顶u0到其余各顶点的最短轨长度。

u0v1=8，u0v2=1，u0v3=4，u0v4=2，u0v5=7，v1v2=7，v1v3=2，v1v6=4，v2v4=2，v2v7=3，v3v5=3，v3v6=6，v4v5=5，v4v7=1，v5v6=4，v5v7=3，v6v7=6，

v2v42

7121 3758v1v7 u0v533446请画出6阶3正则图。 24 v3v66

请画出4个顶，3条边的所有非同构的无向简单图。

设图G={V(G)，E(G)}其中V={a1, a2, a3, a4, a5}，E(G)={(a1, a2)，(a2, a4)，(a3, a1)，(a4, a5)，(a5, a2)}，试给出G的图形表示并画出其补图的图形。

一个图的生成子图必是唯一的。

不同构的有2条边，4个顶的无向简单图的个数为 A．1 B．2 C．3 D．4

画出5个具有5个结点5条边的非同构的无向连通简单图。

u0到v1的最短轨长度为6，u0到v2的最短轨长度为1，u0到v3的最短轨长度为4，u0到v4的最短轨长度为2，u0到v5的最短轨长度为6，u0到v6的最短轨长度为9，u0到v7的最短轨长度为3。

用Dijkstra算法求下图中从v1点到其他任意一点的最短路。

v21v5v1v3

209109v1v2

13v3v7v1v2v5 v14v1v3v4 15843v1v2v5v6 v37v6v1v2v5v6v7

设有城市v1，v2，v3，v4，v5，v6，各城市之间的距离如下表。使用Dijkstra算法求城市v1到其他各城市的最短路径以及最短距离。要求说明求解过程（提示：应将城市之间的道路图看作是无向图）。 道路 距离 步骤 v1v2 1 v1 0 v1v3 4 v2 1/(v1) ①/(v1) v2v3 2 v2v4 7 v3 4/(v1) 3/(v2) ③/(v2) v2v5 5 v4 ∞ 8/(v2) 8/(v2) 7/(v5) ⑦/(v5) v3v5 1 v4v5 3 v5 ∞ 6/(v2) 4/(v3) ④/(v3) v4v6 2 v6 ∞ ∞ ∞ 10/(v5) 9/(v4) ⑨/(v4) v5v6 6 解：下面的表格给出了求解v1到其他各顶点之间的最短距离的Dijkstra算法执行过程：

最后得到v1到其他各城市的最短路径及最短距离为：

v1到v2的最短路径是：v1v2 长度为1 v1到v3的最短路径是：v1v2v3 长度为3 v1到v4的最短路径是：v1v2v3v5v4 长度为7 v1到v5的最短路径是：v1v2v3v5 长度为4 v1到v6的最短路径是：v1v2v3v5v4v6 长度为9

求下图中顶v1到v11的最短轨及最短距离。 v52v2v81

265 3979v66v9281L v1v11v3 4321471

v49v71v10

100个顶点的星的最大顶点次数是 。

做一个图G，使其顶的次序列为(5,5,4,4,3,3,2,2,2)。

下列哪个序列不可能构成一个图的顶点次数序列？ A．(2,2,2,2,2) B．(3,3,3,3) C．(1,2,3,4,5) D．(2,2,3,4,5)

已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 ．

任取n个人组成的人群，n≥2，证明至少有两位，他们在人群中的朋友一样多。

证明：把n个人看做n个点，如果两个人是朋友，则在这两个点之间连一条边，这样可以得到一个含n个顶的单图。

显然顶的最大次数为n?1，如果这n个顶的次数不一样，则它们必为0,1,2,…,n?1，而次为0的顶与各顶都不相邻，因此不可能有顶的次为n?1，出现矛盾。因此n个顶的次数必至少有两个是相等的。

所以至少有两位，他们在人群中的朋友一样多。

设G是一个含n个顶点的无向简单图，n是大于等于2的奇数．证明图G与它的补图GC中的奇数次顶点个数相等。

E(GC)是由完全图Kn的边删去E(G)所得到的．所以对于任意结点u∈V(G)，u在G和GC中的次数之和等于u在Kn中的次数．由于n是大于等于2的奇数，从而Kn的每个顶点都是偶数度的（n?1≥(2)度），于是若u∈V(G)在G中是奇数次顶点，则它在GC中也是奇数次顶点．故图G与它的补图GC的奇数次顶点个数相等。

具有m条边的树有几个顶点？