灯笼图的奇优美标号

提出了灯笼图、多向灯笼图、复杂灯笼图,研究了它们的奇优美性,证明灯笼图是二分奇优美图、超级边魔幻图和超级反魔幻图.     

龙图的奇优美性

根据复杂网络研究的需要,定义(k,m)-奇优美龙图和一致(k,m)-龙图作为复杂网络的模型.这些龙图的奇优美性得到研究,其中证明方法可算法化.     

伪完全二分图PK_(n,n)奇优美标号的计算机实现

给出了伪完全二分图PK_(n,n)的定义及性质,提出了该类图的奇优美标号算法,证明了算法的正确性及时间复杂度,从而证明了伪完全二分图的奇优美性.并给出了伪完全二分图PK_(n,n),当n=3,4,5的一种标号方法.     

几类有趣图的奇优美性和奇强协调性

对于简单图G=〈V,E〉,如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1}满足:1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);2)max{f(v)|v∈V}=2|E|-1;3)对任意的e_1,e_2∈E,若e_1≠e_2,则g(e_1)≠g(e_2),此处g(e)=|f(u)+f(v)|,e=uv;4)|g(e)|e∈E}={1,3,5,…,2|E|-1},则称G为奇优美图,f称为G的奇优美标号.设G=〈V,E〉是一个无向简单图.如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1},满足:1)f是单射;2)■uv∈E(G),令f(uv)=f(u)+f(v),有{f(uv)|uv∈E(G)}={1,3,5,…,2|E|-1},则称G是奇强协调图,f称为G的.奇强协调标号或奇强协调值.给出了链图、升降梯等几类有趣图的奇优美标号和奇强协调标号.     

积图P_n×P_m的奇优美性和奇强协调性

给出了积图P_n×P_m的奇优美标号和奇强协调标号.     

太阳图的奇优美性和奇强协调性

设k_1,k_2,…,k_n是非负整数,C_n=v_v_2…v_nv_1是有n个顶点n条边的圈,则称图C_n+{v_1v_(11),v_1v_(12),…,v_1v_1k_1,v_2v_(21),…,v_2k_2,…,v_nv_(n1),…,v_nk_n}为(k_1,k_2,…,k_n)轮环图,简记为C(k_1,k_1,…,k_n).研究了太阳图1C_n的奇优美性及其奇强协调性,得到了太阳图1C_n在n为偶数时的奇优美标号算法和奇强协调标号算法,从而证明了太阳图1C_n在n为偶数时是奇优美图和奇强协调图的结论.     

图P^3n的奇优美标号算法

本文讨论了图P^3n的奇优美性,给出了图只奇优美标号算法．     

舵图的优美性

在“东南亚第十一届组合图论与计算机学术会议”上,K.M.Koh与D.G.Rogers等人提出了一个猜想:“对所有n≥3,舵图H_n为优美图”。本文证明了这一猜想为真。     

一类偶阶图的边优美性

本文讨论了一类偶阶图的边优美性。同时得到了完全图是边优美图的充要条件。     

优美图的一些性质

对于一个(p,q)-图G,如果存在一个单射.f:V(G)→{0,1,…,q},使得边标号集合{f(uv)| uv∈E(G)}={1,2,…,q},其中边标号为f(uv)=|f(u)-f(v)|,那么称G是优美图,并称.f是G的一个优美标号.通过研究若干优美图,得出一些优美图的性质.     

关于k-消去二分图的一些结果

图 G的一个 k-正则支撑子图称为 G的 k-因子 ,若对 G的任一边 e,图 G- e总存在一个 k-因子 ,则称 G是 k-消去图 .证明了二分图 G=( X,Y) ,且 | X | =| Y|是 k-消去图的充分必要条件是 k| S|≤ r1 + 2 r2 +…+ k( rk+… + rΔ) - ε( S)对所有 S X成立 .并由此给出二分图是 k-消去图的充分度条件 .     

