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

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

项目编号： No.11461038

项目类型： 地区科学基金项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 李敬文

作者单位： 兰州交通大学

项目金额： 36万元

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

中文关键词： 随机图；点可区别边全染色；邻点可区别边全染色；算法；复杂网络

英文摘要： 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.

英文关键词： random graph;vertex distinguishing edge (total) coloring;adjacent vertex distinguishing edge (total) coloring;algorithm;complex networks