检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

二分图最大匹配问题的分布式算法

计算机工程与应用 1990年第10期26卷 48-53页

作者：唐策善梁维发中国科技大学计算机系

本文基于异步通讯网络,对二分图最大匹配问题,建议了两个分布式算法。其中第一个简单算法的通讯复杂性为O(n(n^2+m))、时间复杂性为 O(n^3);第二个算法的通讯复杂性为O(n^(1/2)(n^2+m))、时间复杂性为O(n^(5/2)),这里n和m分别为二分图... 详细信息

本文基于异步通讯网络,对二分图最大匹配问题,建议了两个分布式算法。其中第一个简单算法的通讯复杂性为O(n(n^2+m))、时间复杂性为 O(n^3);第二个算法的通讯复杂性为O(n^(1/2)(n^2+m))、时间复杂性为O(n^(5/2)),这里n和m分别为二分图的结点个数及边的数目。关于这一问题的分布式算法目前尚未见诸报导,这里建议的算法很可能是此问题的第一个分布式算法。

关键词：二分图最大匹配分布式算法

在线全文

学校读者我要写书评

暂无评论

二分图的与星正交的(g,f)-因子分解

陕西师范大学学报（自然科学版） 1998年第1期26卷 25-28页

作者：马润年高安喜空军电讯工程学院数学教研室陕西财经学院管理科学系

设ｇ和ｆ是定义在二分图Ｇ的顶点集Ｖ（Ｇ）上的两个整数值函数且对每个ｘ∈Ｖ（Ｇ）有ｇ（ｘ）≤ｆ（ｘ）．证明了若Ｈ是二分图Ｇ的任一ｍ－星，则Ｇ有一个（ｇ，ｆ）－因子分解与Ｈ正交的充要条件是Ｇ为一个（ｍｇ，ｍｆ）－图．

关键词：正交因子分解无向图二分图星

在线全文

学校读者我要写书评

暂无评论

二分图的因子

二分图的因子

作者：鲁富荣山西大学

学位级别：硕士

具有重要的理论意义的因子问题，一直是图论中的热点话题之一，且至今已有相当丰富的研究成果。关于分数因子的研究也是最近几年提出的新问题。国外数学家在匹配概念的基础上提出因子、分数因子的概念。设g和f是定义在V(G)上的两个整数... 详细信息

具有重要的理论意义的因子问题，一直是图论中的热点话题之一，且至今已有相当丰富的研究成果。关于分数因子的研究也是最近几年提出的新问题。国外数学家在匹配概念的基础上提出因子、分数因子的概念。设g和f是定义在V(G)上的两个整数值函数，且对每个x∈V(G)有0≤g(x)≤f(x)，设F是图G的一个生成子图，若对每个x∈V(G)有g(x)≤d(x)≤f(x)，则称F为图G的一个(g，f)-因子。若g(x)=a，f(x)=b，则称上述因子为(a，b)-因子。若a=b=k，则称(a，b)-因子为k-因子。设h是定义在图G的边集E(G)上的一个函数，使得对任意的e∈E(G)有h(e)∈[0，1]，令d(x)=∑h(e)，其中E={e|e=xy∈E(G)}，则称d(x)是G中顶点x的分数度。若h满足对任意的x∈V(G)，有g(x)≤d(x)≤f(x)，则称h是G的一个分数(g，f)-表示函数。令E={e∈E(G)|h(e)≠0}，设G是G的生成子图，若E(G)=E，则称G是G的一个分数(g，f)-因子。类似可定义分数(a，b)-因子，分数k-因子。在第一章中，我们给出了本文所用的术语、记号。在第二章中，给出了二分图存在分数k-因子的一个充要条件。在第三章中，给出了二分图中包含圈和对集的一个证明。在第四章中，研究了二分图中一个与韧度相关的参数与k-因子存在性的关系。本文主要结果如下：定理2.1设G=(X，Y;E)为二分图，G有分数k-因子当且仅当对任意的S(?)X，T(?)Y，有sum from j=0 to k-1(k-j)P(G-S)≤k|S|，且sum from j=0 to k-1(k-j)P(G-T)≤k|T|。其中P(G)=|{x|d(x)=j}|。定理2.2设G=(X，Y;E)为二分图，a，b为两个非负整数，且a≤b。若对任意的S(?)X，T(?)Y，有sum from j=0 to a-1(a-j)|(G-S)∩T|≤b|S|且sum from j=0 to a-1(a-j)|(G-T)∩S|≤b|T|，则G存在[a，b]-因子。其中G={x|d(x)=i}。定理3．1设G=(V，V;E)是一个二分图，|V|=|V|=n≥5，并且δ(G)≥[1/2n]+1，又设l是满足 (1)3≤l≤n-1 (2)l≠n(mod2)的任一整数，则G有一个支撑子图含有长为2l的圈C和n-l条边的对集M，使得V(C)∩V(M)=φ。一般地，N(x)表示x在图G中的邻集，我们令N(x，T)=N(x)∩T表示T中x的邻集且d(x，T)=|N(x，T)|。定理4．2设G=(X，Y;E)是一个二分图，若对任意的T(?)X或Y，r≤2，且t′(G)=1，则二分图G存在2-因子。其中r=|{x|d(x，T)=1，x∈N(T)}|。

