极大3限制边连通图的充分条件

k限 制 边 连 通 度 是 度 量 网 络 可 靠 性 的 重 要 参 数。 设G = (V, E)是 一 个 连 通 网 络。 称 一 个 边 集 合S ? E 是一个k限制边割,如果G ? S的每个连通分支至少有k个顶点。 称G的所有k限制边 割中所含边数最少的边割的基数为G的k限制边连通度,记为λk (G)。 定义ξk (G) = min{[X, Y ]:|X| = k,G[X]连通,Y = V (G)\X}。 称网络G是极大k限制边连通的,如果λk (G) = ξk (G)。 给出了网络是极大3限制边连通的一些充分条件。

极小n边连通图的几个性质

设Ｇ是简单极小ｎ边连通图，最大度为△（Ｇ），ｎ度顶点集合为Ｄ．对每一顶点ｘ∈Ｖ（Ｇ），给出Ｖ（Ｇ）─（Ｘ）一个特殊划分，并由此推出｜Ｄ｜≥△（Ｇ）及存在ｄ（ｘ）条边不相交的Ｘ－Ｄ路．

围长为g>5的极大4限制边连通图的充分条件

设G=(V,E)是一个连通图.称一个边集合S■E是一个k限制边割,如果G-S的每个连通分支至少有k个顶点.称G的所有k限制边割中所含边数最少的边割的基数为G的k限制边连通度,记为λk(G).定义ζk(G)=min{[X,Y]:|X|=k,G[X]连通,Y=V(G)\X}.称图G是极大k限制边连通的,如果λk(G)=ζk(G).本文给出了围长为g>5的极大4限制边连通图的充分条件.

围长g>7的极大5限制边连通图的充分条件

设G=(V,E)是一个λk-连通图,称图G的λk-割所含边的数目为G的k限制边连通度.定义ξk(G)=min{|[X,Y]|∶|X|=k,G[X]连通,Y=V(G)\X}.拟研究λ5(G)=ξ5(G)的围长条件.

极大4限制边连通图的充分条件

设G=(V,E)是一个连通图。称一个边集合S⊆E是一个k限制边割,如果G-S的每个连通分支至少有k个顶点。称G的所有k限制边割中所含边数最少的边割的基数为G的k限制边连通度,记为λk(G)。给出了图是极大4限制边连通的充分条件。

探索2-边连通图的等价定义

k-边连通图在网络研究和图论研究中有着极其重要的地位.图论中有关2-边连通图的命题很多,它们刻画了2-边连通的本质.本文给出17种关于2-边连通图的等价性命题,力图从不同角度深入理解、挖掘2-边连通图的本征,并从本文定义的2种新运算出发,提出了新的有关2-边连通图的命题,并给出这些命题相互间的等价性证明.

判定k-点连通图与k-边连通图极小性的定理

主要研究了判定k 点连通图是极小的充要条件和k 边连通图是极小的必要条件 .

3-边连通图中的超欧拉图

一个含有生成闭迹的图称为超欧拉图 .设G是n阶 3-边连通图 ,若对任意G的边数为 3的最小边割E都满足G -E的每一连通分支的阶至少为 (n - 1) / 10 ,则或者G是超欧拉图 ,或者G可收缩为G′=Petersen图 ,且G′的每个顶点在G中的原像是G的一个可折叠子图 ,其顶点数至少是 (n - 1) / 10 .

一类特殊的m限制边连通图

设G是一个连通图,F是G的一个边割,若G-F的每个连通分支至少有m个顶点,则称F是G的一个m限制边割.若图G存在m限制边割,则称图G是m限制边连通图.文章刻画了只含一个圈且长度为5的m限制边连通图.

图中顶点子集的边连通度与最优分级边连通图的构造问题

G =(V ,E)是无向连通图 ,无环允许有重边 .S是V的至少包含两个顶点的子集 ,S的边连通度λG(S)被定义为使S中的顶点不属于同一连通分支所需去掉的最少边数 .给定集合V和V的一个划分V =V1∪V2 ∪…∪Vr(|r|≥ 1,|V1|≥ 2 )以及正整数序列k1>k2 >… >kr≥ 2 .记Si=V1∪V2 ∪…∪Vi,1≤i≤r.构造一个连通图G =(V ,E)满足 :λG(Si)≥ki(1≤i≤r)且边数 |E|最小 .这种图G称为与所给划分和正整数序列相对应的最优分级边连通图 .在给出顶点子集的边连通度概念的基础上 。

含有欧拉生成子图的3边连通图

本文所讨论的图均为无向、有限简单图。文中没有指明的记号、术语见[3]。图G的欧拉生成子图是一条经过G的所有顶点的闭迹,以下简称S-闭迹。

临界n-连通图与临界n-边连通图的特征

Lick在文献[1]中给出了n-连通图与n-边连通图的充要条件.本文在这基础上给出了临界n-连通图和临界n-边连通图的特征.

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

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

图的边连通性研究及简单实现

提出了一个通过DFS树求解图的边连通性问题的简单算法,本算法具有容易理解、形式规范的特点,无论用于教学还是解决实际问题,都有较大的实用价值。

临界h-边-连通图的临界度(英文)

图G称为k-临界h-边-连通的,若h=λ(G)且对每个k顶点集{u1,…,uk}有λ(G-{u1,…,ui})≤λ(G-{u1,…,ui-1})-1,i≤k.若G是k-临界h-边-连通但不(k+1)-临界h-边-连通,则记之为(h*,k*)λ.本文证明了:存在(h*,k*)λ图的充要条件是(1)1≤k≤[(h+1)/2],h≡0,1,2(mod 4);1≤k≤[(h-1)/2],h≡3(mod 4);或(2)k=h,G=Kk+1.

寻找λ-边连通子图的一次遍历搜索算法

寻找图的λ-边连通子图时,可利用深度优先搜索算法,但需要经过λ次的遍历搜索过程才能完成。基于图的邻接矩阵储存结构特点,提出了一种新的搜索算法,可以通过一次遍历搜索过程得到图的λ-边连通子图。对比深度优先搜索算法,新算法结构简单,容易实现,大大提高了算法的执行效率。这种搜索算法也可以用于判定图的连通性。

一种任意无向图的R边连通扩充算法

本文提出了一个最小地扩充任意无向连通图为 R 边连通图的有效算法RMA。该算法采用了“先满足必要条件,再满足充要条件”的指导思想。对于一个任意无向连通图,首先将图中各点扩充到它所要求的最小度,然后检查它是否满足充要条件,如果不满足,则将该图分解,再根据最优程则,增加扩充边。将图合并,最后进行可行删除,解雇增广点,得到一个最小 R 边连通图。

关于k-全图T_K(G)的连通性

本文主要研究全图与3-全图的连通性，得到G是k-边连通时，其全图T（G）是K-连通的，3-全图T3（G）连通的充要条件及连通3-全图T3（G）是2-连通的等一些结论。

关于临界n_连通图的一些性质

本文给出了临界n_连通图的充要条件,临界n_连通图是第一类图和临界n_连通图(v<2n+1)是临界n_边连通图等性质.

超级局部边连通定向图的依赖团数的度序列条件

一个有向图D称为超级局部边连通的，若对D的任意两个顶点u和v，每个λ（u，v）-割都由发自u的边组成，或由发至v的边组成．笔肯利用著私的Turan定理，给出了定向图是超级局部边连通的依赖团数的度序列条件．