Please wait a minute...
高校应用数学学报
高校应用数学学报  2019, Vol. 34 Issue (2): 239-    
    
度条件下的二部图的定向图
张雪飞, 郑素文, 夏静, 曹贻鹏, 许飞
陆军装甲兵学院基础部, 北京100072
Oriented graphs of the bipartite graph under degree
ZHANG Xue-fei, ZHENG Su-wen, XIA Jing, CAO Yi-peng, XU Fei
Basic Education Department, Army Academy of Armored Forces, Beijing 100072, China
 全文: PDF(332 KB)  
摘要： 二部图是具有二分类(X; Y )的简单偶图, 其中X的每个顶点与Y 的每个顶
点相连, 若jXj = m, jY j = n, 则这样的图记为Km;n. 该文研究了Kn;n的定向图.
对于非负整数a和b, 若存在满足每个顶点的入度或者是a或者是b的一个Kn;n的定向
图, 则存在非负整数s和t满足方程s + t = 2n 和as + bt = n2. 论文证明了如下结论:
设s和t是任意两个非负整数, 对于满足方程s + t = 2n和as + bt = n2的非负整数a和b,
存在Kn;n的定向图使得每个顶点的入度或者是a或者是b, 从而得到了上述必要条件
为Kn;n是[a; b]n可实现的充分条件.
关键词： 完全二部图;  定向;  入度;  算法    
Abstract: A graph is bipartite if its vertex set can be partitioned into two subsets X and Y such
that every edge has one end in X and one end in Y ; such a partition (X; Y ) is called a bipartition of the
graph. A simple bipartite graph with bipartition (X; Y ) is called a complete bipartite graph if every
vertex in X is adjacent to every vertex in Y . Furthermore, the complete bipartite graph is denoted
by K_{m;n} if |X| = m and |Y| = n. It has known that if the in-degree of each vertex in an oriented
graph of Kn;n is a or b, where a and b are two non-negative integers, then there exist two non-negative
integers s and t satisfying the equations s + t = 2n and as + bt = n^2. This paper investigates oriented
graphs of Kn;n, and proves the following results. Let s and t be two arbitrary non-negative integers.
For two non-negative integers a and b satisfying the equations s+t = 2n and as+bt = n^2, there exists
an oriented graph of Kn;n such that the in-degree of each vertex is a or b. This paper shows that the
necessary condition is also su±cient for a complete bipartite graph K_{n;n}.
Key words: complete bipartite graph    orientation    in-degree    algorithm
出版日期: 2019-07-05
CLC:  O157.6  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
张雪飞
郑素文
夏静
曹贻鹏
许飞

引用本文:

张雪飞, 郑素文, 夏静, 曹贻鹏, 许飞. 度条件下的二部图的定向图[J]. 高校应用数学学报, 2019, 34(2): 239-.

ZHANG Xue-fei, ZHENG Su-wen, XIA Jing, CAO Yi-peng, XU Fei. Oriented graphs of the bipartite graph under degree. Applied Mathematics A Journal of Chinese Universities, 2019, 34(2): 239-.

链接本文:

http://www.zjujournals.com/amjcua/CN/    或    http://www.zjujournals.com/amjcua/CN/Y2019/V34/I2/239

[1] 黄翰诚, 江渝. 一类改进DBSCAN算法及在金融中的应用[J]. 高校应用数学学报, 2020, 35(2): 169-180.
[2] 李瑞娟, 史 杰, 张新鸿. 准传递定向图上的Seymour点[J]. 高校应用数学学报, 2020, 35(2): 245-252.
[3] 庄丹, 刘友波, 马铁丰. 多变点检测问题的Shape-based BS算法[J]. 高校应用数学学报, 2019, 34(2): 151-.
[4] 赵远英, 徐登可, 庞一成. 联合均值与方差模型的Bayes分析[J]. 高校应用数学学报, 2018, 33(2): 157-166.
[5] 袁玉萍, 安增龙, 沙琪. 基于变分不等式的支持向量机优化算法研究[J]. 高校应用数学学报, 2017, 32(4): 455-461.
[6] 严羽洁. 单台机以总完工时间为目标的批排序问题[J]. 高校应用数学学报, 2017, 32(4): 462-472.
[7] 袁巧莉, 吴刘仓, 戴琳. 混合双重广义线性模型的参数估计[J]. 高校应用数学学报, 2017, 32(3): 267-276.
[8] 王璞玉 , 张海 , 曾锦山. 分布式$L_{1/2}$正则化[J]. 高校应用数学学报, 2017, 32(3): 332-342.
[9] 魏利, 张雅南. 无穷个$m$增生映射和逆强增生映射的隐式单调投影算法与$p$-Laplacian系统[J]. 高校应用数学学报, 2017, 32(2): 229-240.
[10] 朱志娥, 吴刘仓, 戴琳. 偏t正态数据下混合线性联合位置与尺度模型的参数估计[J]. 高校应用数学学报, 2016, 31(4): 379-389.
[11] 何朝兵. 删失截断情形下失效率变点模型的Bayes参数估计[J]. 高校应用数学学报, 2016, 31(4): 413-427.
[12] 张文帅, 张安, 陈光亭, 陈永. 一类无干涉作业的码头起重机调度问题的近似算法研究[J]. 高校应用数学学报, 2016, 31(3): 351-356.
[13] 何朝兵. 删失截断情形下Weibull分布多变点模型的参数估计[J]. 高校应用数学学报, 2015, 30(2): 127-138.
[14] 魏利, 陈蕊. 一类$p$-Laplacian型Neumann边值问题非平凡解的存在性及迭代算法研究[J]. 高校应用数学学报, 2015, 30(2): 180-190.