Network Decomposition and Maximum Independent Set Part Ⅱ：Application Research

According to the researches on theoretic basis in part I of the paper，the spanning tree algorithms solving the maximum independent set both in even network and in odd network have been developed in this part，part Ⅱ of the paper．The algorithms trans form first the general network into the pair sets network，and then decompose the pair sets network into a series of pair subsets by use of the characteristic of maximum flow passing through the pair sets network．As for the even network，the algorithm requires only one time of trans formation and decomposition，the maximum independent set can be gained without any iteration processes，and the time complexity of the algorithm is within the bound of O(｜V｜^3)．However，as for the odd network，the algorithm consists of two stages．In the first stage，the general odd network is transformed and decomposed into the pseudo-negative envelope graphs and generalized reverse pseudo-negative envelope graphs alternately distributed at first；then the algorithm turns to the second stage，searching for the negative envelope graphs within the pseudo-negative envelope graphs only．Each time as a negative envelope graphhas been found．renew the pair sets network by iteration at once．and then tum back to the first stage．So both stages form a circulation process up to the optimum．Two available methods，the adjusting search and the picking-off search are specially developed to deal with the problems resulted from the odd network．Both of them link up with each other harmoniously and are embedded together in the algorithm．Analysis and study indicate that the time complexity of this algorithm is within the bound of O(｜V｜^5)．     

图的循环自同构群

证明了对于n阶循环群Cn(n>=3),存在3n个点,5n条边的图Gn,且Gn的自同构群Γ(Gn)与Cn同构.     

电子海图上水平夹角网的绘制

针对手工绘制水平夹角网的不足,分析了利用计算机绘制的必要性和可行性,设计了具体的算法,并基于VC6.0进行了编程实现,对减轻航海人员劳动具有一定的意义.     

Value of acoustic perceptual method for analysis of compensatory articulation errors in postoperative patients with cleft palate

Objective To establish an acoustic perceptual method analyzing the compensatory articulation errors in children with operated cleft palate via the formants of Chinese pure vowels. Methods The first three formants which represent vocal transmission character in Chinese pure vowels of 84 subjects with operated cleft palate, were measured by Computerized Speech Signal Processing System （CSSPS）. The Chinese vowel graph of postoperative patients with cleft palate was stated by the first formant frequencies （F1） and the second formant frequencies （F2） of the Chinese pure vowels between the two groups. Results Values of F1 and F2 of vowels except [a] in the poor articulation group （Group A） were significantly different from those in the good articulation group （Group B） （P〈0.05 or P〈 0.01）. As compared with that in Group B, the vowel graph demonstrated the decreased perceptual distances in Group A. These findings indicated that there might still be the backward movements of tongue, perverted mandibular movements and disharmonious lip movements in addition to the velopharyngeal insufficiency （VPI） in Group A. Conclusion The speech articulation of children with repaired cleft palate should be gained by correcting the aberrant compensatory articulation errors in the condition of velopharyngeal competence. Computerized Speech Signal Processing System （CSSPS）, which is regarded us the content of objective quantitative measurement, is a precise, simple, reliable and atroumatic technique for children with cleft palate to analyze pathological compensatory articulation errors.     

基于图自编码-生成对抗网络的路网数据修复

完整的交通路网数据是实现智能交通系统的前提,故本文提出一种基于图自编码-生成对 抗网络的方法对路网中缺失数据进行修复。首先,通过降噪图变分自编码器提取路网缺失数据 的时空特征,使其能最大程度捕获原始路网信息;其次,基于该时空特征利用生成对抗网络生成 路网数据,加入重建损失并优化生成对抗网络的目标函数,实现对缺失数据的有效插补;最后,采 用西雅图(Seattle)和加州(PEMS04)路网速度数据集,针对不同缺失类型和缺失率下的数据修复进 行对比实验。当随机缺失率在 10% ~70%时,Seattle 数据集的 MAE 指标在 2.38~3.25 之间, PEMS04 数据集的 MAE 指标在 1.46~2.38 之间;当聚集缺失率在 10%~70%时,Seattle 数据集的 MAE指标在2.51~2.82之间,PEMS04数据集的MAE指标在1.52~1.54之间。对比结果表明,本文 提出的路网数据修复方法均优于BP、DSAE、BGCP等模型。     

