三圈图的最小Hosoya指标的任务书.docx

该【三圈图的最小Hosoya指标的任务书 】是由【niuww】上传分享，文档一共【2】页，该文档可以免费在线阅读，需要了解更多关于【三圈图的最小Hosoya指标的任务书 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。三圈图的最小Hosoya指标的任务书任务书:三圈图指由三个互相连接的圆组成的连通图,如下图所示。请你研究对于给定的三圈图,其最小Hosoya指标的计算方法。Hosoya指标是指该图的所有不同的简单环(包括图中的三个圈)的节点数和边数之和。例如,在下图中,共有7个简单环,它们的节点数和边数之和分别为:+2=+2+3=+3+3=+4+3=+4+2+3=+4+3+3=+4+3+2+3=15因此,这个图的Hosoya指标为5+8+9+10+12+13+15=72。请你设计算法,针对给定的三圈图,计算其最小Hosoya指标。你需要使用图的邻接矩阵来表示该图,并采用程序自动读取输入和输出结果的方式。具体要求如下:输入:输入的第一行包括一个整数n(3≤n≤100),表示三圈图中所有节点的个数;接下来的n行,每行n个整数0或1,用空格隔开。第i行第j列的整数表示节点i和节点j之间是否有边相连。若相连则该值为1,否则为0。输出:输出单独一个整数,表示给定三圈图的最小Hosoya指标。样例输入:6011000101100110110011011001101000110样例输出:42提示:三圈图是一种特殊的图形式,由于这个图的边具有一定的规律,因此对于一个节点i和j之间的连接情况,有以下特点:节点i,j分别代表三个圆上的节点,节点i在第一圆上,节点j在第二圆上,若二者之间连有一条边,则相应的第三个点k将在第三个圆上,且与字符i,j的位置相对;多个匹配关系之间不会重叠;也就是说,节点i和j之间的连边,在第三个圆上只有唯一的节点与之对应。