路的k阶幂图的连通性研究

设G是连通图,G的k阶幂图G^(k)是一个与G具有相同顶点集的图,G^(k)中的两个顶点相邻当且仅当这两个顶点在G中的距离不大于k.本文研究了路的幂图P_(n)^(k)的点连通度κ(P_(n)^(k))、边连通度λ(P_(n)^(k))和限制边连通度λ_(2)(P_(n)^(k)).得到:当n>k时,κ(P_(n)^(k))=λ(P_(n)^(k))=k;关于限制边连通度:当2≤n≤k+1时λ_(2)(P_(n)^(k))=2n-4,当n>k+1时,λ_(2)(P_(n)^(k))=2k-1.

基于幂图的属性约简搜索式算法

粗糙集理论是一种新的处理不精确、不完全与不一致数据的数学工具.属性约简是粗糙集理论的重要研究内容之一,已有的属性约简算法主要是基于代数表示与信息表示的方法.同一问题在不同的知识表示下,其求解难度是不同的.文中从改变属性约简问题的知识表示入手,提出了该问题的一种新的表示方式——幂图;给出了基于幂图的属性约简搜索式算法,把属性约简计算问题转化为在幂图中的搜索问题.理论分析表明新算法是有效的,为属性约简研究提供了一条新的途径.

路径幂图、Flower Snark图及多锥图独立数

图的独立数是图论中的重要参数,令G=(V(G),E(G))是一个简单有限无向图.如果V(G)的子集S中任意两个顶点均不相邻,则S是图G的一个独立集.顶点独立集大小的最大值,称为图G的独立数,记做α(G).研究了路径幂图、Flower Snark及其相关图、多锥图的独立数问题,首先构造出了它们的独立集,得到其独立数的下界,然后证明了该值也是其独立数的上界,并给出了它们独立数的准确值.

基于幂图的离群子空间搜索算法

通过分析子空间搜索算法的研究现状以及存在的问题,提出基于幂图的离群子空间搜索算法。该方法主要讨论离群点产生的原因,能够找出单个对象的离群子空间,并根据离群子空间对离群点进行分类。在对幂图扩展的基础上进行剪枝,减少了存储量和计算量,算法性能得到很大的提高。采用实例说明了该算法,并通过实验证明了该算法的可行性和高效性。

幂图的全色数

根据幂图的结构性质,利用穷染、替换的方法,研究了幂图Pkn的全色数,并给出了一种染色方案.

幂图P_n^k的邻点可区别全色数和邻点可区别-VE全色数

根据路的幂图Pkn的结构性质,用穷染、递推的方法,讨论了Pkn的邻点可区别全染色和邻点可区别-VE全染色,得到了相应的色数,并给出了一种染色方案。

两类幂图的强边染色

图的强边染色是在正常边染色的基础上,要求每个色类的导出图是一个匹配。本文通过构造法,研究了路的幂图的强边色数至多是9,圈的幂图的强边色数至多是14。

幂图的点强全色数

图G的一个正常全染色称为图G的点强全染色,当且仅当N[v]中任意元素都染有不同的颜色,其中N[v]={u|uv∈E(G)}∪{v},图G的点强全染色所用颜色的最少数目称为图G的点强全色数.文章通过研究幂图Pk n的结构性质,利用穷染、置换的方法,研究了幂图Pk n的点强全色数,并给出了一种具体的染色方案.

幂图C_n^2的强边染色

图的强边染色是在正常边染色的基础上,要求距离至多为2的任意两条边染不同颜色.根据幂图的结构,利用构造、穷染的方法,给出了幂图C_n^2的强边染色,得到了图C_n^2的强边色数.

幂零群与内幂零群的幂图

主要研究幂零群、内幂零群以及内交换群幂图的相关图论性质.一般地,给出有限群G的幂图P(G)为某图的线图当且仅当G为素数幂阶循环群,得到幂零群与内交换群幂图独立数取临界值时的充要条件,以及内幂零群与内交换群幂图可平面化的充要条件.最后,分析内幂零群与内交换群真幂图的连通性,给出了连通情形的直径估计以及非连通情形的连通分支个数.

幂图的两个遗传性质

