一些图的弱外部平衡划分

设G是一个图。G的一个2-划分是V(G)的一个2-划分,即V(G)=V1∪V2且V1∩V2= ∅。如果一个2-划分满足||V1|-|V2||≤1,我们就称其为平衡划分。本文的研究主要基于Bollobás和Scott提出的一个猜想:每个图G都有一个平衡划分(V1,V2),对于V1中的每一个顶点v,v的邻点中至少有一半减去一个在V2中;对于V2中的每一个顶点v,v的邻点中至少有一半减去一个在V1中。在本文中,将对二部图、皇冠图以及风车图证实这一猜想。

拟平衡二部图的弱逐点可迹性的若干充分条件

图的哈密尔顿问题一直以来都是图论研究的重点和难点。由于图的谱和拓扑指数便于计算,近年来人们开始利用其优势来研究图的哈密尔顿性。受此启发,首先根据平衡二部图是弱哈密尔顿-连通的边充分条件得到拟平衡二部图是弱逐点可迹的边充分条件;其次利用图的谱半径及无符号拉普拉斯谱半径分别给出了拟平衡二部图是弱逐点可迹的充分条件;最后利用图的Wiener指数、Hyper-Wiener指数以及Harary指数分别给出了拟平衡二部图是弱逐点可迹的充分条件。

平面二部图的完美匹配集合上的有向根树结构及其生成

图的完美匹配或１－因子指覆盖了其所有顶点的独立边集．对含有完美匹配的平面二部图，其所有完美匹配通过某旋转变换形成层次组织结构，可用有向根树或半格表示．

2n阶(n-2)-正则二部图的最小基本圈基

设图G为2n阶(n-2)-正则二部图.构造了图G的一个基本圈基并且证明了此圈基就是图G的一个最小基本圈基,同时还确定了任意最小基本圈基对应的生成树的结构.

平面二部图的无圈边染色

本文主要研究了平面二部图的无圈边染色问题。证明出:对于平面二部图G,如果任意一个度为3的顶点至多关联于一个度为4的面,那么其无圈边色数a'(G)≤△(G)+3。

关于平面图平衡二部划分的一个结论

关于平面图的平衡二部划分的研究有一个猜想:任意具有n个顶点的平面图必含有一个平衡二部划分V_(1),V_(2),使得e(V_(1),V_(2))≤n.本文证明了n阶平面图G,若其边数m≤2n-2,则G含有一个平衡二部划分V_(1),V_(2),使得e(V_(1),V_(2))≤n.并给出了它的极图有且仅有K_(4).

二部图中的匹配问题

(本讲适合高中)实际应用中,有非常多的问题与图的匹配有关,而一般涉及图的匹配问题都比较有难度.对于特殊的二部图而言,结论相对完善.本文主要研究二部图中的匹配问题及其相关的结论在具体问题中的应用.1知识介绍先介绍一些与图有关的定义和基本结论.二部图图G(V,E)的顶点集V可分成两个两两不相交的子集的并(V=V_(1)∪V_(2),V_(1)∩V_(2)=■).

完全二部图Kn+1,2n与完全三部图K1,n,2n的厚度关系

图的厚度是指将该图分解为平面生成子图的最小数,它是衡量一个图可平面性的关键指标之一.研究一个图的厚度至关重要,它在超大规模集成电路和网络设计中有着重要应用.目前已经得到一部分图类的厚度的精确值,但完全二部图与完全三部图的厚度关系未完全得到,通过构造完全三部图K1,3p+1,6p+2的一个平面分解得到了完全三部图K1,n,2n的厚度,进而推出完全二部图Kn+1,2n与完全三部图K1,n,2n的厚度相等.

超图的可平面性算法

随着超图理论在实际问题中的深入应用,其平面性研究也更加具有意义。回顾了超图的一般理论,给出了超图的二部图概念,并在此基础上给出了超图的可平面性算法。该算法是多项式时间算法,是有效算法。

Mycielskian图的凸控制和弱凸控制数的研究

令 G = (V, E) 是一个连通图。用 dG(u, v) 表示图 G 中的两个顶点 u 和 u 之间的最短(u, v) 路的长 ,一个长 为 dG(u, v) 的(u, v) 路 一个(u, v) -测地线。图 G 的一个点子集 X ⊆ V 叫做图 G 的一个弱凸集,如果对 X 中的任意两个顶点 a, b ,在图 G 中都存在一个(a, b) -测地线使信(a, b) -测地线上的所有顶点都属千 X. 类似地,图 G 的一个点子集 X ⊆ V 叫做图 G 的一个凸集,如果对 X 中的任意两个顶点 a, b, 图 G 中的每一条(a, b) -测地线上的所有顶点都属千 X。图 G 的一个点子集 D ⊆ V 叫做图 G 的一个控制集,如果 V -D 中的每一个顶点都至少有一个邻点在 D 中. V 的点子集 X   为 G 的弱凸(或凸)控制集,如果 X 既是弱凸(或凸)集又是控制集。图 G 的弱凸(或凸)控制数,是点数最少的弱凸(或凸)控制集所包含的点数,记为 γwcon(G) (或γcon(G)). 本文主要给出了一些特殊图的Mycielskian图的控制数、弱凸控制数和凸控制数的确切值。

