图属性
在图论中,图属性(graph property)或图常量(graph invariant,又称图不变量)是图的一种性质,它只取决于其抽象结构,而不取决于图的表示形式如特定的图标号或图绘制形式。[1]
定义
虽然图的绘制和图的表示都是图论中的有效课题,但为了只关注图的抽象结构,图属性被定义为在图的所有可能同构下仍存在的属性。换句话说,它是图本身的属性,而不是其特定的绘制或表示形式。非正式用法中,术语“常量”用于定量表示其属性,而“属性”用于定性描述图的特征。例如,语句“图没有度为1的顶点”为“属性”用法,而“图中度为1的顶点数量”为“常量”用法。
更正式地说,图属性是指具有相同属性的一类图,其任何两个同构图要么都属于该类,要么都不属于该类。[1]等价来说,可以使用这类图的指示函数(将图转化为布尔值的函数,属于该类的图为真,否则为假)将图属性形式化,其中任何两个同构图必须具有相同的函数值。类似地,图常量或图参数可以形式化为一个函数,还可从图推广到更广泛的值类,如整数、实数、数字序列或多项式,这些值对应的图其任何两个同构图都具有相同的值。[2]
图属性的特征
对于图上定义的某些自然偏序关系或预序关系,许多图属性与其相关性较高:
- 如果具有P属性的图其每一个诱导子图都具有P属性,则称该图是遗传的。例如,完美图和弦图是遗传的。[1]
- 如果具有P属性的图其每一个子图都具有P属性,则称该图是单调的。例如,二分图和无三角形图是单调的。所有单调的图都是遗传的,但遗传的图不一定单调。例如,弦图的子图不一定是弦图,所以弦图并不是单调的。[1]
- 如果具有P属性的图其每一个次图都具有P属性,则称该图是小型闭合的。例如,平面图是小型闭合的。所有小型闭合的图都是单调的,但单调的图不一定是小型闭合的。例如,无三角形图的次图不一定是无三角图,所以无三角形图不是小型闭合的。[1]
这些定义可以从图属性扩展到图的数值常量:如果图常量形式化为对应到实数域的单调函数,则图常量是遗传的、单调的或小型闭合的。。
此外,还研究了图常量在图的不相交并集方面的行为:
常量值
定义图常量的函数其目标集可以是:
图常量与图同构
易于计算的图常量有助于快速识别同构图,或者说是识别非同构图。因为对于任何常量,具有不同值的两个图(根据定义)不能是同构的。然而,具有相同常量的两个图可能是同构的,也可能不是同构的。
如果常量I(G)和I(H)恒等,则意味着图G和图H的同构,此时称图常量I(G)是完备的。找到一个可有效计算这种常量的方法(图规范化问题)等价于给出一个简单解决富有挑战性的图同构问题的方法。然而,即使多项式的常量值如色多项式,通常也不完备的。例如,爪形图和4个顶点的道路图都具有相同的色多项式。
实例
属性
整数常量
- 顶点数
- 边数
- 元件数
- 电路等级(图的顶点、边和元件的线性组合)
- 直径(顶点对之间最长的最短路径)
- 围长
- 顶点连通性(切断图所需移除的最小顶点数)
- 边的连接性(切断图所需移除的最小边数)
- 着色数(将所有顶点着色且相邻顶点不同颜色的最小颜色数)
- 着色指数(将所有边着色且相邻边不同颜色的最小颜色数)
- 独立集(规模最大的独立顶点集)
- 团顶点数(最大完备子图的顶点数)
- 荫度
- Hosoya指数
- Wiener指数
实数常量
序列和多项式
参见
參考文獻
- ^ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 Lovász, László, 4.1 Graph parameters and graph properties, Large Networks and Graph Limits, Colloquium Publications 60, American Mathematical Society: 41–42, 2012
- ^ Nešetřil, Jaroslav; Ossona de Mendez, Patrice, 3.10 Graph Parameters, Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics 28, Springer: 54–56, 2012, ISBN 978-3-642-27874-7, MR 2920058, doi:10.1007/978-3-642-27875-4.