一类极大临界h连通图

讨论了最小度等于 3h/ 2 - 1的极大临界 h连通图的性质 ,并给出这类图的构造方法 .

一类极大临界h连通图的性质

设G是h连通图 ,图G的顶点v称为临界点 ,G-v不再h连通 ,如果G的每一个顶点都是临界的 ,则称G为临界h连通图 .对于G中任意两个不相邻的顶点x与y ,G +xy不再临界h连通 ,则称G为极大临界h连通图 .引入图的粘合的概念 ,讨论了δ(G) =3h/ 2 - 1的极大临界h连通图的性质 ,得到了这类图有关原子 ,最小点割和分支的重要性质 ,这有利于进一步研究这类图的结构 .

一类极大临界h连通图的结构

引入图的粘合的概念,进一步研究最小度等于3h/2-1的极大临界h连通图均性质,给出一个图是这类图的一个充要条件,由此给出这类图的一种新的构造方法,更易操作．

一种基于极大连通子图的电信社群网分割算法

随着电信事业的发展,电信社群网的分析逐渐兴起。根据电信数据的特点,以关系数据库为基础,实现了一个极大连通子图求解算法(MCSG)。该算法利用等价类的概念实现了图数据分层处理,利用边标识法表示极大连通子图,确保了结果中顶点和边信息的完整性。实验表明,MCSG算法有效实现了对电信社群网的分割。

变换图G^(-+-)的极大边连通性

对任意图G=(V(G),E(G)),其变换图G^(-+-)的顶点集为V(G)∪E(G),顶点α和β在G^(-+-)中邻接当且仅当下列条件之一成立:当{α,β}■E(G)时,α和β在G中不邻接或不关联;当{α,β}■ E(G),α和β在G中邻接。证明了所有连通的变换图G^(-+-)都是极大边连通图。

一种基于极大连通子图的相关度属性选择算法

本文提出一种基于极大连通子图的相关度属性选择算法,该算法利用极大连通子图求解方法得到最优属性子集,该属性子集满足相关度要求并且尽可能多地保留数据集中包含的信息。论文结合选定的分类算法验证该属性选择算法的应用效果,实验表明,该属性选择算法在分类算法的数据预处理过程中可明显提高分类准确率,与利用贪婪搜索策略的基于相关度的属性选择算法相比,应用该算法的分类算法准确率更高。

极大3等周边连通图的充分条件

k等周边连通度是一个比边连通度更可靠的网络可靠性参数。连通图G的k等周边连通度定义为γ_k(G)=min{[X,]:X■V(G),X≥k,≥k},其中=V(G)\X。令β_k(G)=min{[X,]:X■V(G),X=k}。图G是极大k等周边连通的如果γ_k(G)=β_k(G)。令G是一个阶至少为6的连通图。本文证明了如果对于G中任意一对不相邻的顶点u,v,当u和v都不在三角形中时满足N(u)∩N(v)≥2;当u和v中至少有一个在三角形中时满足N(u)∩N(v)≥5,那么G是极大3等周边连通的。

基于Tarjan算法的极大点连通子图研究

由于传统朴素算法求解无向图的双连通分量时间花费过高,为了在线性时间内求出双连通分量并得到极大连通子图。文章对Tarjan算法的思想以及具体实现做出了详细的分析。同时结合具体实例,验证了算法中割点的判定条件以及回溯数组初始化的有效性和适用性。最后,给出了Tarjan算法在求解极大连通子图过程中,结点和栈空间状态转化图。

极大限制边连通网络的充分条件

限制边连通度是度量网络可靠性的重要参数。设G是一个边集为E的连通网络。称一个边集合S?E是一个限制边割,如果G-S是不连通的且每个分支至少有两个顶点。网络G的限制边连通度,记为λ',定义为G的最小限制边割的基数。设d(v)表示顶点v的度,ξ=min{d(u)+d(v)-2:uv∈E}表示G的最小边度。称网络G是极大限制边连通的,如果λ'=ξ。给出了网络是极大限制边连通的一些充分条件。

网络连通性的最优化

简述了极大边连通图和超边连通图;限制边连通度、极大限制边连通图和超限制边连通图的研究进展.