H-局部连通图的路圈性质的任务书.docx

该【H-局部连通图的路圈性质的任务书 】是由【niuww】上传分享，文档一共【2】页，该文档可以免费在线阅读，需要了解更多关于【H-局部连通图的路圈性质的任务书 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。H-局部连通图的路圈性质的任务书任务书题目:H-局部连通图的路圈性质任务描述:给定一个无向图G,称其为H-局部连通图,如果G的每个点v都至少与H中的一个点相邻接。即对于所有的v∈V(G),都存在至少一个u∈V(H),满足(u,v)∈E(G)。定义一个包含路径和环的图为GG,其中路径和环满足以下性质:,则它必须是G的子环。,则它必须包含在H中。-局部连通图(即GG的每个点v都至少与H中的一个点相邻接)。现在,需要你完成以下任务:-局部连通图G的一个环可以被拆分为若干条路径和环,并且每条路径只连接H中的点。。,则G中不存在环。,找出GG中的一个环。实现提示:可以基于前面的性质设计一个算法,从H中选择一个点作为起点,然后按顺序访问与该点相邻接的点,并标记已经访问过的点,直到遇到一个已经访问过的点,说明找到了一个环。如果找到的环不符合性质1,则从环上任意一点拆出一条路径,并继续搜索。如果遍历了所有的点都没有找到环,则GG中不存在环。评分标准:,证明一个H-局部连通图G的一个环可以被拆分为若干条路径和环,并且每条路径只连接H中的点,得5分。,证明GG中至少存在一个环,得10分。,证明如果GG中不存在环,则G中不存在环,得10分。,设计一个算法,找出GG中的一个环,得15分。,得20分。,得40分。