强乘积图的限制边连通度和限制弧连通度的中期报告.docx

该【强乘积图的限制边连通度和限制弧连通度的中期报告 】是由【niuwk】上传分享，文档一共【2】页，该文档可以免费在线阅读，需要了解更多关于【强乘积图的限制边连通度和限制弧连通度的中期报告 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。强乘积图的限制边连通度和限制弧连通度的中期报告强乘积图是由两个图的笛卡尔积构成的有向图,其中一个图为主图,另一个图为副图。强乘积图具有很多在网络中应用的特性,如路由算法、集成电路设计等。本文研究了强乘积图的限制边连通度和限制弧连通度的问题。限制边连通度定义:强连通有向图G的边连通度为最小的整数k,使得至少需要删除k条边才能使得图G不再是强连通图。我们通过建立强乘积图G的一个辅图来研究限制边连通度的问题。首先对主图和副图分别进行一次深度优先搜索,得到主图和副图的拓扑序列。然后,对于主图中所有在拓扑序列中位置相邻的两个节点,若在辅图中不存在一条有向边从前一个节点连向后一个节点,则在辅图中添加一条有向边(前一个节点指向后一个节点)。同样地,对于副图中所有在拓扑序列中位置相邻的两个节点,若在辅图中不存在一条有向边从前一个节点连向后一个节点,则在辅图中添加一条有向边(前一个节点指向后一个节点)。对于强乘积图G,通过计算其辅图的边连通度,即可得到G的限制边连通度。我们采用数值计算的方法来求解边连通度,具体计算过程为:,将路径长设为1。,找到路径长为k的所有路径,,将路径长加1,重复步骤2,直到找到了一条从u到v的路径或搜索完毕。,则返回路径长即为边连通度k;否则,将路径长加1,回到步骤2,继续搜索。限制弧连通度定义:强连通有向图G的弧连通度为最小的整数k,使得至少需要删除k条弧(即至少需要将强连通图G中一条有向路径上的所有边或反向边删除)才能使得图G不再是强连通图。我们采用类似于限制边连通度的方法,利用辅图求解强乘积图G的弧连通度。具体地,我们对于主图和副图的任意两个顶点,如果它们在辅图中没有一条有向边连接,则我们令它们之间有一个边权为1的有向边;,我们采用数值计算的方法来求解弧连通度,具体步骤为:,将路径长设为1,,找到路径长为k的所有路径,,将路径长加1,重复步骤2,直到找到了一条从u到v的路径或搜索完毕。,则返回路径长即为弧连通度k;否则,将路径长加1,重复步骤2,直到找到从u到v的路径或搜索完毕。总结本文研究了强乘积图的限制边连通度和限制弧连通度的问题,通过建立强乘积图的辅图来解决这些问题。在计算边连通度和弧连通度时,采用了数值计算的方法。我们的实验结果表明,这种方法可以在较短时间内得到精确的结果。