在图论 中，图属性（graph property） 或图常量（graph invariant， 又称图不变量） 是图 的一种性质，它只取决于其抽象结构，而不取决于图的表示形式如特定的图标号 或图绘制形式。[1]
一个示例图。该图为平面图 与连通图 ，有顶点 数为6，边 数为7，最短路径 为3，围长 为3，度序列 为<3, 3, 3, 2, 2, 1>。 定义 编辑 虽然图的绘制和图的表示都是图论中的有效课题，但为了只关注图的抽象结构，图属性 被定义为在图的所有可能同构 下仍存在的属性。换句话说，它是图本身的属性，而不是其特定的绘制或表示形式。非正式用法中，术语“常量 ”用于定量表示其属性，而“属性 ”用于定性描述图的特征。例如，语句“图没有度 为1的顶点 ”为“属性”用法，而“图中度为1的顶点数量”为“常量”用法。
更正式地说，图属性是指具有相同属性的一类图，其任何两个同构图 要么都属于该类，要么都不属于该类。[1] 指示函数 （将图转化为布尔值的函数，属于该类的图为真，否则为假）将图属性形式化，其中任何两个同构图必须具有相同的函数值。类似地，图常量或图参数可以形式化为一个函数，还可从图推广到更广泛的值类，如整数 、实数 、数字序列或多项式 ，这些值对应的图其任何两个同构图都具有相同的值。[2]
图属性的特征 编辑 对于图上定义的某些自然偏序关系 或预序关系 ，许多图属性与其相关性较高:
如果具有P属性的图其每一个诱导子图都具有P属性，则称该图是遗传的 弦图 是遗传的。[1] 如果具有P属性的图其每一个子图 都具有P属性，则称该图是单调的 二分图 和无三角形图是单调的。所有单调的图都是遗传的，但遗传的图不一定单调。例如，弦图的子图不一定是弦图，所以弦图并不是单调的。[1] 如果具有P属性的图其每一个次图 都具有P属性，则称该图是小型闭合的 平面图 是小型闭合的。所有小型闭合的图都是单调的，但单调的图不一定是小型闭合的。例如，无三角形图的次图不一定是无三角图，所以无三角形图不是小型闭合的。[1] 这些定义可以从图属性扩展到图的数值常量：如果图常量形式化为对应到实数域的单调函数，则图常量是遗传的、单调的或小型闭合的。。
此外，还研究了图常量在图的不相交并集 方面的行为:
对于图G和图H，如果G和H的不相交并集里的常量值是G和H各自常量值之和，则对应的图常量是可加的 顶点 数是可加的。[1] 对于图G和图H，如果G和H的不相交并集里的常量值是G和H各自常量值之积，则对应的图常量是可乘的 [1] 对于图G和图H，如果G和H的不相交并集里的常量值是G和H各自常量值的最大值，则对应的图常量就是两者中的最大值。[1] 此外，图属性可以根据它们所描述的图类型进行分类：图是无向的还是有向的，图的属性是否适用于多重图 等。[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-7MR 2920058 , doi:10.1007/978-3-642-27875-4
图属性, 在图论中, graph, property, 或图常量, graph, invariant, 又称图不变量, 是图的一种性质, 它只取决于其抽象结构, 而不取决于图的表示形式如特定的图标号或图绘制形式, 一个示例图, 该图为平面图与连通图, 有顶点数为6, 边数为7, 最短路径为3, 围长为3, 度序列为, 目录, 定义, 的特征, 常量值, 图常量与图同构, 实例, 属性, 整数常量, 实数常量, 序列和多项式, 参见, 參考文獻定义, 编辑虽然图的绘制和图的表示都是图论中的有效课题, 但为了只关注图的. 在图论中 图属性 graph property 或图常量 graph invariant 又称图不变量 是图的一种性质 它只取决于其抽象结构 而不取决于图的表示形式如特定的图标号或图绘制形式 1 一个示例图 该图为平面图与连通图 有顶点数为6 边数为7 最短路径为3 围长为3 度序列为 lt 3 3 3 2 2 1 gt 目录 1 定义 2 图属性的特征 3 常量值 4 图常量与图同构 5 实例 5 1 属性 5 2 整数常量 5 3 实数常量 5 4 序列和多项式 6 参见 7 參考文獻定义 编辑虽然图的绘制和图的表示都是图论中的有效课题 但为了只关注图的抽象结构 图属性被定义为在图的所有可能同构下仍存在的属性 换句话说 它是图本身的属性 而不是其特定的绘制或表示形式 非正式用法中 术语 常量 用于定量表示其属性 而 属性 用于定性描述图的特征 例如 语句 图没有度为1的顶点 为 属性 用法 而 图中度为1的顶点数量 为 常量 用法 更正式地说 图属性是指具有相同属性的一类图 其任何两个同构图要么都属于该类 要么都不属于该类 1 等价来说 可以使用这类图的指示函数 将图转化为布尔值的函数 属于该类的图为真 否则为假 将图属性形式化 其中任何两个同构图必须具有相同的函数值 类似地 图常量或图参数可以形式化为一个函数 还可从图推广到更广泛的值类 如整数 实数 数字序列或多项式 这些值对应的图其任何两个同构图都具有相同的值 2 图属性的特征 编辑对于图上定义的某些自然偏序关系或预序关系 许多图属性与其相关性较高 如果具有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的不相交并集里的常量值是G和H各自常量值的最大值 则对应的图常量就是两者中的最大值 1 此外 图属性可以根据它们所描述的图类型进行分类 图是无向的还是有向的 图的属性是否适用于多重图等 1 常量值 编辑定义图常量的函数其目标集可以是 一个真值 如图属性的指示函数 一个整数 如顶点数或图的色数 一个实数 如图的分数色数 一个整数的序列 如图的度序列 一个多项式 如塔特多项式 图常量与图同构 编辑易于计算的图常量有助于快速识别同构图 或者说是识别非同构图 因为对于任何常量 具有不同值的两个图 根据定义 不能是同构的 然而 具有相同常量的两个图可能是同构的 也可能不是同构的 如果常量I G 和I H 恒等 则意味着图G和图H的同构 此时称图常量I G 是完备的 找到一个可有效计算这种常量的方法 图规范化问题 等价于给出一个简单解决富有挑战性的图同构问题的方法 然而 即使多项式的常量值如色多项式 通常也不完备的 例如 爪形图和4个顶点的道路图都具有相同的色多项式 实例 编辑属性 编辑 连通图 二分图 平面图 无三角形图 完美图 欧拉图 汉密尔顿图整数常量 编辑 顶点数 边数 元件数 电路等级 图的顶点 边和元件的线性组合 直径 顶点对之间最长的最短路径 围长 顶点连通性 切断图所需移除的最小顶点数 边的连接性 切断图所需移除的最小边数 着色数 将所有顶点着色且相邻顶点不同颜色的最小颜色数 着色指数 将所有边着色且相邻边不同颜色的最小颜色数 独立集 规模最大的独立顶点集 团顶点数 最大完备子图的顶点数 荫度 Hosoya指数 Wiener指数实数常量 编辑 聚类系数 介数中心性 分数色数 代数连通度 等周数 Estrada指数 强度序列和多项式 编辑 程序 图谱 邻接矩阵的特征多项式 色多项式 塔特多项式参见 编辑逻辑图 用于指定图形属性的几种形式语言之一 拓扑指数 在化学图论的一个密切相关的概念參考文獻 编辑 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 Lovasz Laszlo 4 1 Graph parameters and graph properties Large Networks and Graph Limits Colloquium Publications 60 American Mathematical Society 41 42 2012 Nesetril 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 取自 https zh wikipedia org w index php title 图属性 amp oldid 62209198, 维基百科，wiki ，书籍，书籍，图书馆，
文章 ，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。