基于距离泛化的二分图(α,β)-core高效分解算法

(α,β)-core分解作为图数据管理与分析研究中的热点问题,已经被广泛应用于电商欺诈检测和兴趣群组推荐等实际场景中。然而现有(α,β)-core模型在构建时仅考虑顶点距离为1的邻居,难以刻画出二部图社区中的细粒度信息。针对此问题,提出了基于距离泛化的(α,β,h)-core模型,即由二部图中两个不相交的顶点集构成一个最大子图,满足一个集合中的任何一个顶点至少有α个与它的距离不大于h的邻居顶点,另一个集合中的任何一个顶点至少有β个与它的距离不大于h的邻居顶点。通过引入距离为h的邻居,解决了(α,β)-core模型细粒度刻画能力不足的问题。由于新模型需要考虑距离不大于h的邻居,因此(α,β,h)-core分解变得更为困难。为此,提出了基于计算共享的分解策略,据此设计了高效的(α,β,h)-core分解算法,并分析了算法性能。考虑到确定距离不大于h的邻居顶点非常耗时,还提出一种(α,β,h)-core下界以减少重复计算距离不大于h的邻居顶点,进一步提高计算效率。在8个真实图数据上的对比实验结果验证了新模型的有效性和算法的高效性。

机械产品选配问题的二分图非形式化描述

在机械产品选配中,为了表达装配模型应考虑的关键因素、装配体间的配合关系以及便于个性化更改,建立基于二分图的机械产品选配非形式化描述模型,提出了d型匹配需要满足的约束条件。利用0-1矩阵将非形式化描述转化成一个便于用算法实现的形式化模型。在此基础上,提出了基于遗传算法的形式化模型求解方法。通过一个机械产品选配实例对其进行了验证。

同级供应网络中产品的协同调剂研究

论述了同级供应网络中产品调剂的可能性。说明了实现产品调剂需要网络中各节点的协同。针对产品调剂的目标,从产品缺货损失、产品库存积压损失和调剂成本等方面,建立了相应的有向赋权二部图,并转化为网络流模型求解最优产品调剂方案。用具体实例论证了模型的可行性。讨论了需要进一步研究的内容。

模糊偶图最佳匹配的计算与度量

通过模糊综合评判给出模糊偶图中边的隶属度，又给出一种简化计算的代换法，并对节省的计算量给出度量，得出一种应用效果更佳的调配方法．

偶图特征的谱刻划

本文用图的谱性质刻划偶图及完全偶图的特征性质．

TREE DECOMPOSITIONS OF MULTIGRAPHS

For a graph G, if E(G) can be partitioned into several pairwise disjoint sets as{E1 , E2,...,El } such that the subgraph induced by Ei is a tree of order ki ) (i = 1, 2,... , l),then G is said to have a {k1, k2, ..., kl }-tree-decomposition, denoted by { k1, k2 ,..., Kl } G.For k 1 and l 0, a collection (k,l) is the set of multigraphs such that G e Q(k,l)if and only if e(G) = k(G - 1) - l and (H) max{(k - 1)(H - 1),k(H -1) -l}for any subgraph H of G. We Prove that (1) If k 2,0 l 3 and G Q(k,l) oforder + 1, then {n,n,...,n -- l} E G. (2) If 2 and G (k,2) of ordern 3, then {n,n, ...,n,n-- 2} E G and {n,n,.. -1,n - 1} G. (3) If 3 andG g(k,3) of order n 4, then {n, n,... n,n-- 3} G ) {n,n,.., n,n-- 1,n -- 2} Gand {n,n,... n,n -- 1,n -- 1,n -- 1} G.