随机图的点可区别染色算法及其在复杂网络中的应用研究

In 1993, A.C.Burris and R.H.Schelp have introduced the notation of vertex-distinguishing edge coloring of graphs and its conjecture. After 2002, Zhang et_al. has proposed several new concepts and methods of vertex-distinguishing coloring of graphs, and obtained many published results. This project mainly studies a series of vertex-distinguishing coloring algorithms of random graphs and random digraphs, and focus on the algorithms of vertex-distinguishing edge (total) coloring and adjacent vertex- distinguishing edge (total) coloring, respectively. Combining the spnning algorithms of simple connected graph with finite vertices, it is cheaked the correctness of total coloring conjecture、vertex-distinguishing edge (total) coloring and adjacent vertex- distinguishing edge (total) coloring conjecture within finite vertices. Furthermore, using the vertex-distinguishing chromatic number, color set, color sequence et_al. characterize the nodes coding peoperties and subgraph' structure properties of graphs, those characterizations will be applied to solve the problems such as searching special nodes, subgraph isomorphic and analysis of the structural evolution of complex dynamical networks; Based on the vertex-distinguishing coloring algorithms of random graphs, a new binary clooring method has been proposed the authors, this method not only can solve the vertex-distinguishing coloring of digraphs, but also can greatly reduce the complexity of maximum clique algorithm of graphs. Moreover, the method will be applied to solve the problem of complex network community mining.

1993年A.C.Burris和R.H.Schelp提出了图的点可区别边染色的概念及猜想，2002年以后张忠辅等人提出了一系列图的可区别染色新概念和新方法，取得了许多结果；本项目主要研究针对随机无向图和有向图的一系列可区别染色算法，重点研究点可区别边（全）染色算法和邻点可区别边（全）染色算法，结合有限点数所有简单连通图的生成算法，验证有限点数范围内全染色、邻点可区别边染色和邻点可区别全染色猜想的正确性；进而利用可区别染色的色数、色集合、色序列分布等结果设计节点编码和子图编码，用其来刻画图的节点特性和子图结构特性，并将它们应用于寻找特殊节点问题、子图同构问题以及动态复杂网络的结构演化分析问题；在随机图的可区别染色算法基础上，提出一种新的二元全染色法，该方法不仅可以求解随机有向图的可区别染色问题，还可以极大降低求解图的系列极大团算法的复杂度，并研究将该方法应用于复杂网络的社团挖掘问题。

随着大数据、云计算、计算机网络和通信技术的发展，越来越多的领域可以有效应用图染色和图标号技术来解决问题。现实中的问题转换成图论问题时，形成的网络图或为有向图或为无向图，基本上是随机图，而目前获得的有关图染色和图标号的结果绝大多数是针对特殊图的,本项目主要目的是研究计算机算法解决随机图的染色和标号问题，根据得到的结果验证相关猜想、提出新的猜想、算法证明一些有益的结果、将图论的理论研究与实际应用有效结合。项目围绕图染色概念邻点可区别边（全）染色、点可区别边（全）染色、均匀染色、可约染色、Smartachly染色、距离染色等总共发表标论文29篇，其中SCI 2篇，CSCD核心23篇，CSCD扩展4篇，已录用待发表7篇，已投稿待录用12篇；获软件著作权1项，申请中发明专利6项，图染色软件系统一套。