最小生成樹問題的數學模型及其證明

孫培　劉凱

摘要：對圖論中賦權無向圖中最小生成樹問題的數學模型，分析了建立的過程，并證明了各邊不構成圈的一個等價條件，最后推廣到有向圖中，為用數學軟件求解圖論問題打下基礎。

關鍵詞：最小生成樹；賦權無向圖；賦權有向圖

中圖分類號：O221.4 文獻標識碼：A 文章編號：1009-3044（2014）28-6682-03

1 概述

迄今為止，許多學者對賦權無向圖中的最小生成樹問題已經進行了研究，提出了很多有效地求解算法，例如破圈法、避圈法等。其實最小生成樹問題也可以用整數規劃來表示，謝金星教授已給出了最小生成樹問題的數學表達式[1]，但其中的無圈等價條件沒有證明，并且無圈的等價條件還有許多種表示方法[2-9]，這些表示方法雖然數學表達式不同，但本質上是相同的。因此，該文將對無圈的等價條件給出證明，并給出賦權有向圖中最小生成樹問題的數學模型。

2 賦權無向圖中最小生成樹問題的數學模型

對一賦權無向圖G，我們假定G無重邊和環，即G為簡單圖，事實上，若G不是簡單圖，則有以下引理保證也可以求G的最小生成樹。

引理：給定賦權無向圖G，若G有重邊和環，則去掉后結果不會比原來的差。

證明：若G有環，直接去掉，若G有重邊，則將重邊按權從大到小排列，只留下邊權最小的邊，其余的重邊全去掉，得到新圖G*。由于最小生成樹問題是要求權最小的生成樹，故由G*的生成方式知，G*的最小生成樹就是G的最小生成樹。

我們用有向圖的思想來解決無向圖的最小生成樹問題。……