生成樹維基百科,自由的 encyclopedia 在圖論中,無向圖 G 的生成樹(英語:Spanning Tree)是具有 G 的全部頂點,但邊數最少的連通子圖。[1] 此條目需要補充更多來源。 (2020年3月8日) 格子圖(英語:grid graph)的生成樹(圖中的藍色粗線) 以 V {\displaystyle V} 表示頂點, E {\displaystyle E} 表示邊,若圖 G = ( V ( G ) , E ( G ) ) {\displaystyle G=(V(G),E(G))} 和樹 T = ( V ( T ) , E ( T ) ) {\displaystyle T=(V(T),E(T))} ,有 E ( T ) ⊂ E ( G ) {\displaystyle E(T)\subset E(G)} 和 V ( G ) = V ( T ) {\displaystyle V(G)=V(T)} ,那麼 T {\displaystyle T} 是 G {\displaystyle G} 的生成樹。 一個圖的生成樹可能有多個。
在圖論中,無向圖 G 的生成樹(英語:Spanning Tree)是具有 G 的全部頂點,但邊數最少的連通子圖。[1] 此條目需要補充更多來源。 (2020年3月8日) 格子圖(英語:grid graph)的生成樹(圖中的藍色粗線) 以 V {\displaystyle V} 表示頂點, E {\displaystyle E} 表示邊,若圖 G = ( V ( G ) , E ( G ) ) {\displaystyle G=(V(G),E(G))} 和樹 T = ( V ( T ) , E ( T ) ) {\displaystyle T=(V(T),E(T))} ,有 E ( T ) ⊂ E ( G ) {\displaystyle E(T)\subset E(G)} 和 V ( G ) = V ( T ) {\displaystyle V(G)=V(T)} ,那麼 T {\displaystyle T} 是 G {\displaystyle G} 的生成樹。 一個圖的生成樹可能有多個。