关键词：二分图因子分数因子度韧度

一种改进的二分图投影算法及其在专家意见综合中的应用

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

管理评论 2013年第11期25卷 106-114页

作者：朱正祥顾基发国防大学信息作战研究所北京100091 中国科学院数学与系统科学研究院北京100190

复杂问题的解决,单靠数据、信息和模型是不够的,还需集成专家的意见,然而专家的意见未必一致,需要对专家意见的共识情况进行综合。本文提出基于二分图网络投影算法的专家意见综合方法,并对传统的二分图边权重单一的不足进行了改进,使其... 详细信息

复杂问题的解决,单靠数据、信息和模型是不够的,还需集成专家的意见,然而专家的意见未必一致,需要对专家意见的共识情况进行综合。本文提出基于二分图网络投影算法的专家意见综合方法,并对传统的二分图边权重单一的不足进行了改进,使其减少投影过程中的信息损失,以满足复杂条件的分析需要。实证表明,改进之后的算法能够准确地反映不同专家间的意见相似度以及单个专家在群体中的独立性。最后,利用非线性映射技术,以可视化方式直观显示专家意见的共识情况。

关键词：意见综合二分图共识研讨厅

在线全文

学校读者我要写书评

暂无评论

二分图的Laplace矩阵的最大特征值

合肥工业大学学报（自然科学版） 2004年第8期27卷 952-955页

作者：殷剑宏合肥工业大学计算机与信息学院安徽合肥230009

图的Laplace矩阵的谱,在物理、化学和计算机等学科有着广泛应用。但是,求图的Laplace矩阵的谱,是很不容易的。文章通过分析二分图的结构,研究了二分图的Laplace矩阵的特点,利用非负矩阵的经典理论和图论方法,导出了一般二分图的Laplace... 详细信息

图的Laplace矩阵的谱,在物理、化学和计算机等学科有着广泛应用。但是,求图的Laplace矩阵的谱,是很不容易的。文章通过分析二分图的结构,研究了二分图的Laplace矩阵的特点,利用非负矩阵的经典理论和图论方法,导出了一般二分图的Laplace矩阵的最大特征值的界值。

关键词：二分图 Laplace矩阵最大特征值界值

在线全文

学校读者我要写书评

暂无评论

DTN中基于二分图的路由选择

福建师范大学学报（自然科学版） 2014年第6期30卷 33-39页

作者：林超君林丽美许力周书明福建师范大学数学与计算机科学学院福建福州350007 福建省网络安全与密码技术重点实验室福建福州350007

由于DTN(delay tolerant networks)缺乏稳定的端到端传输路径,为了提高其路由协议的传输效率,减少网络延迟和开销,主要采用增加冗余数据包副本的办法.而传统的DTN路由协议往往无法有效地控制数据包副本的数量,最终导致路由性能下降.由于... 详细信息

由于DTN(delay tolerant networks)缺乏稳定的端到端传输路径,为了提高其路由协议的传输效率,减少网络延迟和开销,主要采用增加冗余数据包副本的办法.而传统的DTN路由协议往往无法有效地控制数据包副本的数量,最终导致路由性能下降.由于DTN网络中的节点具有社会属性这一特点,使得节点的移动具有一定的规律性和稳定性.首先分析了节点之间信息交换关系,证明DTN中存在二分图的性质.其次提出DTN网络中基于二分图的路由选择和具有时间因素的最优路由算法,最后给出了模拟仿真实验结果.

