关于Ghouila—Houri定理的注记

Ghouila—Houri 得到强连通有向图 D 是有向 H 图的充分条件.强连通有向图 D 中,若对任一点 V.d((?))≥p,则 D 是有向 H 图。任一有向图都可以看作某个相应马尔可夫链的转移概率图。我们应用马尔可夫链理论得到:强连通有向图 D 中,如果 min{δ~+(D),δ~-(D)}≥p/d,则 D 是有向 H图。这里 d 是马尔可夫链周期,因此 d≥2。当 d=2时,即是 Ghouil—Houri 定理条件。     

立方图的可圈性

图的可圈性是哈密尔顿性的一个推广.设G是有向图,如果对G的每一个定向D,都存在S(D) V(G)使在D中改变所有恰与S(D)中一个顶点相关联的弧的方向后所得到的图为有向哈密尔顿图,则称G为可圈图.证明至少含5个顶点的连通图G的立方图是可圈图当且仅当G不同构于任何一条偶路.该结果改进了Klostermeyer的3个定理.     

关于有向图着色的Brooks定理

本文证明了Brooks定理在有向图上的一个推广:设D是简单的强连通图。如果D不是有向圈或者C_(2n+1)~*或者K_n~*则d_k(D)≤min{△-(D),A~+(D)}。此处d_k(D)表示D的有向色数。     

关于“A NOTE ON CHRO MATIC UNIQUENESS OF GRAPHS”一文的注记

G.L.Chia在“A Note on Chromatic Uaipueness of Graphs”一文中(J.Graph Theory,10(1986),541—543),给出了色唯一图的几条性质,回答了Whitehead和Zhao提出的一个猜想。原文对定理的证明如下: 定理设G是由两个块H和K_2所组成的图,那么,G是色唯一的当且仅当H是色唯一的和顶点可迁的。     

有向线图存在Hamilton圈和Hamilton路的一个充要条件

有向图D的有向线图是以A（D）为顶点集，弧集为{（xy，yz），xy∈A（D），yz∈A（D）}的有向图，用L（D）表示D的有向线图。文章证明了连通有向线图存在Hamilton圈当且仅当它有圈因子；连通有向线图存在Hamilton路当且仅当它有1-路圈因子。     

关于两个三角形成正交透视的几年定理及其应用

几何学中纯结合关系的最重要成果之一是由法国数学家 Desargues发现的联系两个三角形的定理 :两个三角形有透视心当且仅当它们有透视轴 .本文在此基础上提出了两个三角形成正交透视的定义 ,得到了成正交透视的两个三角形的一个结果 :如果两个三角形是正交透视和透视的 ,则透视心和两个正交透视心共线且垂直于它们的透视轴 ,可看作是 Euler定理的推广     

关于团图的一个注记

在这个注记中,我们将[1]定理3·1改进成:图G满足条件2~(|G|-ω(G))=|K(G)|当且仅当G是Turan图T(|G|,ω(G))的子图且同时G包含一个子图同构于[1]定理2·3的证明中引入的Hedman图H(|G|,ω(G))。我们还指出[1]定理3·2是错误的。事实上我们进一步证明了:如果图G满足条件2~(|G|-ω(G))=|K(G)|,则或者K(G)是Neumann图或者K(G)是完全图,并且K(G)为完全图当且仅当Δ(G)=|G|-1。     

哈密顿竞赛图的一个充要条件

设T=(V,A)是一个竞赛图,记■本文证明了张存铨同志提出的下列问题:定理竞赛图T有哈密顿回路当且仅当T中存在由R的一个顶点到S的一个顶点的一条道路。证:必要性是显然的。充分性。由定理的条件知,■于是T中有回路。     

拓展教学内容,培养学生能力——谈谈行列式一个定理的教学