关于扇和完全等二部图联图的边染色

得到了扇和完全等二部图联图的边色数.     

关于扇和完全等二部图联图的点可区别边染色

通过结构分析的方法,考虑各种不同情况,给出了一类联图的点可区别的边染色方法,并得到了它的点可区别的边色数.     

一种基于二部图的试题知识点标注方法

针对在线教育中试题知识点自动标注问题,本文提出了一种基于二部图的试题知识点标注方法。首先,为了合理划分知识点粒度,本文构建了知识点知识图谱来融合知识点;其次,基于教材等语料抽取知识点与特征词二部图和试题与特征词二部图,并利用TF-IDF公式计算知识点与特征词、试题与特征词之间的边权,以构建试题-知识点二部图模型;再次,提出词频加权的相似性度量方法计算试题和知识点之间的相似度,将相似度最高的知识点作为试题知识点标签。最后,以某在线教育平台提供的高中历史试题为实验数据集进行数值实验,实验结果表明该方法的效果显著优于朴素贝叶斯、K最近邻、随机森林以及支持向量机。     

A Distributive Lattice on the Set of Perfect Matchings of a Plane Bipartite Graph

Let G be a plane bipartite graph and M(G) the set of perfect matchings of G. The Z-transformation graph of G is defined as a graph on M(G): M,MM(G) are joined by an edge if and only if they differ only in one cycle that is the boundary of an inner face of G. A property that a certain orientation of the Z-transformation graph of G is acyclic implies a partially ordered relation on M(G). An equivalent definition of the poset M(G) is discussed in detail. If G is elementary, the following main results are obtained in this article: the poset M(G) is a finite distributive lattice, and its Hasse diagram is isomorphic to the Z-transformation digraph of G. Further, a distributive lattice structure is established on the set of perfect matchings of any plane bipartite graph.     

关于二部图Km1m2-Hm2的升分解

在文献[2]中作者定义了图的一种新分解-升分解(Ascending subgraph Decomposition简记为ASD)，并提出了一个猜想：任意有正数条边的图都可以升分解．本文主要证明了二部图Km1m2-Hm2(m1≥m2)可以升分解，其中Hm2是至多含m2条边的Km1m2的子图．     

关于奇强协调图的一些结果

对于一个(p,q)-图G,如果存在一个单射f:V(G)→{0,1,…,2q-1},使得边标号集合{f(uv)|uv∈E(G)}={1,3,5,…,2q-1},其中边标号为f(uv)=f(u)+f(v),那么称G是奇强协调图,并称f是G的一个奇强协调标号.通过研究若干奇强协调图,得出一些奇强协调图的性质.     

关于二部图K(m,n)-2的色唯一性

设Ｋ（ｍ，ｎ）－２表示从完全二部图Ｋ（ｍ，ｎ）中删去任意２条边所得之图．本文证明了：１．若ｎ≥ｍ≥３，且ｎ＋ｍ＞(（ｎ－ｍ）^２＋８)^1/2＋１/２（ｎ－ｍ）^２＋４，则Ｋ（ｍ，ｎ）－２是色唯一图；２．当ｍ≥３时，Ｋ（ｍ，ｍ）－２，Ｋ（ｍ，ｍ＋１）－２和Ｋ（ｍ，ｍ＋２）－２均是色唯一图．     

Schrijver图SG(2k+2,k)的Hamilton性

通过图G的每个顶点的路称为Hamilton路,通过图G的每个顶点的圈称为Hamilton圈,具有Hamilton圈的图G称为Hamilton图.1952年Dirac曾得到关于Hamilton图一个充分条件的结论:图G有n个顶点,如果每个顶点υ满足:d(υ)≥n/2,则图G是Hamilton图.本文研究了Schrijver图SG(2k+2,k)的Hamilton性,采用寻找Hamilton圈的方法得出了Schrijver图SG(2k+2,k)是Hamilton图.