单选题
11个城市之间的公路交通网络以及每条公路长度如图9-11所示。从城市s到城市t的最短距离为{{U}}
{{U}} 44 {{/U}}
{{/U}}；现引入“转弯”的定义如下：在从s旅行到t的过程中，每从一条公路转到另一条公路上时称进行了一次转弯，从城市s到城市t最少经过{{U}}
{{U}} 45 {{/U}} {{/U}}次转弯。
单选题
【正确答案】
C
【答案解析】
单选题
【正确答案】
A
【答案解析】[解析] 本试题第一问关于图论算法中两节点间最短距离求解的问题，也可看作赋权简单连通无向图的单源问题的求解。求单源最短距离主要使用迪克斯特拉(E.W.Dijkstra)算法求解，即按路径长度递增顺序产生各节点最短距离。
对于图9-11，从城市s到城市t的最短距离为(21+20+20+8+12)=81。
根据试题给出的“转弯”的定义，其实质是求从城市s到城市f中间至少要经过多少个节点。如果将图9-11中每条公路长度数值定义为“边”，则从城市s到城市t的行走路径为：21→25→45→12时，所经过的转弯次数为3，即最少需经过3次转弯。
单选题
在无向图G中，节点间的连通关系是一个二元关系，该关系是______关系。
【正确答案】
C
【答案解析】[解析] 根据连通的概念，在无向图G中，①节点X与其自身是连通的；②如果节点X与节点Y是连通的，则节点Y与节点X也是连能的：③如果节点X与节点Y是连通的，节点Y与节点z是连通的，则节点X与节点Z也是连能的。
根据关系的性质，这种节点间的关系满足自反性、对称性、传递性，因此该关系为等价关系。
单选题
图9-12中不存在______。
【正确答案】
A
【答案解析】[解析] 通过连通图G中每条边一次且仅一次，遍历图中所有节点的回路称为欧拉回路。
通过连通图G中每条边一次且仅一次，遍历图中所有节点的开路称为欧拉开路(欧拉路径)。
若G是连通图，则存在欧拉回路的充要条件是：所有节点的度数均为偶数度；存在欧拉开路的充要条件是：当且仅当G中有且只有两个节点的度数为奇数度。
由于图9-12中有两个节点的度数是奇数度，因此图9-12中只存在欧拉路径，但不符合欧拉回路的充要条件，即不存在欧拉回路。
通过连通图G中每个节点一次且仅一次的回路称为欧密尔顿回路。
通过连通图G中每个节点一次且仅一次的开路称为欧密尔顿开路(哈密尔顿路径)。
单选题
在图9-13中，由点O(0，0)到点P(5，6)的最短路径共有______条。
【正确答案】
B
【答案解析】[解析] 图9-13所示点O到点P的最短路径，即只能向上或向右走的所有路径。从点O走最短路径到点P可以分为两步：
(1)从O到点(1，1)：共2条路径，分别是先向上和先向右走。
(2)从点(1，1)到点P：设向右走一格的长度为x，向上走一格的长度为y，那么不管怎么走，从点(1，1)出发，总是要经过4个x，5个y，方能到达点P，所以一条从点(1，1)到点P的最短路径对应一个由4个x、5个y共9个元素构成的排列；反之，给定一个这样的排列，按照x，y的含义，必对应一条从点(1，1)到点P的最短路径。因此从点(1，1)到点P的最短路径与4个x，5个y的排列一一对应。故从点(1，1)到点P的最短路径计数转换为不尽相异元素的全排列问题，其解为从排列的9个位置中选出4个位置放x，剩下的5个位置放y，计数结果为[*]。
按照乘法规则，从点O到点P的最短路径数为2×126=252条。
单选题
设|V|=n(n＞1)，当且仅当______，G=＜V，E＞是强连通图。
【正确答案】
D
【答案解析】[解析] 在简单有向图G中，任何一对节点间两者之间是相互可达的，则称这个图是强连通的。设|V|=n(n＞1)，当且仅当G中有通过每个节点至少一次的回路，G=＜V，E＞是强连通图。
对于选项C，例如图“A→B”，即只有A到达B，有一次路，但是该图不是强连通的。因此选项C的说法不能成为强连通图的充要条件。