VERTEX-DISJOINT QUADRILATERALS IN BIPARTITE GRAPHS

H. Wang considered the minimum degrees condition that G has large vertex-disjoint cycles in bipartite graphs. Motivated by this, we consider the small vertex-disjoint cycles in bipartite graphs in this paper. We prove the following result: Let m > 3, n > 2 and k >1 be three integers. Let G = (V1,V2;E) be a bipartite graph with | V1| = | V2| =n > 2k 1. If the minimum degreefor any cycle C of G with length 2m, then G contains k vertex-disjoint cycles of length 4. Moreover, the degrees condition is sharp.     

Bipartite Consensus of Linear Multi-Agent Systems by Distributed Event-Triggered Control

For multi-agent systems with competitive and collaborative relationships, signed graph can more intuitively express the characteristics of their interactive networks. In this paper, the bipartite consensus is investigated for multi-agent systems with structurally balanced signed graph. In order to reduce actuation burden in dynamical network environment, the event-triggering strategy is applied to bipartite consensus protocol for the multi-agent systems. The triggered condition for each agent is designed by using its own information and transmitted information of its neighbors at sampling instant and make the number of triggers of the whole systems be reduced. Based on the distributed eventtriggered control, some sufficient conditions are derived to guarantee the leaderless and leader-following bipartite consensus. Finally, some numerical examples are shown to demonstrate the effectiveness of the theoretical results.     

基于二分图的城市公交网络拓扑性质研究

以北京市公交系统为例,用二分图模型对其进行描述,分别构建出公交站点网络和公交线路网络,对二分图、公交站点网络和公交线路网络进行了度的分布、集聚系数以及平均路径长度等拓扑参数的计算,并与规则网络和随机网络进行了比较,发现北京市公交系统具有"小世界"网络的性质.最后深入地研究了公交线路网络与公交站点网络拓扑参数形成的机理.     

基于二分图最优匹配的虚拟网络映射算法

针对现有虚拟网络映射存在开销较大、资源利用不够合理的问题,提出了一种基于二分图最优匹配的虚拟网络映射算法。首先以虚拟节点和物理节点为顶点构建二分图,将节点映射问题转化为二分图最优匹配问题;其次将节点资源评价最高的物理节点与节点需求评价最高的虚拟节点优先匹配,并利用Kuhn-Munkres算法求解二分图最优匹配,依据匹配结果进行节点映射;最后利用 k-最短路径算法实现链路映射。实验表明,与以往的映射算法相比,提出的映射算法在保持较高映射成功率的同时,提高了长期收益开销比,且资源利用更加合理。     

铁路技术站调机运用模型及算法

研究铁路车站作业计划编制过程中,如何编制调机运用计划的关键问题,通过分析运用调机时区集合上的偏序结构特点,可以知道使用调机问题的实质是偏序集合的全序分解问题。利用偏序集合的传递性构造调机的有向图－图,再将调机运用问题转化有向图的有向路分解问题,对于传递图构造它对应的偶图－无向偶图,将传递图的向路分解问题转化为其对应偶图的匹配问题,最后,利用偶图最大匹配问题的算法解决调机运用问题。     

THE CONNECTIVITY OF MAXIMUM MATCHING GRAPHS

The maximum matching graph of a graph has a vertex for each maximummatching and an edge for each pair of maximum matchings which differ by exactly oneedge. In this paper, we prove that the connectivity of maximum matching graph of abipartite graph is equal to its minimum degree.     

中国汽车零部件企业竞争网拓扑结构分析

通过搜集中国汽车零部件生产企业的信息,构建了中国汽车零部件及其生产企业的信息数据库以及描述二者之间关系的二部图,在二部图的基础上转化得到了零部件企业竞争网.用复杂网络的理论和方法分析了二部图和企业竞争网的各项静态统计属性.研究发现中国汽车零部件企业竞争网的度分布服从分段指数分布,且具有较小的平均路径长度、较大的群聚系数和结构测度值,表明其是既具有小世界性,又具有无标度性的随机网络.并讨论j二部图和企业竞争网的各项统计指标所具有的现实意义.     

众筹项目的个性化推荐:面向稀疏数据的二分图模型

二分图模型是一种全局优化算法,本文将二分图模型应用于直接推荐众筹项目,使用PersonalRank算法迭代计算网络节点的全局关联度,从而推荐那些基于余弦相似度的协同过滤不能有效推荐的项目,适用性更加广泛.更进一步,提出将二分图模型与协同过滤算法相结合,首先把网络结构划分为二分图,采用二分图算法得到的两类节点(用户节点,项目节点)之间的全局相似度,再结合协同过滤算法,得到基于二分图模型的协同过滤算法.实验表明,在众筹项目推荐中,由于数据极端稀疏,适宜采用二分图模型来进行相似度计算并进行推荐.     

基于DG的航天器部件可诊断性测点配置方法

以故障可诊断性,即可检测性和可分离性为目标进行测点配置方法研究。针对航天器部件测点较多,传统基于有向图（directed graph, DG）的方法在偶图绘制非常复杂且容易出错的情况,引入关联矩阵描述处理可诊断性测点配置方法,关联矩阵方法便于应用计算机编程,且在节点较多时便于扩展。在基于DG可诊断性测点配置方法思路的基础上,对应了关联矩阵与DG二者之间的转化关系,并以动量轮为例进行基于可诊断性的测点配置。结果表明该方法对卫星部件级测点配置具有实用价值。     

