在图论中,图形属性或图形不变量是图形的一种属性,它只依赖于抽象结构,而不依赖于图形表示形式,如图形的特定标签或图的绘图。[1]
虽然图形绘制和图形表示是图论中的有效主题,但是为了只关注图形的抽象结构,图形属性通常被定义为在图形的所有可能同构下保持的属性。换句话说,它是图形本身的属性,而不是图形的特定绘图或表示形式。非正式地,术语“图形不变量”用于定量表示属性,而“属性”通常指图形的描述性特征。例如,语句“图没有度为1的顶点”是一个“属性”,而“图中、度为1的顶点数”是一个“不变量”。
更正式地说,图属性是一类图,其属性是任何两个同构图要么都属于该类,要么都不属于该类。[1]等价地,图形属性可以使用该类的指示函数来形式化,该函数从图形到布尔值对于该类中的图形是真的,否则是假的;同样,任何两个同构图必须具有彼此相同的函数值。图形不变量或图形参数可以类似地被形式化为从图形到更广泛的一类值的函数,例如整数、实数、数列或多项式,它们对于任何两个同构图形都具有相同的值。[2]
对于图中定义的某些自然偏序或预序,许多图属性表现良好:
这些定义可以从图的性质扩展到数值不变量:如果将不变量形式化的函数形成了从图上相应的偏序到实数的单调函数,则图不变量是遗传的、单调的或次闭的。
此外,已经研究了图不变量在图的不相交并集方面的行为:
此外,图形属性可以根据它们描述的图形类型来分类:图形是无向的还是有向的,属性是否适用于多重图形,等等。[1]
定义图形不变量的函数的目标集可以是以下之一:
易于计算的图形不变量有助于快速识别图形同构,或者更确切地说是不同构,因为对于任何不变量,两个具有不同值的图形(根据定义)不可能同构。然而,具有相同不变量的两个图可能同构,也可能不同构。
如果不变量I(G)和I(H)的恒等式意味着图G和H的同构,那么图不变量I(G)被称为完备的。找到一个可有效计算的这种不变量(图规范化问题)意味着一个简单的解决方案来解决具有挑战性的图同构问题。然而,即使多项式值不变量,如彩色多项式,通常也不完全。例如,爪形图和4个顶点上的路径图都具有相同的彩色多项式。
^Lovász, László (2012), "4.1 Graph parameters and graph properties", Large Networks and Graph Limits, Colloquium Publications, 60, American Mathematical Society, pp. 41–42..
^Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "3.10 Graph Parameters", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, 28, Springer, pp. 54–56, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058..
暂无