在具有6个顶点的无向简单图中，当边数最少为(26)条时，才能确保该图一定是连通图，当边数最少为(27)条时，才能确保该图一定是哈密尔顿图。给定带权的有向图，如下图所示。设该图代表一个地区的交通图，从S到T的最短路径有(28)条，路径的长度是(29)，从S

admin2009-02-15 91

问题在具有6个顶点的无向简单图中，当边数最少为(26)条时，才能确保该图一定是连通图，当边数最少为(27)条时，才能确保该图一定是哈密尔顿图。
给定带权的有向图，如下图所示。设该图代表一个地区的交通图，从S到T的最短路径有(28)条，路径的长度是(29)，从S出发经过每点一次且只有一次到T的路径(哈密尔顿路径)有(30)条。

选项 A、0
B、2
C、56
D、59

答案A

解析一个即不包含回路又不包含平行边的图称为简单图。如果一个无向图G的边数大于

为顶点个数)，则G是一个连通图。依题意n=6，所以如果边数大于10，则该图为连通图。如果图G具有一条包含　G中所有顶点的回路，则称该回路为哈密尔顿回路，其相应的图叫做哈密尔顿图，当边数最少为12条时，才能确保该图一定是哈密尔顿图。从入度为0的顶点S出发到达出度为。的顶点T的最短路径有两条，它们是：(S，A，E，F，T)和(S，A，B，　T)，其路径长度为56。从图中可以看出，从S出发经过每个顶点一次仅且一次到达T的路径不存在。

转载请注明原文地址:https://kaotiyun.com/show/gDxZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

在MIB-2功能组的接口组中，如果对象ifAdminStatus的值为up(1)，而ifOperStatus的值为down(2)，则该接口的状态为(38)。

在OSI参考模型中，上层协议实体与下层协议实体之间的逻辑接口叫做服务访问点(SAP)。在Internet数据帧中，目的地址“0x000F781C6001”属于(10)的服务访问点。

国际标准化组织制定的OSI公共管理信息协议是(8)，另外，ISO还定义了5个管理功能域，(9)属于性能管理域。IAB制定的网络管理切，议是SNMP，在SNMP管理框架中使用的管理信息库为(10)。管理站(Manager)通过GetRequest命令查询代

在层次网络体系结构中，第n层协议利用(2)提供的服务向(3)提供服务，对等实体是指(4)，数据在同一个系统自上层传到下层，这种数据格式称为(5)，某层实体接收到上层传来的数据后，一般要(6)才能使接收方知道如何处理。

光缆布线系统的测试是工程验收的必要步骤。以下不是对光缆进行测试的工作内容的是(57)。

女，36岁，风心病心衰，用强心苷和利尿剂治疗，出现恶心、呕吐、食，奴不振，心电图示；室性早搏二联律，可能是

以下是水浸法操作步骤的有()。

建设工程监理管理服务的内涵包括它的(　　)。

监管部门的作用有()。

根据马斯洛的需要层次理论，下列需要层次中，主要靠内在因素来满足的需要层次是()。

关于产品的认识，正确的看法是()

①如果有了正确的理论，只是把它_，并不实行，这种理论再好也是没意义的。②明摆着是歪理邪说，本应_才是，却有那么多人相信。真令人想不通。③这孩子真怪，别的什么都不怕，却怕癞蛤蟆，一只癞蛤蟆就吓得他_

根据下面材料回答问题：关于城镇污水集中处理情况，下列表述正确的是()。

软件设计师上午基础知识考试

软考中级

在MIB-2功能组的接口组中，如果对象ifAdminStatus的值为up(1)，而ifOperStatus的值为down(2)，则该接口的状态为(38)。

在OSI参考模型中，上层协议实体与下层协议实体之间的逻辑接口叫做服务访问点(SAP)。在Internet数据帧中，目的地址“0x000F781C6001”属于(10)的服务访问点。

国际标准化组织制定的OSI公共管理信息协议是(8)，另外，ISO还定义了5个管理功能域，(9)属于性能管理域。IAB制定的网络管理切，议是SNMP，在SNMP管理框架中使用的管理信息库为(10)。管理站(Manager)通过GetRequest命令查询代

在层次网络体系结构中，第n层协议利用(2)提供的服务向(3)提供服务，对等实体是指(4)，数据在同一个系统自上层传到下层，这种数据格式称为(5)，某层实体接收到上层传来的数据后，一般要(6)才能使接收方知道如何处理。

光缆布线系统的测试是工程验收的必要步骤。以下不是对光缆进行测试的工作内容的是(57)。

女，36岁，风心病心衰，用强心苷和利尿剂治疗，出现恶心、呕吐、食，奴不振，心电图示；室性早搏二联律，可能是

以下是水浸法操作步骤的有()。

建设工程监理管理服务的内涵包括它的( )。

监管部门的作用有()。

根据马斯洛的需要层次理论，下列需要层次中，主要靠内在因素来满足的需要层次是()。

关于产品的认识，正确的看法是()

根据下面材料回答问题：关于城镇污水集中处理情况，下列表述正确的是()。

建设工程监理管理服务的内涵包括它的(　　)。