共查询到20条相似文献,搜索用时 31 毫秒
1.
关于嵌入图中最短圈的多项式算法的存在性问题,是由Thomassen最早提出的.本文通过改进的Ford-Fulkerson算法,可以得到最短割算法.另一方面,通过定义嵌入图的几何对偶图及其相应的嵌入系统,得到几何对偶图中的可分离圈就对应于原图中的割;反之,若几何对偶图中的割在原图中对应于-个圈,那么该圈一定可分离.从而在射影平面上解决了Mohar与Thomassen关于是否存在多项式算法寻找短圈的问题.对于-般曲面上嵌入图,只要它的面宽度充分大,那么同样有多项式算法发现最短可收缩圈. 相似文献
2.
3.
关于图与圈之并图的圈唯一性 总被引:2,自引:0,他引:2
Farrell[1]引进图 G 的圈多项式 c(G;■).文[6]猜测:轮形图 W_8是圈唯一的.本文中我们证明上述猜测为真且讨论了某些图与圈之并图的圈唯一性. 相似文献
4.
5.
完全图K_n(n为奇数)或K_n-I(n为偶数,I为K_n的1-因子)是否有2-因子分解称Oberwolfach问题.每个2-因子恰包含α_i个长为m_i的圈(i=1,2,…,t)的Oberwolfach问题记为OP(m_1~(α_1),m_2~(α_2),…,m_t~(α_t)).证明了对任意的a≥0,b=2,3和s=3,5,6,且(a,s,b)≠(0,3,2),都存在OP(4~a,s~b)的解. 相似文献
6.
本文研究了图的反符号圈控制的问题.利用分类和反证的方法,获得了满足反符号圈控制数为负边数加4的连通图的刻画和完全二部分图的反符号圈控制数. 相似文献
7.
8.
两个不交图的联图的最小圈基长度 总被引:1,自引:0,他引:1
这篇文章中,我们分两种情形分别给出了计算两个不交图的联图的最小圈基长度的公式.作为它们的应用,我们给出了计算n个相同的图的联图以及完全r-部图等图的最小圈基长度的公式. 相似文献
9.
一个边割被称为圈边割,如果该边割能分离图的两个不同圈.如果一个图有圈边割,称该图为圈边可分离的.一个圈边可分离图G的最小圈边割的阶数被称为圈边连通度,记作cλ(G).定义:ζ(G)=min{w(X)|X导出G的最短圈},其中w(X)为端点分别在X和V(G)-X中的边的数目.如果一个圈边可分离图G使得cλ(G)=ζ(G)成立,称该图是圈边最优的.Tian和Meng在文章[11]以及Yang et al在文章[15]中研究了两种不同的双轨道图的圈边最优性.本文我们将研究具有两个同阶轨道的双轨道图的圈边连通度. 相似文献
10.
11.
研究了(赋权)图的圈基结构并且对包含在最小圈基中的短圈提供了大量信息. 建立了一个基变换的Hall型定理, 利用此定理, 给出了判断一个圈基是最小圈基的充分必要条件, 而且,证明了一个(赋权)图的最小圈基结构是唯一的. 这一性质对于最大圈基也成立 (尽管在最小圈基方面已有很多工作, 而在最大圈基方面的工作几乎没有). 利用这些方法, 发现了(赋权)图中具有特定性质的短圈的一些新结果. 作为应用, 决定了一个嵌入图的短圈的结构, 并找到一个多项式算法能够判断一个嵌入图中是否存在双侧圈, 如果这样的圈存在, 就可以找到一个最短的双侧圈. 这回答了B. Mohar和C. Thomassen提出的一个未解决问题, 并对他们提出的另一个未解决问题给出了部分解答. 相似文献
12.
本文研究了Abel群上 Cayley图的Hamilton圈分解的问题.利用"字"和H方操作法,获得了Abel群上4度Cayley图的Hamilton圈分解方案和理论证明. 相似文献
13.
14.
The problem of decomposing a complete 3-uniform hypergraph into Hamilton cycles was introduced by Bailey and Stevens using a generalization of Hamiltonian chain to uniform hypergraphs by Katona and Kierstead. Decomposing the complete 3-uniform hypergraphs K_n~(3) into k-cycles(3 ≤ k n) was then considered by Meszka and Rosa. This study investigates this problem using a difference pattern of combinatorics and shows that K_(n·5m)~(3) can be decomposed into 5-cycles for n ∈{5, 7, 10, 11, 16, 17, 20, 22, 26} using computer programming. 相似文献
15.
16.
17.
记G=(V,E)是简单图,1971年Bondy得到O re条件下的泛圈图的著名结果:若2连通n阶图G的不相邻的任两点x、y均有d(x) d(y)≥n,则G是泛圈图或G=Kn/2,n/2.这里进一步研究条件d(x) d(y)≥n-1,得到:若2连通n阶图G的不相邻的任两点x、y均有d(x) d(y)≥n-1,则G是泛圈图或G∈{K(Cn 1)/2∨G(n-1)/2,Kn/2,n/2}.本文作者得知最近国际著名权威专家Ho lton等人也得到完全相同的结果,但本证明更简捷. 相似文献
18.
19.
阶为$n$的图$G$的圈长分布是序列$(c_1,c_2,\cdots,c_n)$, 其中$c_i$ 是图$G$ 中长为$i$的圈数.设$A\subseteq E(K_{n,r})$.本文得到如下结果: 若$\mid A\mid =2$,且$n\leq r\leq \min\{n+6,2n-5\}$,则$G=K_{n,r}-A$是由它的圈长分布确定的;若$\mid A\mid =3$,且$n \leq r\leq \min\{n+6,2n-7\}$,则$G=K_{n,r}-A$也是由它的圈长分布确定的. 相似文献
20.
图上作业法是借助流向图进行物流合理规划的简便线性规划方法.对于有圈交通图,“舍边破圈”是用图上作业法解决平衡运输问题的关键.将对运输问题图上作业法的破圈技巧展开探讨,梳理了几种常用的破圈技巧,并通过若干反例说明了常用的破圈技巧其效果的不确定性,最后给出了相对合理可行的破圈调整技巧. 相似文献