图G=(V,E)被称为点可迹的,如果对任意一点u,G中存在Hamilton链使u为其一端点;图G被称为{u}-Hamilton链连通的,如果对任意v∈V\u,G中存在Ha-milton链使u,v为其两端点。对于任意V_0V,0≤|V_0|≤h(或V_0V\u.0≤|V_0|≤h),如果G\V_0是点可迹的(或{u}-Hamilton连通的),则称G为h-点可迹的(或h-{u}-Hamilton连通的)。本文证明了:若G是h-点可迹的(或h-{u}-Hamilton连通的),则其幂图G^h是(h+2k-2)-点可迹的(或(h+2k-2)-{u}-Hamilton连通的)(|V|≥h+2k+1)。

简单连通图的k阶幂图的指数集(英文)

设Ｇ 是一个ｎ 阶简单连通图，ｋ≥２ 是一个整数．Ｇ 的ｋ 阶幂图记作Ｇｋ ，定义为：Ｖ（ Ｇｋ） ＝ Ｖ（ Ｇ） 且对任意ｕ ，ｖ∈Ｖ（ Ｇｋ） （ ｕ≠ｖ） ，（ ｕ ，ｖ） ∈Ｅ（ Ｇｋ） 当且仅当ｄＧ（ ｕ ，ｖ） ≤ｋ ，则对任意的ｋ≥２ ，Ｇｋ 本原．令Ｅ（ｋ，ｎ） ＝ ｛ γ（ Ｇｋ）｜ Ｇ 是ｎ阶简单连通图｝ ，可以得到Ｅ（ｋ ，ｎ） ＝ｄｋ ｋ＋ １ ≤ｄ ≤ｎ － １ ， 若２ ≤ｋ≤ｎ － ２ ，｛２｝ ， 若ｋ≥ｎ － １ ．

关于连通图的k阶幂图的几个性质

本文研究了简单连通图的 k 阶幂图的一些性质,给出了有关边连通、局部连通和叶连通的结果,以及有关泛圈和泛连通的结果。

路和圈幂图的邻点可区别E-全染色

以一个简单图G为基础,连接G的任意最短路长为k的2个顶点就可得到基础图G的k-幂图,研究了路的k-幂图和圈的2-幂图的邻点可区别E-全染色问题,并结合该类幂图的结构性质,运用构造法、反证法和穷举分类染色技术给出了其邻点可区别E-全色数,为确定图的各类染色问题提供了有效的借鉴.

关于有限群幂图的强彩虹连通数

图的强彩虹连通数在网络信息安全传输中有重要的应用,由于决定图的强彩虹连通数问题是NP-困难的,因此需要给出一些特殊图的强彩虹连通数的计算方法.该文首先运用图论与群论的相关知识,给出了幂图强彩虹连通数的一些上下界,并且研究了达到界的一些幂图.其次利用这些界给出了循环群、初等交换p-群、二面体群和半二面体群的幂图的强彩虹连通数的计算公式.结果表明,幂图的强彩虹连通数依赖于群的极大对合数及群的极大循环子群数.

连通图二次幂图的Hamilton连通性

本文对圈和树的二次幂图的 Hamilton 连通性进行了研究。

简单无向连通图的k阶幂图的指数集

设Ｇ为简单无向图，以Ｖ＝Ｖ（Ｇ）为顶点集，以Ｅ＝｛（ｕ，ｖ）｜ｄ（ｕ，ｖ）≤ｋ｝为边集的图称为Ｇ的ｋ阶幂图。ｎ阶简单无向连通图的ｋ（ｋ≥２）阶幂图的指数集。

关于小阶数非交换群的简化幂图

给定一个有限群G,群G上的简化幂图是以G的所有元素为顶点集合的一个简单图,其中两个不同的顶点x和y相邻当且仅当⊂或⊂。本文将给出14阶以内的非交换群的简化幂图的结构。此外本文也求了这些群简化幂图的独立数、团数以及彩虹连通数。

圈的幂图的s-迹连通性

对于图G的任意两个顶点x和y,如果G有一条(x,y)-生成迹,则称图G是迹连通的。给定一个整数s≥0,对于任意点子集X?V(G)并且|X|≤s,如果G-X是迹连通的,则称图G是s-迹连通。设k是一个正整数,图G的k次幂图记为G~k。设t(G)是t一个最大值s使得图G是s-迹连通但不是(s+1)-迹连通,设C_n是一个包含n个点的圈,k是一个正整数并且k≥2,将证明:t(C_n~k)={2k-3,如果n=2k+22k-2,如果n≥2k+3 n-3,如果n≤2k+1.

两类图的幂图的联结数

本文给出了路与圈的任意k次幂图(k≥2)的联结数的计算公式,并给出了证明。