Tournament网络节点的排序算法

2024年2月5日发(作者：考研数学试卷有多少个题)

第37卷 第02期数字技术与应用第 37 卷 数字技术与应用 2019年 2月Digital Technology &ApplicationVol.37 No.2February 2019算法分析DOI:10.19695/12-1369.2019.02.70Tournament网络节点的排序算法林馨(福建师范大学 数学与信息学院,福建福州 350007)摘要:在组合网络理论中,常将网络节点抽象为图的节点,借助图来研究网络的性质。本文将Tournament网络抽象为图,并以网络中节点输出的信息量为依据,重点探讨了双向连通Tournament网络节点的排序问题,并给出相应的算法。关键词:tournament；网络；排序中图分类号:O157.5文献标识码:A文章编号:1007-9416(2019)02-0124-020 引言在组合网络理论中,常将网络节点抽象为图的节点,借助图来研究网络的性质[1]。若从节点A到节点B有信息传输,则对应的图上有从顶点A到顶点到B的有向边。图中,若存在从顶点A至顶点C的一条有向路径,则认为在网络中节点A的信息能传输至节点C。以节点在网络中输出的信息量为依据,对网络节点的重要性进行排序[2]。考虑一类特殊的网络:Tournament网络。相关定义:任意两个顶点间都有边的无向图称为完全图。每条边都有方向的图称为有向图。有向完全图称为Tournament图[3]。对任意一对顶点,若存在两条有向路径,使得两顶点可以互相连通,则这类有向图称为双向连通的。若Tournament图存在唯一的完全路径(即经过所有顶点的有向路径),则按此完全路径的顶点顺序,可给出Tournament网络的节点排序。010A0其邻接矩阵为:01011100000110110100101000001110为每个顶点计分以衡量其输出的信息量,则可得顶点的分数向量t(t1,t2,,t6)T,其中ti是顶点i的分数。则结合邻接矩阵的定义,知tA(1,1,1,1,1,1)T(3,2,3,2,1,4)T。但由此分数向量对节点进行排序,只能反映出节点直接输出的信息量,而忽略了间接传输的信息量。为了得到更合理的排序,我们试图找一个分数向量,使它能综合全面的反映出节点输出的信息量。令tt(1),进一步求t(2)At(1)(6,7,5,3,2,9)T,此分数向量表示每个顶点(作为出点)的邻接顶点在t(1)中的分数之和。继续求解,1 主要结论以下讨论双向连通Tournament网络(即每对顶点间存在两条有向路径,此时图上有不止一条完全路径)节点的排序问题。定义n阶Tournament图的邻接矩阵A(aij)nn:t(3)(10,15,12,9,7,16)T,t(4)(28,26,31,22,15,38)T,t(5)(68,66,63,41,26,96)T,...当k时,t(k)归一化后将收敛到某个极限分数向量,即邻接矩阵A的对应于最大特征值的特征向量t。可算出邻接矩阵A的最大特征值2.2324,对应的最大特征向量t(0.4047,0.4437,0.4167,0.2878,0.1988,0.5859)T归一化后得:t(0.1731,0.1898,0.1783,0.1231,0.0850,0.2507)T由此可得,节点排名为{6,2,3,1,4,5}对n阶双向连通Tournament网络节点排序算法如下:Step1.A0nn.i1,j2. 若i到j存在有向边,则令aij1,转step3;否则转3.若jn,则j:=j+1;否则转4.若in,则i:i1,j:1转step2;否则,转5.计算矩阵A的最大特征值和对应的特征向量1, 存在顶点i到顶点j的有向边aij0, 否则考查以下6阶Tournament网络如图1所示。该图具有两条完全路径:452613以及652134,因此为双向连通Tournament网络。图1 6阶Tournament网络图t(t1,t2,,tn)6.对特征向量的各分量排序[4]:Begink=n;收稿日期:2019-01-09作者简介:林馨(1981—),女,福建福州人,硕士研究生,讲师,研究方向:图论及其应用。124Copyright©博看网 . All Rights Reserved.

林馨:Tournament网络节点的排序算法flag=1;While flag>0 doBegink=k-1;flag=0;for i=1 to k doif

