图标号
维基百科,自由的 encyclopedia
在图论的数学学科中,图标号(英语:Graph labeling)是对图的边和/或顶点的编号(传统上用整数表示)进行赋值[1]。
其正式定义为:给定图G = (V, E),顶点标号(Vertex labeling)是V 中一个标号集的函数。这样定义出来的函数图被称为顶点标号图(Vertex-labeled graph)。同样地,边标号(Edge labeling)是E中一个标号集的函数,其对应函数图被称为边标号图(Edge-labeled graph)。
当边标号是有序集(例如实数)的成员时,它可被称为加权图(Weighted graph)。
在没有限定条件时,术语标号图通常是指所有标号都不同的顶点标号图。这样的图可以等价地用连续整数{1,…,|V|}来标记,其中|V|是图中顶点的数量[1]。在许多应用中,边或顶点常常被赋予在关联域中有意义的标号。例如可以为边指定遍历事件顶点的表示“花费”的权重[2]。
在以上定义中,图被看作是一个有限的无向简单图。然而,标号的概念可以应用于图的所有扩展和泛化领域。例如,在自动机理论和形式语言理论中,对带标号的多重图进行研究会更方便,其中标号指的是连队顶点对之间带标号的边[3]。