生成子圖(spanning subgraph)是1993年公布的數學名詞。
基本介紹
- 中文名:生成子圖
- 外文名:spanning subgraph
- 所屬學科:數學
- 公布時間:1993年
生成子圖(spanning subgraph)是1993年公布的數學名詞。
生成子圖(spanning subgraph)是1993年公布的數學名詞。公布時間1993年,經全國科學技術名詞審定委員會審定發布。出處《數學名詞》第一版。1...
支撐子圖(spanning subgraph)亦稱生成子圖,圖論中一類圖的統稱。由一個圖的全部頂點及連結這些頂點的部分邊構成的圖稱為原圖的支撐子圖。若支撐子圖是樹,則為支撐樹。在圖論中,解決一些懸而未決的問題往往首先從樹這類圖入手。許多問題...
子圖的定義 設 為兩個圖(同為無向圖或同為有向圖),若 且 ,則稱G'是G的子圖,G是G‘的母圖,記作 ,又若 且 ,則G'稱是G的真子圖,若 ,則稱G'是G的生成子圖。設 為一圖, 且 ,稱以 為頂點集...
生成子圖(Spanning Subgraph)定義:生成子圖G’中頂點個數V’必須和原圖G中V的數量相同,而E’∈E即可。導出子圖 (Induced Subgraph)定義:導出子圖G’,V’∈V,但對於V’中任一頂點,只要在原圖G中有對應邊,那么就要在E’中...
spanning tree)是一個管理學術語。圖的生成樹( spanning tree):若一個無向圖G的生成子圖是一棵樹,則稱之為G的生成樹。連通且不含圈的無向圖如城市煤氣、自來水管道網路,鐵路的專用線網等,都可以用樹的形式來表示。
(共n-1條)組成的極小連通子圖就是生成樹。(源點是生成樹的根)通常,由深度優先搜尋得到的生成樹稱為深度優先生成樹,簡稱為DFS生成樹;由廣度優先搜尋得到的生成樹稱為廣度優先生成樹,簡稱為BFS生成樹。注意:①圖的廣度優先生成...
算法的思路比較簡單,但是對於包含較多圖的輸入集合來說執行效率非常低,主要是因為挖掘算法在生成候選子圖時要判斷是否存在相同的k-1子圖,當川尺大時,這需要花費很長時間。並且通過每次添加一個頂點來產生候選子圖時會產生許多冗餘k+l...
第五節 對生成子圖的連通性檢測和補正/107 第六節 本章小結/110 第六章 應急物流車輛監控導航實驗平台開發/112 第一節 應急物流車輛監控導航實驗平台總體設計/112 第二節 嵌入式試驗開發板的選擇和調試/116 第三節 嵌入式操作...
生成子圖(Spanning Sub-Graph):指滿足條件V(G') = V(G)的G的子圖G'。導出子圖(Induced Subgraph):以圖G的頂點集V的非空子集V1為頂點集,以兩端點均在V1中的全體邊為邊集的G的子圖,稱為V1導出的導出子圖;以圖G的...
為連通子圖α的秩,則 就是秩多項式,其中,表示由S所成的支撐子圖的秩。(3°) 若令 ,其中 為連通子圖α的邊數,則 就是色多項式,事實上,記 ,並以 表示H的生成子圖的秩,則上式可改寫為 這就是色多項式的展開式(極易由...
若圖G= 〈V,E〉的生成子圖T是樹,則T稱為G的生成樹。圖G有生成樹若且唯若G是連通圖。利用“破迴路法”可求給定連通圖的生成樹。這僅需每次刪去一條迴路上的一條邊(保留端點),直到不再含有迴路為止,就得到一棵生成樹。利用...
若連通圖G的生成子圖是一棵樹,則稱這棵樹為G的生成樹。設G是一個 -連通圖,則相對於它的任何一個生成樹T,含有m-(n-1)個補樹邊,根據定理1中命題(4),對每條補樹邊e,T+e有且僅有一個圈,因此G中至少含有m-n+1個圈...
,歸納地定義G的連通子圖序列 如下: ;若 不是G的生成子圖,設 是在G中而不在 中的一個頂點,則存在從 到 的邊的不重路 和 ,定義 ,由於 ,這個序列必然終止於G的一個生成子圖 。現依次給每個 定向:首...
與G的生成子圖對應。引理1 設 ,則 (1)若G滿足(P₁),則H滿足(P₁);(2)若G滿足(P₂),則H滿足(P₂)。引理2(Fulkerson,1971;Lovász,1972)設G滿足(P₂),令 ,那么由G滿足(P₃)可推出日滿足(P₃)。引...
成功解決這個任務展示了該模型結合了多種能力:(1)識別圖中所描繪的函式;(2)通過逆向圖形推斷生成子圖的代碼;(3)按照指示將子圖放置在期望的位置;(4)抽象推理(推斷指數圖必須保持在原來的位置,因為正弦圖必須為三維圖騰出...
枝杈樹:若圖 G 的生成子圖 H 是樹,則稱 H 為 G 的枝杈樹或支撐樹。最小枝杈樹:設G=[V,E]是一個無向圖,對每一條邊 ∈E有一個長度C( ) ≥0,G的任意支撐樹T各條邊的長度之和稱為樹T的長度,記為C(T)。長度...
子圖存在性問題是圖論中重要的研究內容之一。 而頂點不交子圖的存在性問題是其中一個主要的方向。這一方面的研究更多的是子圖結構類型相同的情況,如圖中包含因子(生成正則子圖)的各種條件的研究.關於子圖結構類型不相同的情況還有許多問題沒...
X... X Gk,則稱G;(1<i<k)是G的素因子.若兩個圖沒有相同的素因子,則稱這兩個圖為互素圖。若一個圖G的支撐子圖的每一個節點在這生成子圖上的次均不大於2,則這個支撐子圖稱為G的線性子圖。