图边单射染色问题的复杂性及算法研究

摘要

图的单射染色问题是图论研究中的一个热点问题.在2002年，Hahn等人提出了一种新的染色方式-单射染色.单射染色的概念是源自于随机存取机的复杂性理论，可应用于纠错码理论.单射染色的概念与局部单射染色以及L(h，k)-标号的概念密切相关.给出一个简单图G=(V,E)，图G的顶点的单射染色是一个映射c:V→{1，2，…，k}，对于k∈N*，使得任意u,v∈V，且u，v之间相连一个公共的顶点，则c(u)≠c(v)，其中字母k表示这个映射点的单射染色数.设G=(V,E)是简单图，图G的边单射染色是一个映射d: E→{1，2，…，k}，k∈N*，对于任意e1，e2∈E，若e1，e2相邻一条公共边，则d(e1)≠d(e2)，其中字母k表示这个映射的边单射染色数.本文记图G的点（边的单射染色数）为xi(G)(xie(G))，是指使得上述染色条件成立且使用的颜色数最少的k值.很显然对顶点的单射染色有△(G)≤xi(G)≤|V(G)|(其中△(G)表示图G的点的最大度）. Hahn等人给出Xi(G)的上下界，并且证明了△(G)≤Xi(G)≤△(G)(△(G)-1），同时他们证明了点的单射染色是NP-完全的.Hell等人(2008)证明了在弦图上顶点的单射染色问题仍为NP-完全的，Jin等人(2013)证明了在平衡二部图上顶点的单射染色也是NP-完全的.受上述顶点的单射染色问题的启发，本文从边的角度去研究图的单射染色问题. 本文重点研究边的单射染色问题，首先研究该问题的计算复杂性，并对于度有界的可平面图给出了一个2-近似算法.针对一般图，本文描述了采用半张量积方法可给出边单射染色问题的精确算法，该算法适用于小规模问题. 本文共五章内容.第一章给出了文章用到的相关符号，基本概念以及已有的一些结论.在第二章中，研究了边单射染色问题的计算复杂性，阐明了边的单射染色问题是NP-完全的.在第三章中给出了度有界的可平面图边单射染色问题的2-近似算法.在第四章中，通过利用Wang等人(2012)提出的矩阵方法，得到边单射染色问题的精确算法，并且该方法也可以用来给出超图的最大匹配问题的精确算法.在文章的最后给出了一些可以进一步讨论的问题.

目录

声明

摘要

前言

第1章 绪论

1．1 基本概念

1．2 单射染色问题研究背景及已有的结论

第2章 关于边单射染色问题的NP-完全性

第3章 度有界可平面图边单射染色问题的近似算法

3．1 针对度有界可平面图边单射染色问题的分层方法及相关结论

3．2 度有界的可平面图边单射染色的近似算法及近似性能比分析

第4章 从矩阵的角度给出边的单射染色及相关问题的精确算法

第5章 可进一步研究的问题

参考文献

致谢