信道分配与二部图的非正常边染色  

Channel Allocation and Improper Edge Colorings of Bipartite Graphs

作　　者：张昊[1] 赵燕 Zhang Hao;Zhao Yan(School of Mathematics and Physics,Nanjing Institute of Technology,Nanjing 211167,China;School of Mathematical Science,Nanjing Normal University,Nanjing 210023,China;Department of Mathematics,Taizhou University,Taizhou 225300,China)

机构地区：[1]南京工程学院数理学院,江苏南京211167 [2]南京师范大学数学科学学院,江苏南京210023 [3]泰州学院数理学院,江苏泰州225300

出　　处：《南京师大学报（自然科学版）》2023年第3期20-25,共6页Journal of Nanjing Normal University(Natural Science Edition)

基　　金：国家自然科学基金项目(11901426);江苏省高校“青蓝工程”资助项目.

摘　　要：确定二部图的边染色数和极小边染色是计算机领域的一个经典算法问题.该问题在信道分配和计算机科学的众多方面有广泛应用,并且是NP完全的.本文首先从二部图结构入手,利用非正常边染色定义,采用构造方法得到亏格为1和2时部分完全二部图的非正常边染色数,给出相应算法和复杂性分析,然后将其转化为网络中的信道数量.Finding the edge chromatic number and minimal edge chromatic in bipartite graphs is a well-known algorithm problem in the computer field.It has wide application in channel allocation and many aspects of computer science and it is NP complete.From the structure of bipartite graphs and the definition of improper edge colorings,this paper presents some chromatic index of bipartite graphs when the deficiency is 1 or 2 and the algorithm and complexity analysis are also given.What’s more,transforms it to the numbers of channel in a network.

关 键 词：信道分配 二部图 非正常边染色 NP完全 

分 类 号：O157.6[理学—数学]