空圖
(重定向自空地區圖)
在圖論中,空圖可以代表無任何元素的圖(如空集合)[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]
空地區圖
參見
參考文獻
- ^ 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).