有向图的局部反魔幻标号

论文摘要

图的标号问题作为图论中的重要分支,其研究历史久远.图的染色问题就是一种特殊的图的标号问题,其历史可以追溯到图论发展的先导之一:四色猜想.一直以来,图的标号问题备受关注,它不仅在图论中扮演重要角色,而且在生命科学、社会科学等方面都有着广泛应用.图的标号问题本质上可以看作图的点集或边集到其他集合的映射（一般地,我们考虑整数集合）.本文中,我们研究的是有向图的局部反魔幻标号问题.对于一个顶点数为n,边数为m的有向图D,如果存在一个从D的边集到整数集{1,2,...,m}的双射,使得任意两个邻点的点和不同,则称图D是局部反魔幻的,这里点和是指该点所有入边的标号之和减去该点所有出边的标号之和.反魔幻标号问题自1990年由Hartsfield等人提出以来受到广泛关注,但仍未完全解决,其难点在于需要区分所有顶点的点和.而2006年Karonski等人提出的1-2-3猜想,考虑的则是邻点之间的点和问题.受此启发,我们开始研究图的局部反魔幻标号,进而推广到有向图.本文中,我们用概率方法证明了除了一些特例之外,任一有向图D都是局部反魔幻的.

论文目录

• 中文摘要
• 英文摘要
• 符号说明
• 第一章 绪论
•   1.1 基本概念
•   1.2 反魔幻标号的简介
•   1.3 本文主要结果
• 第二章 有向图的局部反魔幻标号
•   2.1 准备工作
•   2.2 定理证明
•     2.2.1 引理2.1.2的证明
•     2.2.2 引理2.1.3的证明
•     2.2.3 引理2.1.4的证明
•   2.3 结语
• 参考文献
• 致谢
• 攻读硕士学位期间完成论文情况
• 附件

文章来源

类型: 硕士论文

作者: 欧阳前程

导师: 王光辉

关键词: 有向图,局部反魔幻标号,概率方法

来源: 山东大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 山东大学

分类号: O157.5

总页数: 36

文件大小: 1314K

下载量: 21