图属性

在图论中，图属性（graph property）或图常量（graph invariant，又称图不变量）是图的一种性质，它只取决于其抽象结构，而不取决于图的表示形式如特定的图标号或图绘制形式。

定义 
虽然图的绘制和图的表示都是图论中的有效课题，但为了只关注图的抽象结构，图属性被定义为在图的所有可能同构下仍存在的属性。换句话说，它是图本身的属性，而不是其特定的绘制或表示形式。非正式用法中，术语“常量”用于定量表示其属性，而“属性”用于定性描述图的特征。例如，语句“图没有度为1的顶点”为“属性”用法，而“图中度为1的顶点数量”为“常量”用法。

更正式地说，图属性是指具有相同属性的一类图，其任何两个同构图要么都属于该类，要么都不属于该类。等价来说，可以使用这类图的指示函数（将图转化为布尔值的函数，属于该类的图为真，否则为假）将图属性形式化，其中任何两个同构图必须具有相同的函数值。类似地，图常量或图参数可以形式化为一个函数，还可从图推广到更广泛的值类，如整数、实数、数字序列或多项式，这些值对应的图其任何两个同构图都具有相同的值。

图属性的特征 
对于图上定义的某些自然偏序关系或预序关系，许多图属性与其相关性较高:

 如果具有P属性的图其每一个诱导子图都具有P属性，则称该图是遗传的。例如，完美图和弦图是遗传的。
 如果具有P属性的图其每一个子图都具有P属性，则称该图是单调的。例如，二分图和无三角形图是单调的。所有单调的图都是遗传的，但遗传的图不一定单调。例如，弦图的子图不一定是弦图，所以弦图并不是单调的。
 如果具有P属性的图其每一个次图都具有P属性，则称该图是小型闭合的。例如，平面图是小型闭合的。所有小型闭合的图都是单调的，但单调的图不一定是小型闭合的。例如，无三角形图的次图不一定是无三角图，所以无三角形图不是小型闭合的。

这些定义可以从图属性扩展到图的数值常量：如果图常量形式化为对应到实数域的单调函数，则图常量是遗传的、单调的或小型闭合的。。

此外，还研究了图常量在图的不相交并集方面的行为:

 对于图G和图H，如果G和H的不相交并集里的常量值是G和H各自常量值之和，则对应的图常量是可加的。例如，其顶点数是可加的。
 对于图G和图H，如果G和H的不相交并集里的常量值是G和H各自常量值之积，则对应的图常量是可乘的。例如，Hosoya指数(匹配数)是可乘的。
 对于图G和图H，如果G和H的不相交并集里的常量值是G和H各自常量值的最大值，则对应的图常量就是两者中的最大值。

此外，图属性可以根据它们所描述的图类型进行分类：图是无向的还是有向的，图的属性是否适用于多重图等。

常量值 
定义图常量的函数其目标集可以是:

 一个真值，如图属性的指示函数。
 一个整数，如顶点数或图的色数。
 一个实数，如图的分数色数。
 一个整数的序列，如图的度序列。
 一个多项式，如塔特多项式。

图常量与图同构 
易于计算的图常量有助于快速识别同构图，或者说是识别非同构图。因为对于任何常量，具有不同值的两个图(根据定义)不能是同构的。然而，具有相同常量的两个图可能是同构的，也可能不是同构的。

如果常量I(G)和I(H)恒等，则意味着图G和图H的同构，此时称图常量I(G)是完备的。找到一个可有效计算这种常量的方法(图规范化问题)等价于给出一个简单解决富有挑战性的图同构问题的方法。然而，即使多项式的常量值如色多项式，通常也不完备的。例如，爪形图和4个顶点的道路图都具有相同的色多项式。

实例

属性 

 连通图
 二分图
 平面图
 无三角形图
 完美图
 欧拉图
 汉密尔顿图

整数常量 

 顶点数
 边数
 元件数
 电路等级（图的顶点、边和元件的线性组合）
 直径（顶点对之间最长的最短路径）
 围长
 顶点连通性（切断图所需移除的最小顶点数）
 边的连接性（切断图所需移除的最小边数）
 着色数（将所有顶点着色且相邻顶点不同颜色的最小颜色数）
 着色指数（将所有边着色且相邻边不同颜色的最小颜色数）
 独立集（规模最大的独立顶点集）
 团顶点数（最大完备子图的顶点数）
 荫度
 Hosoya指数
 Wiener指数

实数常量 

 聚类系数
 介数中心性
 分数色数
 代数连通度
 等周数
 Estrada指数
 强度

序列和多项式 

 程序
 图谱
 邻接矩阵的特征多项式
 色多项式
 塔特多项式

参见 

 逻辑图，用于指定图形属性的几种形式语言之一
 拓扑指数，在化学图论的一个密切相关的概念

參考文獻

有未审阅翻译的页面