Remove ads

在數學中,將一個無向圖按照某種分佈隨機分配邊權後可得一個新圖,後者的最小生成樹便稱為隨機最小生成樹

若給定的圖是n個頂點的完全圖,且邊權的分佈函數處處連續並在原點處導數D > 0,則隨機生成樹的邊權總和有上界C,後者不隨n的增長而增長。更精確地講,n趨向於無窮大時,C趨向於ζ(3)/D,其中ζ黎曼ζ函數ζ(3)阿培里常數。例如,若邊權均勻分佈於單位區間,則其導數為D = 1n趨向於無窮大時,C恰趨向於ζ(3)[1]

網格圖英語grid graph的隨機生成樹在多孔介質中液態流體的入侵滲透英語invasion percolation模型[2]以及迷宮生成英語maze generation算法[3]中都有所應用。

參考資料

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Remove ads