图论中若干经典问题  

作　　者：武育杰 王浩 王宏立 王晓 

机构地区：[1]商洛学院数学与计算机应用学院,陕西商洛726000

出　　处：《电脑知识与技术》2023年第14期106-108,共3页Computer Knowledge and Technology

基　　金：大学生创新创业训练计划项目(S202211396022);商洛学院科研基金(22SKY111)。

摘　　要：现实生活中具有二元结构特征的问题都可以用“图”来建立其数学拓扑模型。图论作为理论工具,在复杂网络、大数据处理、化学分子结构、生物基因图谱、大规模集成电路等领域都有着广泛的应用。四色问题、中国邮递员问题和周游世界问题都是图论中的经典问题,在图论学科的发展过程中起着至关重要的作用。由四色问题衍生图的着色理论,已成为结构图论中最经典的部分;中国邮递员问题来源于图论中欧拉图问题,是中国学者研究图论的典型结果之一;周游世界问题即为图论中的哈密尔顿图问题,是一个经典的NP-难问题,对NP问题的研究起到了重要的促进作用。综述图论中经典问题的发展历史,可促进图论知识的普及,吸引更多研究者深入研究图论理论及其应用。

关 键 词：图论 四色问题 中国邮递员问题 哈密尔顿图 

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