空图

维基百科,自由的百科全书

图论中,空图可以代表无任何元素的图(如空集合)[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).