titi1 thenBeginxti;titi1;ti1x;flag=1;EndEndEndStep8. 输出排序后的节点。2019年第 02 期2 结语本文将Tournament网络抽象为图,并以网络中节点输出的信息量为依据,结合代数的知识,重点探讨了双向连通Tournament网络节点的排序问题,并给出相应的算法。此结论为进一步研究各类网络结构和性质提供了依据。参考文献[1] J.A Bondy and U.S.R Murty,“graph theory with applications”,1st Edition, The MacMillan Press,1976.[2] 张莹.运筹学基础[M].清华大学出版社,2004.[3] 耿素云.离散数学[M].北京大学出版社,2015.[4] 苏德富,钟诚.计算机算法设计与分析[M].电子工业出版社,g Algorithm of Tournament NetworkLIN Xin(Fujian Normal UniversityCollege of Mathematics and Informatics Fujian,Fuzhou Fujian 350007)Abstract:In combination network theory, we often consider nodes of a network as vertexes of a graph, so we can study the properties of networksvia graphs. In this article, we will specifically study Bi-connected tournament network, based on the amount of information each node transmit, and givean algorithm to sort all nodes according to their importance in this words:tournament;network;sorting······上接第123页送器,输出接口视为从发送器。该模块采用2／4分裂基高效算法,具有最少的乘法次数和加法次数,简单高效。4 结语本文采用2／4分裂基FFT实现的IPCore进行运算处理和谐波分析,简单高效,有效满足系统实时性和测量精度的要求。仿真和测试的结果符合设计预期,基本达到精度要求,论文所设计的基于FPGA实现FFT运算和系统控制,可以完成对电力系统的谐波分析和电能质量的监测工作,本次设计很好的体现了其灵活性、高速高效、可重构性和高度集成性等优点。参考文献[1] 闫斌.基于FFT谱分析测频算法的FPGA实现[J].科技创新与应用,2013(35):39-40.[2] 刘鹰子,宋元瑞.基于FPGA的FFT算法实现[J].电脑编程技巧与维护,2012(7):87-90.[3] 王金玉,侯士波,林雨晴.基于HHT的暂态电能质量扰动信号检测的研究[J].自动化与仪器仪表,2016(7):12-14.[4] 王志伟,赵庆生,郭贺宏,et al.混合基FFT在电能质量监测装置中的应用[J].水电能源科学,2015(4):189-192+188.[5] 房国志,王猛,王康.基于FPGA的暂态电能质量的检测方法[C]//电工测试技术学术交流会,2012.3 仿真分析在Matlab中产生模拟信号S(t),进行仿真分析,其谐波表达式为:S(t)Asin(2ft30)A/3sin(6ft45)A/5sin(6ft60)其中A=1,f=50Hz,采样频率fs=12.8kHz。经过FFT处理后,根据QuarusII下波形仿真图转化为其对应的各次谐波值。对于模拟输入信号的时序,通过FFT IP Core的驱动模块实现控制,运行至8ns附近输出运算结果。其中基波实部和虚部分别为Y1r=020000H,Y1i=000000H,转换十进制复数为810000+010000i,3次谐波实部和虚部分别为Y3r=93C5H,Y3i=554AH,转换十进制复数为213089+113327i,5次谐波实部和虚部分别为Y5r=3333H,Y5i=58A2H,转换十进制数表示为018000+113849i。这些数据经过进一步的计算,结果如表1所示。由表中数据可得,经过该FFT模块运算和数据处理,能够有效分解出各次谐波幅值和相位,处理精度符合预期,结果表明其输入信号的时序逻辑控制是正确的。Research on Algorithm and Application of Power Harmonic Measurement Based on SOPCQI Xin-bo,TONG Zhan-ying,JIANG Wei-hua(Henan Institute of Technology,Xinxiang Henan 453003)Abstract:This paper studies a power harmonic measurement algorithm and its implementation based on SOPC, In order to solve the problem thatthe system is complex and can not be reconstructed,when the current implementation algorithm of digital signal processor is simulationresults show that the processing accuracy is in line with expectations, and the requirements of system measurement are realized. It has the characteristicsof high integration, flexible reconfiguration and strong words:power harmonics;SOPC;FFT125Copyright©博看网 . All Rights Reserved.