Bipartite Consensus of Discrete-Time Double-Integrator Multi-Agent Systems with Measurement Noise

The effects of measurement noise are investigated in the context of bipartite consensus of multi-agent systems. In the system setting, discrete-time double-integrator dynamics are assumed for the agent, and measurement noise is present for the agent receiving the state information from its neighbors. Time-varying stochastic bipartite consensus protocols are designed in order to lessen the harmful effects of the noise. Consequently, the state transition matrix of the closed-loop system is analyzed, and sufficient and necessary conditions for the proposed protocol to be a mean square bipartite consensus protocol are given with the help of linear transformation and algebraic graph theory. It is proven that the signed digraph to be structurally balanced and having a spanning tree are the weakest communication assumptions for ensuring bipartite consensus. In particular, the proposed protocol is a mean square bipartite average consensus one if the signed digraph is also weight balanced.     

新型公交网络模型与最优出行路径算法

给出一种标号的二分图公交网络模型,在此模型基础上给出线路换乘与最优出行路径的算法,这种算法充分利用标号信息给出站点网络图的边权函数.基于站点网络图不仅能够搜索换乘线路而且能够找到最短路径.最后利用天津市部分公交系统验证了该模型及方法的有效性.     

图书馆借阅网的二分图研究

通过搜集上海理工大学图书馆1年内的图书外借信息,构建了图书及其借阅者的数据库及描述二者关系的二分图.根据图书和读者之间是否存在借阅关系和读者借阅书籍的天数这两种情况分别建立了无权和加权网络,并且通过复杂网络的理论和方法分析得到相关统计属性.研究发现这些统计属性均服从指数分布,且无权和加权网中相应的统计属性正相关.这表明,与无权网络相比,加权网不仅能描述合作竞争关系和结构,还能精确地描述竞争结果.并且,结合实际讨论了二分图中读者和图书内部及其之间的合作竞争关系和各项统计指标所具有的现实意义.     

用于非直接对抗性体育比赛的编排算法

本文以非直接对抗性体育比赛的“最佳编排法”为基础,针对“最佳编排法”中没有考虑到的缺项现象设计了一种编排算法。该算法以偶图匹配、回溯技术为数学工具。     

疾病基因网络的二分图投影分析

介绍了一种可揭示同一集合内部结点相互关系的二分网络投影方法,并运用此方法对基因疾病二分网络图做研究.通过遗传性疾病与致病基因的关联性来分析不同疾病之间隐含的相互关系,得出由相同的基因变异所引起的各种不同疾病之间存在着或多或少的联系,这些疾病比起毫无联系的疾病,其相互引发的概率也要大得多.此结论使我们能够更清楚地认识到遗传性疾病的发病机制,对疾病预防以及医疗诊断都有一定的参考价值.     

飞行员全动模拟机复训问题求解

针对无训练资源约束的飞行员全动模拟机复训问题,构建双目标整数规划模型对问题进行刻画,通过构造网络流、二部图和加权路等一系列网络规划模型,将原问题转化为最小费用最大流和最长路求解问题,并设计多项式启发式算法对问题进行求解,证明所得解为原问题的非劣解. 最后,实证说明了模型和算法的有效性.     

MPS上作业的分配和调度问题

多处理机系统MPS(MultiprocessorSystem)上作业的分配和调度问题是其运行效率的关键.本文讨论的是具有不相容性作业集的作业分配和调度问题,提出了一种启发式方法及其定量分析技术,并证明了相关定理和若干推论.     

新型公交网络模型与最优线路选择算法

针对公交线路的最优线路选择问题,给出了基于标号公交网络二分图模型,在此模型基础上给出了最小换乘条件下的可行线路的“纺锤-修剪”搜索算法,进而给出在最小换乘条件下的最短路径和换乘站点的数学规划方法.最后给出算例并验证了该方法的有效性．     

EDGE CONDITION FOR A HAMILTONIAN BIPARTITE GRAPH TO BE BIPANCYCLIC

Let G be a hamiltonian, bipartite graph on 2n vertices, where n>3. It isshown that if e(G)>n(n-1)/2 + 2 then G contains cycles of every possible even length.This improves a result of Entringer and Schmeichel.     

Projective Group Consensus of Multi-Agent Systems with Arbitrary Parameter

In this paper, the projective group consensus issue for second order multi-agent systems(MASs) in directed graphs with a dynamic leader is investigated. The proposed projective group consensus with arbitrary parameter includes traditional consensus, reverse group consensus and cluster consensus as its special cases. Novel distributed control protocols are designed to obtain projective group consensus without analyzing signed directed graph as in most current literatures on bipartite consensus problem. On the basis of Lyapunov stability property, algebraic graph and some necessary matrix theory, sufficient conditions for delay and delay-free cases are derived. Finally, simulations of nonlinear chaotic MASs are adopted to testify the theoretical results.     

LDPC码的高效译码算法研究

对于LDPC码的译码算法即和积算法,目前的简化算法多在对数域中进行。提出了一种新的基于差分的译码算法,其主要思想是：在LDPC码的二部图上所传递的消息是概率的差分值,而对于校验节点和消息节点的更新都是在特定的加法域中进行。针对校验节点的更新,还可以选择若干个绝对值最小的差分值进行运算,以进一步降低复杂度。与传统的基于对数似然比的译码方法相比,该算法的计算复杂度有很大降低,而译码性能和收敛速度没有明显损失。