毕业论文正文目录+正文模版.docVIP

目录 1. 基本概念……………………………………………………………………………1 1.1图的基本控制理论……………………………………………………………1 2. 主要结论……………………………………………………………………………1 参考文献…………………………………………………………………………………3 致谢………………………………………………………………………………………4 图的控制理论是图论的一个重要研究课题，控制函数是控制理论中的一个重要方面，而符号控制函数又是控制函数中首先研究的基本问题，本文将图的符号控制函数引申为弱符号控制函数，并在此基础上对图的弱符号控制函数及弱符号控制数进行了研究. 1．基本概念 设是一个简单图，对任意一点，点的开邻域是中所有与点相邻的顶点的集合，的闭邻域是，点在图的度，图的最大度和最小度分别用和表示.在不引起混淆的情况下，和简记为和.设，表示顶点分别在中的边集. 设，如果，则称为图的控制集.图的最小控制集中的点数称为图的控制数，用表示.[1] 对于图的一个函数，如果对于任意点均有，则是图的符号控制函数，对令，我们称为符号控制函数的权重.图所有的符号控制函数的权重的最小值称为图的符号控制数，记为.[2,3] 下面我们给出一些关于图的弱符号控制的概念. 1.1 图的基本控制理论 定义1 对于图的一个函数如果对任意点均有，那么是图的弱符号控制函数，对,令，称为弱符号控制函数的权重，对于图的一个弱符号控制函数，如果不存在图的另一个弱符号控制函数，满足对任意点，均有，则称是图的一个极小弱符号控制函数，图的所有极小弱符号控制函数中权重最小者称为图的最小弱符号控制函数，最小弱符号控制函数的权重称为图的弱符号控制数，记为. 2．主要结论 为方便起见，对图的一个弱符号控制函数，我们定义： . 定理1 设为图上的一个函数，则是图上的极小弱符号控制函数当且仅当对满足的任意点存在一点使得. 证明 设为图的一个极小弱符号控制函数，假设有一点满足,且对任意点,有.定义新函数,使得,且对任意点,有则对任意点,有对任意点,有，故是图的一个弱符号控制函数,且.这与为极小弱符号控制函数矛盾. 反之，设为图的一个弱符号控制函数，对满足的任意点均存在点,使得.假设不是极小弱符号控制函数，则存在另一个弱符号控制函数使得，即对任意点有，且存在点，使得 .由于存在点使得且对任意点，有，故有，这与为图的一个弱符号控制函数矛盾. 表1 图的节点及其对应的权值 3 1 4 显然，图的任意一个符号控制函数都是图的一个弱符号控制函数，故有如下定理： 定理2 对任意图，有. 定理3 图，为图的一个弱符号控制函数，对任意点，有 . 图1 图的节点对应的权值 参考文献 (单独一页写参考文献，注意删除此注释 [1] Ore O. Theory of Graphs [M], Amer. Math. Soc. Colloq. Pybl.38, American Mathe- matical Society, Providence, 1962. [2] O. Favaron. Signed domination in regular graphs[J]. Discrete Math., 1995, 158: 287-293. [3] 张忠辅, 徐宝根, 李银珍, 刘林忠. A note on the lower bounds of signed domination number of a graph[J]. Discrete Math., 1999, 195:295-298. [4] Jean Dunbar, Stephen Hedetniemi, Michael A Henning, Alice McRae. Minus domination in graphs[J]. Discrete Mathematics，1999,199:35-47. [5] J. Dunbar. Signed domination in graphs[J], Graphy Theory, Combinatorics and Applications, Wiley, New York, 1995,1:311-322. [6] 王朝瑞.图论.北京：高等教育出版社,1981. 1 各级标题均为小四黑体加粗；各级标题编号为“1.”“1.1.1” “1.1.2”样式；正文全部采用小四宋体，段落首行缩进2个字符；段前、段后设置为0，行距全部为1倍行距