电子科技大学图论期末考试复习题.docVIP

2015电子科技大学 图论考试复习题 关于图论中的图，以下叙述不正确的是 A．图中点表示研究对象，边或有向边表示研究对象之间的特定关系。 B．图论中的图，画边时长短曲直无所谓。 C．图中的边表示研究对象，点表示研究对象之间的特定关系。 D．图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系。 一个图中最长的边一定不包含在最优生成树内。 下面哪个图形不与完全二分图K3,3同构？ A． B． C． D． 有10条边的5顶单图必与K5同构。 ?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中的一条道路 B．是G中的一条道路但不是行迹 C．是G中的一条行迹但不是轨道 D．不是G的一条道路 图G如右，则befcdef A．是G的一个圈 B．是G的一条道路但不是行迹 C．是G的一条行迹但不是轨道 D．是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， 请画出6阶3正则图。 请画出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点到其他任意一点的最短路。 v1v3 v1v2 v1v2v5 v1v3v4 v1v2v5v6 v1v2v5v6v7 设有城市v1，v2，v3，v4，v5，v6，各城市之间的距离如下表。使用Dijkstra算法求城市v1到其他各城市的最短路径以及最短距离。要求说明求解过程（提示：应将城市之间的道路图看作是无向图）。 道路 v1v2 v1v3 v2v3 v2v4 v2v5 v3v5 v4v5 v4v6 v5v6 距离 1 4 2 7 5 1 3 2 6 解：下面的表格给出了求解v1到其他各顶点之间的最短距离的Dijkstra算法执行过程： 步骤 v1 v2 v3 v4 v5 v6 0 1/(v1) 4/(v1) ∞ ∞ ∞ ①/(v1) 3/(v2) 8/(v2) 6/(v2) ∞ ③/(v2) 8/(v2) 4/(v3) ∞ 7/(v5) ④/(v3) 10/(v5) ⑦/(v5) 9/(v4) ⑨/(v4) 最后得到v1到其他各城市的最短路径及最短距离为： v1到v2的最短路径是：v1v2 长度为1 v1到v3的最短路径是：v1v2v3 长度为3 v1到v4的最短路径是：v1v2v3v5v4 长度为7 v1到v5的最短路径是：v1v2v3v5 长度为4 v1到v6的最短路径是：v1v2v3v5v4v6 长度为9 求下图中顶v1到v11的最短轨及最短距离。 L 100个顶点的星的最大顶点次数是 。 做一个图G，使其顶的次序列为(5,5,4,4,3,3,2,2,2)。