基于动态规划理论的船厂码头移泊作业问题研究

基于动态规划理论,建立了船厂码头移泊作业问题的动态规划模型.分析了移泊作业的特点,在此基础上建立起问题的动态模型和对应的赋值有向图,把问题转化为求解赋值有向图的最优路问题.依据图论相关知识,对赋值有向图进行改进,从而得到图的最优路,最终求得问题的最优方案.通过实例计算结果与船厂实际操作安排进行比较和分析,得出算法研究的有效性和优越性的结论.     

关于Cm×Kn的邻点可区别全色数

一个图的正常全染色如果相邻点的点染色及其关联边染色集合是不同的,则称为图的邻点可区别全染色;其所用到的最少颜色数称为图的邻点可区别全色数.得到了圈与完全图的笛卡尔积图的邻点可区别全色数.     

基于异构图学习的交通场景运动目标感知

为了提高无人车在交通场景中的运行效率和运输安全,研究了基于异构图学习的交通场景运动目标感知; 考虑实际交通场景中运动目标之间的复杂交互关系对目标运动的影响,基于异构图学习提出了交通场景中多目标检测-跟踪-预测一体化感知框架; 结合YOLOv5和DeepSORT检测并跟踪运动目标,获得目标的运动轨迹; 使用长短期记忆(LSTM)网络从目标历史轨迹中学习目标的运动信息,使用异构图学习目标间的交互信息,以提高运动目标轨迹预测准确度; 使用LSTM网络对目标运动信息与交互信息解码得到目标未来轨迹; 为了验证方法的有效性,在公共交通数据集Argoverse、Apollo和NuScenes上进行了评估。分析结果表明：结合YOLOv5和DeepSORT可实现对运动目标的检测跟踪,对交通场景中的运动目标实现了75.4%的正确检测率和61.4%的连续跟踪率; 异构图能够有效捕捉运动目标之间复杂的交互关系,并且捕捉的交互关系能够提高轨迹预测精度,加入异构图捕捉交互关系后,运动目标的平均位移预测误差降低了63.0%。可见,考虑交通场景中运动目标之间的交互关系是有效的,引入异构图学习运动目标之间的交互关系可以感知运动目标的历史与未来运动信息,从而帮助无人车更好地理解复杂交通场景。     

应用网络流模型解决航班衔接问题

针对单枢纽机场航线结构的特点，以所需飞机数最少为目标，提出了一种描述航班衔接问题的图论模型及优化算法。首先将航班衔接问题转化为航班节的衔接问题，并建立一个描述航班节衔接问题的二部图，将航班衔接问题转化为二部图的最大匹配问题，然后由二部图生成一个具有单源汇网络特征的辅助图，利用Ford-Fulkerson算法求该网络的最大流，进而得到二部图的最大匹配，从而得到了一个需用飞机数最少的航班节衔接方案，为利用计算机自动编制并优化航班衔接方案提供了一种可行方法。并且通过调整过站时间上限，可以得出不同的航班衔接方案，为制订生产计划提供了必要的灵活性。     

基于多模式的公铁联合军事运输网络图模型研究

目前,我军多方式联合运输的主要手段是铁路和公路,在现实运用中军队重点关注运输方式转换的过程,以便合理地制定转运与保障方案。运用多模式网络建模和图论的相关理论与方法,根据部队联合输送任务需求和转运保障特点,采用铁路车站军事运输装卸载能力指数和军事运输道路通过能力指数评估方法,在地理地图的基础上,简化路网,建立公铁联合军事运输网络图模型,拟为军事联合运输路径优化研究提供方法。