图论模型的建立与转化

图论模型的建立与转化 关键字：图论模型、建立、转化 摘要 本文主要写图论模型的建立与转化，共分四部分： 第一部分引言说明了图论建模在整个信息学竞赛中的地位，以及图论模型与其它数学模型的异同，并指出很有研究总结图论建模的思想、方法及技巧的必要。 第二部分提出了图论模型建立中的两个要点：对原型中的要素进行适当的取舍和选择合适的理论体系，并分别举例加以详细分析，然后从中总结出了图论建模的总的原则：准确、清晰、简明。 第三部分主要讨论了在图论模型的转化中，应用得较为广泛的两种方法：拆分转化和补集转化，并着重分析了前者。文中把前者分为三类：点à边、点à点、边à边，其中详细分析了第二类。 第四部分总结了全文，并指出了进一步研究图论模型的必要性。