图的属性

在图论中，图的属性或图的不变性是图的一种属性，它只取决于抽象结构，而不取决于图的表示，如特定的标记或图的画法。

虽然图画和图表示是图论中的有效话题，但为了只关注图的抽象结构，图属性被定义为在图的所有可能的同构下保留的属性。换句话说，它是图本身的属性，而不是图的具体画法或表示法的属性。非正式地，图不变性一词用于定量表达的属性，而属性通常指图的描述性特征。例如，图没有度数为1的顶点是一个属性，而图中度数为1的顶点的数量是一个不变式。更正式地说，图的属性是一个图的类别，其属性是任何两个同构的图要么都属于这个类别，要么都不属于这个类别。等价地，一个图的属性可以用该类的指示函数来表示，这是一个从图到布尔值的函数，对于该类中的图来说是真的，否则就是假的；同样，任何两个同构的图必须有彼此相同的函数值。图的不变性或图的参数同样可以被形式化为一个从图到更广泛的值的函数，如整数、实数、数列或多项式，它对任何两个同构的图都具有相同的值。

许多图的属性对于定义在图上的某些自然偏序或预序来说是良好的。一个图的属性P是遗传的，如果一个图的每个诱导子图都具有属性P。一个图的属性是单调的，如果一个图的每个子图都具有属性P，那么它就是单调的。每个单调的属性都是遗传的，但不一定反过来；例如，和弦图的子图不一定是和弦的，所以作为一个和弦图不是单调的。如果一个具有属性P的图的每一个子图也具有属性P，那么该图的属性就是次要封闭的，例如，作为一个平面图就是次要封闭的。每一个次要封闭的属性都是单调的，但不一定反过来；例如，无三角形图形的次要属性本身不一定是无三角形的。这些定义可以从属性扩展到图形的数字不变量：如果将不变量形式化的函数形成一个从图形上相应的偏序到实数的单调函数，那么图形不变量就是遗传的、单调的或次要封闭的。此外，图不变量还被研究了它们在图的不相交联合体方面的行为。如果对于所有两个图G和H，在G和H的不相交联合体上的不变量的值是G和H上的值的总和，则图的不变量是加法的。

如果对于所有两个图G和H，在G和H的不相交联合体上的不变量的值是G和H上的值的乘积，则图的不变量是乘法的，例如，Hosoya指数（匹配的数量）是乘法的。如果对于所有两个图G和H，在G和H的不相交的联合体上的不变量的值是G和H上的值的xxx值，则图的不变量是xxx的。此外，图的属性可以根据它们描述的图的类型来分类：图是无向的还是有向的，属性是否适用于多图，等等。

定义图不变量的函数的目标集可以是以下之一。一个真值，真或假，为图属性的指示函数。一个整数，如图的顶点数或色度数。一个实数，如图的分数色度数。一个整数序列，如图的程度序列。多项式，例如图的Tutte多项式。图的不变量和图的同构性容易计算的图的不变量对于快速识别图的同构性，或者说非同构性很有帮助，因为对于任何不变量，两个具有不同值的图（根据定义）是不可能同构的。然而，具有相同不变性的两个图可能是同构的，也可能不是。如果不变量I(G)和I(H)的同一性意味着图G和H的同构，那么一个图不变量I(G)就被称为完整。