The Wayback Machine - https://web.archive.org/web/20221029033950/https://baike.sogou.com/kexue/d10160.htm

图形属性

编辑
具有平面性和连通性的示例图,其阶数为6,尺寸为7,直径为3,周长为3,顶点连通性为1,度序列为<3,3,3,2,2,1>

在图论中,图形属性或图形不变量是图形的一种属性,它只依赖于抽象结构,而不依赖于图形表示形式,如图形的特定标签或图的绘图。[1]

1 定义编辑

虽然图形绘制和图形表示是图论中的有效主题,但是为了只关注图形的抽象结构,图形属性通常被定义为在图形的所有可能同构下保持的属性。换句话说,它是图形本身的属性,而不是图形的特定绘图或表示形式。非正式地,术语“图形不变量”用于定量表示属性,而“属性”通常指图形的描述性特征。例如,语句“图没有度为1的顶点”是一个“属性”,而“图中、度为1的顶点数”是一个“不变量”。

更正式地说,图属性是一类图,其属性是任何两个同构图要么都属于该类,要么都不属于该类。[1]等价地,图形属性可以使用该类的指示函数来形式化,该函数从图形到布尔值对于该类中的图形是真的,否则是假的;同样,任何两个同构图必须具有彼此相同的函数值。图形不变量或图形参数可以类似地被形式化为从图形到更广泛的一类值的函数,例如整数、实数、数列或多项式,它们对于任何两个同构图形都具有相同的值。[2]

2 属性的特性编辑

对于图中定义的某些自然偏序或预序,许多图属性表现良好:

  • 如果性质为P图的每个诱导子图都具有属性P,那么这个图的属性P是遗传的。例如,一个完美的图或者一个弦图都是遗传的。[1]
  • 如果性质为P的图的每个子图也具有性质P,则图的性质是单调的。例如,作为二部图或无三角形图是单调的。每一种单调的属性都是遗传的,但不一定反之亦然;例如,弦图的子图不一定是弦图,所以作为弦图不是单调的。[1]
  • 如果性质为P的图的每个次图也具有性质P,则图的性质是次闭的。例如,平面图是次闭的。每个次闭性质都是单调的,但不一定反之亦然;例如,无三角形图的子图本身不一定是无三角形的。[1]

这些定义可以从图的性质扩展到数值不变量:如果将不变量形式化的函数形成了从图上相应的偏序到实数的单调函数,则图不变量是遗传的、单调的或次闭的。

此外,已经研究了图不变量在图的不相交并集方面的行为:

  • 如果对于所有G和H两个图,G和H的不交并集上的不变量的值是G和H上的值的和,则图不变量是可加的。例如,顶点的数量是可加的。[1]
  • 如果对于所有G和H两个图,G和H的不交并集上的不变量的值是G和H上的值的乘积,则图不变量是乘法的。例如,霍索亚(Hosoya)指数(匹配次数)是乘法的。[1]
  • 如果G和H两个图的不变量在不相交并集上的值是在G和H上的最大值,那么图不变量是最大的。例如,色数是最大的。[1]

此外,图形属性可以根据它们描述的图形类型来分类:图形是无向的还是有向的,属性是否适用于多重图形,等等。[1]

3 不变量的值编辑

定义图形不变量的函数的目标集可以是以下之一:

  • 图形属性的指示函数的真值,真或假。
  • 整数,如图的顶点数或色数。
  • 实数,如图形的分数色数。
  • 整数序列,如图形的度序列。
  • 一种多项式,如图形的图特(Tutte)多项式。

4 图不变量和图同构编辑

易于计算的图形不变量有助于快速识别图形同构,或者更确切地说是不同构,因为对于任何不变量,两个具有不同值的图形(根据定义)不可能同构。然而,具有相同不变量的两个图可能同构,也可能不同构。

如果不变量I(G)和I(H)的恒等式意味着图G和H的同构,那么图不变量I(G)被称为完备的。找到一个可有效计算的这种不变量(图规范化问题)意味着一个简单的解决方案来解决具有挑战性的图同构问题。然而,即使多项式值不变量,如彩色多项式,通常也不完全。例如,爪形图和4个顶点上的路径图都具有相同的彩色多项式。

5 例子编辑

5.1 属性

  • 连通图
  • 二部图
  • 平面图
  • 无三角形图
  • 完美图形
  • 欧拉(Eulerian)图
  • 哈密尔顿(Hamiltonian)图

5.2 整数不变量

  • 顺序,顶点的数量
  • 大小,边的数量
  • 连接组件的数量
  • 电路秩,边、顶点和元件数量的线性组合
  • 直径,成对顶点之间最短路径长度中最长的一个
  • 周长,最短周期的长度
  • 顶点连通性,即移除时断开图形的最小顶点数
  • 边连通性,即移除时断开图形的最小边数
  • 色数,正确着色中顶点的最小颜色数
  • 色度指数,在适当的边着色中边的最小颜色数
  • 可选择性(或列表色数),使G为可选择的最小数k
  • 独立数,独立顶点集的最大大小
  • 群数,完全子图的最大阶
  • 树木性
  • 图形属
  • 页码
  • Hosoya指数
  • 维纳(Wiener)指数
  • 科林·德·威尔第尔(Colin de Verdière)图不变量
  • 盒子度

5.3 实数不变量

  • 聚类系数
  • 中间中心度
  • 分数色数
  • 代数连通性
  • 等周数
  • 埃斯特拉达(Estrada)指数
  • 稳定度

5.4 序列和多项式

  • 度序列
  • 图形光谱
  • 邻接矩阵的特征多项式
  • 彩色多项式,  函数的  颜色数
  • 图特多项式,一种二元函数,对图形的大部分连通性进行编码

参考文献

  • [1]

    ^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..

  • [2]

    ^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..

阅读 31
版本记录
  • 暂无