循环图和广义Petersen图的支配参数

论文摘要

图的支配问题是近年来图论中一个比较活跃的研究领域，在网络设计中有许多实际应用。比如在一个通讯网络的一些节点上放置发射器，要求每个发射器的节点一定和某个发射器的节点有一个直接的通讯线路。如何选择节点使得放置的发射器的数目最小，就是一个支配数问题。计算图的支配数问题属于NP-完全问题，因此至今只有少数类图的支配数被找到并证明。支配集是指集合S（?）V（G），对任意的顶点v∈V（G），都有v∈S，或着v和某点w邻接，且w∈S．即，S是一个支配集当且仅当N[S]=V（G）．如果支配集S的任何真子集都不是图G的支配集，则称支配集S为图G的一个极小支配集（minimal dominating set）．如果对图G的任意的一个极小支配集S*，满足|S*|≥|S|，则称极小支配集S为图G的一个最小支配集（minimum dominating set）．最小支配集S中所含元素的个数称为图G的支配数（dominationnumber），记作γ（G）．独立集是指集合S（?）V（G），集合S内不包含两个邻接的顶点。对于任何点集，如果其真子集是S，那么其都不是独立的，那么称S为图G的极大独立集（independent set）．如果对图G的任意一个极大独立集S*（maximal independent set），满足|S*|≤|S|，则称极大独立集S为图G一个最大独立集（minimum independent set）．最大独立集S中所含元素的个数称为图G的独立数（independence number），记作α（G）．本文利用计算机求出n和k比较小的广义Petersen图的独立数和循环图的支配数，并构造出相应的独立集和支配集，从中找出规律，推出n和k较大时的独立集和支配集，从而确定出循环图C（n；{1，k}），n=3k,4k的支配数上确界和广义Petersen图P（n，k），k=1，2，3，5的独立数的下确界。本文利用计算得的结果，并严格证明了循环图C（n；{1，k}），n=3k,4k的支配数的下确界和广义Petersen图P（n，k），k=1，2，3，5的独立数的上确界，从而得出了两者的准确值。

论文目录

• 摘要
• Abstract
• 引言
• 1 图论基础知识
• 1.1 图的基本概念
• 1.2 关于图的支配参数问题的进展
• 1.2.1 图的支配参数的定义
• 1.2.2 支配数国内外研究现状
• 1.2.3 独立数国内外研究现状
• 1.3 本文的工作
• 2 循环图的支配数
• 2.1 循环图的定义
• 2.2 循环图C（4k;{1,k}）的支配数
• 2.3 循环图C（3k;{1,k}）的支配数
• 2.4 循环图C（n;{1,k}）的支配数
• 3 广义Petersen图P（n,k）的独立数
• 3.1 广义Petersen图的定义
• 3.2 广义Petersen图P（n,k）,k=1,2,3,5的独立数
• 4 图的支配参数算法
• 4.1 回溯与分支限界技术
• 4.1.1 可能解集合
• 4.1.2 状态树
• 4.1.3 搜索策略与判定函数
• 4.1.4 子集树与排列树
• 4.2 支配数算法介绍
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