空圖
在圖論中，空圖可以代表無任何元素的圖（如空集合）[1]、階數為0的圖（如K0）或雖有頂點但沒有任何邊的圖（如無邊圖，英語：edgeless graph）。
性質
[編輯]若空圖包含了個頂點，則其可以記為。[2]:329 空圖的大小（即邊的數量）恆為0，[3]:45 然而空圖的階數（即頂點的數量）不一定為0。[3]:44 階數為零的空圖又稱為零階圖[4]，階數不為零的空圖（即有頂點存在的圖）又稱為無邊圖。[5]
零階圖
[編輯]| 零階圖 (空圖) | |
|---|---|
| 頂點 | 0 |
| 邊 | 0 |
| 圍長 | |
| 自同構群 | 1 |
| 色數 | 0 |
| 色指數 | 0 |
| 屬性 | 積性 對稱 樹寬值為-1 |
在圖論中，零階圖（K0）是一種沒有任何頂點的圖，因此其階數為0，且不存在任何邊。零階圖是階數為零的正則圖，然而其不存在頂點，因此也無法探討其頂點的分支度，因此，部分研究不會將零階圖列如圖的探討範圍中[6]。零階圖是否有效取決於其上下文對這種圖論結構的描述方式。就積極的一面而言，零階圖做為圖論定義下遵守良序原則的定義，即有序對(V,E)在V和E皆為空的情形，可用於證明其作為數學歸納法的自然基本情況；類似地，在遞歸定義的資料結構中，零階圖可用於定義遞歸基本情況，例如在二元樹的定義中，將空樹缺失邊的子樹視為零階圖，這樣就能確保這個二元樹中每個節點都有2個子樹[7]。在消極的一面而言，若將零階圖視為正式的圖會成為許多明確的圖論屬性公式的例外，導致許多圖論公式需要針對零階圖定義例外情況[6]。為了避免這種情況，一般圖論的「任意圖」術語，除非上下文有明確說明，否則應當不包含零階圖，即「任意圖」應代表「至少存在一個頂點的圖」。[8][6]
無邊圖
[編輯]在圖論中，無邊圖（Edgeless graph）是指沒有邊的圖。其可以有任意數量的頂點，然而每個頂點間皆無邊來做相連。n個頂點的無邊圖稱為n階無邊圖，一般用記為。在不允許零階圖（K0）的上下文中，無邊圖有時被稱為空圖。[8][6]
空地區圖
[編輯]在圖論中，空地區圖（null map）是指對應集合為空集的地區圖[9]，有時用於證明不存在其他同態圖的方式[10]。
參見
[編輯]參考文獻
[編輯]- ^ Harary, Frank and Read, Ronald C. Is the null-graph a pointless concept?. Graphs and combinatorics (Springer). 1974: 37–44.
- ^ Eric Delhez, Algèbre, Tome 2, notes de cours, édition 2012-2013.
- ^ 3.0 3.1 Didier Müller, Introduction à la théorie des graphes （頁面存檔備份，存於網際網路檔案館）, Cahier n° 6, Commission Romande de Mathématiques, 2012.
- ^ Annatala Wolf. Trees and XML. Ohio State University. [2021-08-11]. （原始內容存檔於2021-08-11）.
- ^ Weisstein, Eric W. (編). Edgeless Graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）.
- ^ 6.0 6.1 6.2 6.3 Weisstein, Eric W. (編). Null Graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）.
- ^ Abstract Data Types (PDF). National Chung Hsing University. [2021-08-11]. （原始內容存檔 (PDF)於2021-08-11）.
- ^ 8.0 8.1 Weisstein, Eric W. (編). Empty Graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）.
- ^ Handbook of Mathematics for CS. University of Dublin. 2005.
- ^ 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).