弱哈密顿连通图关于Wiener指数,Harary指数,hyper-Wiener指数的充分条件

对于一个平衡二部图,如果任意两个不同部分的顶点可以由一条哈密顿路连接,那么该平衡二部图称为弱哈密顿连通图。在给出连通的平衡二部图的拓扑指数条件的基础上,利用Wiener指数、Harary指数和hyper-Wiener指数分别给出了平衡二部图是弱哈密顿连通的充分条件。

平面图最小平衡二部划分的上界

关于平面图的平衡二部子图的研究有一个猜想:任意一n个顶点的平面图G(V,E),必含有一个平衡二部子图G(V_1,V_2)使得e(V_1,V_2)≤n.证明了若n个顶点的哈密尔顿平面图G(V,E)中含有一个近似等边三角形,n≥18,那么G(V,E)必含有一个平衡二部子图G(V_1,V_2)使得e(V_1,V_2)≤n.

二部平面图的邻点可区别边色数

图G的邻点可区别边染色是G的一个正常边染色,使得每一对相邻顶点有不同的颜色集合.图G的邻点可区别边色数χ′_a(G)是使得G有邻点可区别边染色的最少颜色数.2006年,Edwards等证明了对最大度至少为12的连通二部平面图,有χ′_a(G)?+1.本文改进了上述结果,证明了若G是最大度至少为7的连通二部平面图,则χ′_a(G)?+1.

Hamilton非二部图的弱泛圈性

图G称为弱泛圈图是指G包含了每个长为l(g(G)≤l≤c(G))的圈,其中g(G),c(G)分别是G的围长与周长.1997年Brandt提出以下猜想:边数大于[(n^2)/4]-n+5的n阶非二部图为弱泛圈图.1999年Bollobás和Thomason证明了边数不小于[(n^2)/4]-n+59的n阶非二部图为弱泛圈图.作者证明了如下结论:设G是n阶Hamilton非二部图,若G的边数不小于[(n^2)/4]-n+12,则G为弱泛圈图.

M是连通拟阵与G（D#）是连通图的关系

研究M是连通拟阵与G(D#)是连通图的关系。证明了M中有一个基B,使得C1,C2,…,Cn-r是M中全体对应于基B的基本极小圈,等价于对任意j∈1,2,…,n-r,Cj∪i≠jCi。由此证明了(Cunningham 1973,Krogdahl 1977)M是连通拟阵等价于B∪e∈E(M)-BCM(e,B),并且对任意X∩Y=φ,X∪Y=E(M)-B都有∪e∈XCMe,B∩∪e∈YCM(e,B)≠φ。得到结果为M是连通拟阵等价于G(D#)是连通图。

关于图形思维能力的开发

一、机械制图课程教学中的图形思维1.两个过程与两个需要。机械制图课程的基本要求,就是以三维形象与二维图象互相转换能力为基本能力,或曰主要能力。课程教学自始至终就是在图画和看图中完成基本要求的。画图过程是:三维形象——二维图象——三维形象;而看图过程为:二维图象——三维形象——二维图象。

n维立方体的性质

n维立方体是一个n-正则的二部图,既有实际应用价值又有理论价值。文中重点研究了n维立方体的Hamilton性质及可平面性质,证明了n维立方体是Hamilton图及非平面图,并且给出了一个具体构造Hamilton圈的方法。

两类广义控制问题的NP-完全性(英文)

研究两类广义控制问题的复杂性:κ-步长控制问题和κ-距离控制问题,证明了κ-步长控制问题在弦图和平面二部图上都是NP-完全的,作为上述结果的推论,给出了κ-距离控制问题在弦图和二部图上NP-完全性的新的证明,并进一步证明了κ-距离控制问题在平面二部图上也是NP-完全的。

一类非匹配分配格

讨论了一类含有一个割点的有限分配格,给出了一类非匹配分配格:当m,n≥3时,m+n型有限分配格L是非匹配分配格.

关于匹配分配格的一个性质的证明

一个有限分配格L称为匹配分配格当且仅当存在一个平面弱基本二部图G使得M(G)L。本文给出匹配分配格的一个性质及其证明。