跳至內容

空圖

維基百科,自由的百科全書

圖論中,空圖可以代表無任何元素的圖(如空集合)[1]、階數為0的圖(如K0)或雖有頂點但沒有任何邊的圖(如無邊圖,英語:edgeless graph)。

性質

[編輯]

若空圖包含了個頂點,則其可以記為[2]:329 空圖的大小(即邊的數量)恆為0,[3]:45 然而空圖的階數(即頂點的數量)不一定為0。[3]:44 階數為零的空圖又稱為零階圖[4],階數不為零的空圖(即有頂點存在的圖)又稱為無邊圖。[5]

零階圖

[編輯]
零階圖 (空圖)
頂點0
0
圍長
自同構群1
色數0
色指數0
屬性積性英語Integral graph
對稱英語Symmetric graph
樹寬值英語Treewidth為-1

在圖論中,零階圖(K0)是一種沒有任何頂點的圖,因此其階數為0,且不存在任何邊。零階圖是階數為零的正則圖,然而其不存在頂點,因此也無法探討其頂點的分支度,因此,部分研究不會將零階圖列如圖的探討範圍中[6]。零階圖是否有效取決於其上下文對這種圖論結構的描述方式。就積極的一面而言,零階圖做為圖論定義下遵守良序原則英語Well-ordering_principle的定義,即有序對(V,E)在V和E皆為空的情形,可用於證明其作為數學歸納法的自然基本情況;類似地,在遞歸定義的資料結構中,零階圖可用於定義遞歸基本情況,例如在二元樹的定義中,將空樹缺失邊的子樹視為零階圖,這樣就能確保這個二元樹中每個節點都有2個子樹[7]。在消極的一面而言,若將零階圖視為正式的圖會成為許多明確的圖論屬性公式的例外,導致許多圖論公式需要針對零階圖定義例外情況[6]。為了避免這種情況,一般圖論的「任意圖」術語,除非上下文有明確說明,否則應當不包含零階圖,即「任意圖」應代表「至少存在一個頂點的圖」。[8][6]

無邊圖

[編輯]

在圖論中,無邊圖(Edgeless graph)是指沒有邊的圖。其可以有任意數量的頂點,然而每個頂點間皆無邊來做相連。n個頂點的無邊圖稱為n階無邊圖,一般用記為。在不允許零階圖(K0)的上下文中,無邊圖有時被稱為空圖。[8][6]

空地區圖

[編輯]

在圖論中,空地區圖(null map)是指對應集合為空集的地區圖[9],有時用於證明不存在其他同態圖的方式[10]

參見

[編輯]

參考文獻

[編輯]
  1. ^ Harary, Frank and Read, Ronald C. Is the null-graph a pointless concept?. Graphs and combinatorics (Springer). 1974: 37–44. 
  2. ^ Eric Delhez, Algèbre, Tome 2, notes de cours, édition 2012-2013.
  3. ^ 3.0 3.1 Didier Müller, Introduction à la théorie des graphes頁面存檔備份,存於網際網路檔案館), Cahier n° 6, Commission Romande de Mathématiques, 2012.
  4. ^ Annatala Wolf. Trees and XML. Ohio State University. [2021-08-11]. (原始內容存檔於2021-08-11). 
  5. ^ Weisstein, Eric W. (編). Edgeless Graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英語). 
  6. ^ 6.0 6.1 6.2 6.3 Weisstein, Eric W. (編). Null Graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英語). 
  7. ^ Abstract Data Types (PDF). National Chung Hsing University. [2021-08-11]. (原始內容存檔 (PDF)於2021-08-11). 
  8. ^ 8.0 8.1 Weisstein, Eric W. (編). Empty Graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英語). 
  9. ^ Handbook of Mathematics for CS. University of Dublin. 2005. 
  10. ^ Cadavid, Paula and Rodino Montoya, Mary Luz and Rodriguez, Pablo M. The connection between evolution algebras, random walks and graphs. Journal of Algebra and Its Applications (World Scientific). 2020, 19 (02).