2014美国大学生数学建模竞赛中的图论

Graph theory in 2014 interdisciplinary contest(ICM)

本文建立了3个模型来解决如何基于节点间的相互关系来判断节点的重要性的问题。可根据不同节点间的相互关系建立不同性质的图,将节点本身的性质做处理并引入到建立的图中。建立不同模型对不同图中节点的度、PR值、介数等参数进行了计算,同时对节点本身的性质做了量化处理,综合以上两方面对节点的重要性给出了定量的判断。运用上述方法对Erds的合作网络和16篇相关联论文组成的网络进行建模分析,并选取北美地区的道路交通网进行模型推广,最后对上述模型的稳定性做了分析。

This paper proposed 3models to solve the problem of how to judge the importance of nodes based on the interrelation between nodes.Different types of graphs are set up according to different relationship between nodes.At the same time,the intrinsic characteristics of nodes are brought into set graphs.Different models are established to calculate nodes’ degree,PR value,betweenness and other parameters.It also quantifies intrinsic characteristics of nodes.Based on the two aspects above,the model gives a quantitative judgment on the importance of nodes.Using mentioned methods makes a modeling analysis of the co-authors network of Erds and the network consist of 16 related papers.A traffic network is also selected in North America as a real application to extend the models and analyzes the stability of the models above.