关键词： DTN 社会属性二分图时间因素最优路由

在线全文

学校读者我要写书评

暂无评论

基于二分图的D2D通信资源复用分配算法

计算机应用研究 2017年第7期34卷 2096-2098,2103页

作者：滑思忠丁爱玲郭达伟郗恩崇长安大学经济与管理学院西安710064 长安大学地质工程与测绘学院西安710064 长安大学信息工程学院西安710064 西北工业大学自动化学院西安710072

为了提升D2D(device to device)通信资源复用分配的频谱效率,以最大化系统吞吐率为目标建立资源复用模型。同时面对高复杂度的组合优化求解过程,提出一种分布式的资源分配迭代算法,该算法使用二分图建立D2D用户与RB(resource block)资... 详细信息

为了提升D2D(device to device)通信资源复用分配的频谱效率,以最大化系统吞吐率为目标建立资源复用模型。同时面对高复杂度的组合优化求解过程,提出一种分布式的资源分配迭代算法,该算法使用二分图建立D2D用户与RB(resource block)资源的关系模型。每轮资源分配中,D2D用户根据所在RB资源上的动态干扰环境,自治地竞争RB资源,基站则根据吞吐率增益选举最优的D2D用户分配,避免多对一的RB竞争冲突。仿真实验表明,二分图算法在降低算法复杂度的同时,拥有较优的吞吐率性能优势。

关键词：终端到终端资源复用分配二分图迭代选举

在线全文

学校读者我要写书评

暂无评论

基于二分图的组密钥管理方案设计

计算机科学 2009年第4期36卷 101-104,124页

作者：周杰饶艳芬李慧芬华南理工大学广东省计算机网络重点实验室广州510641

随着基于群组通信应用的不断发展,安全群组通信成为目前分布式计算领域和信息安全领域研究的一个热点问题。有效的组密钥管理是安全群组通信需要解决的关键问题。将一个安全群组通信系统中组成员拥有的辅助密钥与组成员之间的关系用一... 详细信息

随着基于群组通信应用的不断发展,安全群组通信成为目前分布式计算领域和信息安全领域研究的一个热点问题。有效的组密钥管理是安全群组通信需要解决的关键问题。将一个安全群组通信系统中组成员拥有的辅助密钥与组成员之间的关系用一个二分图表示,将设计组密钥管理方案问题转化为构造满足一定条件的二分图的问题,为设计组密钥管理方案提供了一种新途径。利用构造的二分图设计了一种组密钥管理方案。所设计的组密钥管理方案不需要组管理中心保存树或矩阵等结构,因而降低了组管理中心的存储开销,另外避免了类似LKH方案中维持平衡树的开销。

关键词：安全群组通信系统组密钥管理辅助密钥二分图

在线全文

学校读者我要写书评

暂无评论

基于二分图网络的项目与专家多重匹配策略

小型微型计算机系统 2016年第3期37卷 545-550页

作者：陈泽亚王庆郭静陈晰王晶华中国科学技术大学计算机科学与技术学院合肥230026 中国科学技术大学苏州研究院江苏苏州215123 国家电网公司信息通信分公司北京100761

科技项目培育或评审过程中,往往同时有多个项目和多位专家.每个项目都有限制被匹配的专家数量,每个专家又有最多容许匹配的项目数量.目前大多数的匹配过程中,专家多由人为确定或随机选取产生,往往导致专家与所评项目内容不匹配或相关度... 详细信息

科技项目培育或评审过程中,往往同时有多个项目和多位专家.每个项目都有限制被匹配的专家数量,每个专家又有最多容许匹配的项目数量.目前大多数的匹配过程中,专家多由人为确定或随机选取产生,往往导致专家与所评项目内容不匹配或相关度较低的现象.对于项目与专家网络具有的复杂网络特性,本论文着重考虑到项目与专家网络中同时存在的高聚类和小世界现象,将项目与专家进行抽象,从网络节点的关联性出发,利用二分图网络流模型,提出两种贪心匹配策略与一种传统最大流匹配策略的组合策略,设计出项目与专家的多重匹配算法.本文最后采用电力行业数据集进行多次实验,验证该策略可以有效应对项目专家网络,在计算耗时和匹配结果上都较传统网络流算法高效.

关键词：复杂网络多重匹配策略二分图网络流算法