<正> 行列式是高等代数或线性代数课程中的重要内容。关于行列式的展开,有几个重要的定理,为了叙述方便,现列示如下:定理1:n(n>1)阶行列式D等于行列式的任意一行(列)元素与它们对应的代数余子式乘积的和。定理2:n(n>1)阶行列式D的某行(列)的元素与另一行(列)的对应元素的代数余子式乘积的和等于0。定理3:(拉普拉斯定理):在n(n>1)阶行列式D中,任意取定k(1≤k1)阶行列式D中,任意取定k(1≤k相似文献   

Winkler地基上周期性Euler梁的弯曲振动能带特性

 利用传递矩阵法并结合Bloch定理,分析了周期性Euler梁在Winkler地基上的弯曲振动能带结构,以及地基参数、结构参数对弯曲振动带隙的影响。结果表明,Winkler地基的存在,使得周期性Euler梁的弯曲振动能带结构向高频方向提升,第1弯曲振动带隙从0Hz开始,且随着地基反应模量的增加,第1弯曲振动带隙宽度增大,第2弯曲振动带隙宽度减小;随着长度率的增加,梁的第1弯曲振动带隙和第2弯曲振动带隙宽度均减小。与均质Euler梁对比,周期性Euler梁在Winkler地基上具有更好的隔振特性,对低频弯曲振动有较好的阻隔效果。     

边-超欧拉图的一个度数和条件

图G称为边-超欧拉图,如果对于它的任一条边e,都有欧拉生成子图H包含e．给出了边-超欧拉图的一个度数和条件,即：设G是2一边连通的n个顶点的简单图,如果n≥100并且对于图G的任意两个不相邻的顶点u和v都有d（u）＋d（v）≥2/5n,那么对于图G的任意一条边e,或者G有欧拉生成子图H包含e,或者G（G关于e的剖分图）可以被收缩成K2.3或K2.5．     

广义棱柱和补棱柱中的超欧拉图

对于一个图G,它的顶点标号为1,2,…,n,S_n是在{1,2,…,n}上的n次对称群,α∈S_n是一个置换,图G的α-广义棱柱,记作α(G),是指图G的2个复制,G_x和G_y,连同所有置换边(x_i,y_(α(i))(1≤i≤n)所构成的图.图G的补棱柱,记作G G,同构于由G和G的补图G的不交并,再加上一个连接G和G对应顶点的完美匹配构成的图.如果图G有一个生成欧拉子图,那么称G是超欧拉图.研究了完全二部图、路和圈的广义棱柱和补棱柱是超欧拉图的充要条件.     

基于边被收缩图的有向有环图有向割集求解算法

为了提高有向有环图有向割集生成算法的效率,通过收缩有向有环图环路中的边将有向有环图转换成带收缩顶点的有向无环图,并使得生成有向无环图有向割集的算法可以生成有向有环图的有向割集.在理论上分析了本文提出的算法的时间复杂度和空间复杂度,并进行了实验测试.理论分析和实验测试的结果表明本文提出的算法是很高效的.     

3-方体的一个性质

在相关文献中,引入了α-子图的概念来探索超欧拉图的极大欧拉生成子图的边数,并且证明了2-方体在加入一条新边的情况下是一个3/5-子图．研究了3-方体,证明了3-方体在加入一条新边的情况下是一个9/13-子图.     

具有状态支付向量的有向图上的动态对策

通过在有向图的每个状态结点处引入状态支付向量,运用C．Berge关于图上对策中策略的概念,在有限图上研究动态对策。在非合作情形,证明了具有状态支付向量的有向图上对策的精练均衡的存在性定理。在合作情形,通过建立有向图上局与对策树上路径之间的对应关系,将有向图上的对策转化为对策树,并给出了特征函数的算法以及以Shapley向量作为合作解的计算示例。     

基于有向图的关联规则算法

提出了一种基于有向图的关联规则挖掘算法，采用了垂直二进制位图映射数据库，根据垂直二进制位图来生成有向图，将频繁项的二进制位串作为有向图的权值，通过分析有向图生成最大频繁项集，并给出了最大频繁项集挖掘算法的优势。     

冠状系统R-旋转图连通的充要条件

六角系统的R-旋转图是1棵有向根树,但冠状系统的R-旋转图是一个有向森林.其底图不一定连通.如果冠状系统是基本的,已经证明其R-旋转图至少包含2棵有向根树.利用有向根树问的一种乘法运算,证明了一个冠状系统的R-旋转图为1棵有向根树当且仅当该冠状系统的每个基本分支都是六角系统.     

加权有向图生成算法研究及其计算机实现

提出了加权有向图的生成算法及其在计算机中的实现，定义了加权有向关联矩阵，并据该矩阵解决了加权有向图的生成、绘制问题，从而为可视化教学提供了基础.     

求可达矩阵的Warshall算法

给出并证明了确定内部独立的递阶层次结构的矩阵方法。将系统用有向图描述，利用集合论中求关系问包的Ｗａｒｓｈａｌｌ算法实现了求可达矩阵。在决策因素很多且问题很复杂时，可以通过有向图的可达矩阵来确定系统的层次结构。     

一种新的拓扑排序方法──枚举拓扑排序

拓扑排序属于图论中有向图问题，拓扑排序的输出结果与输入有向边的次序有关．因此需要多次输入不同有向边，经组合才能得到拓扑排序的所有解．本文提出一种新的拓扑排序方法，可一次输入任意一组有向边，即能自动得到所有解．