生成树

维基百科,自由的百科全书
跳到导航 跳到搜索
格子圖英语grid graph的生成樹(圖中的藍色粗線)

图论中,無向圖 G生成树是具有 G 的全部顶点,但边数最少的子圖。

表示顶点,表示边.若图 ,有,那么的生成树。

一个图的生成树可能有多个。