查看“︁图标号”︁的源代码

在[[图论]]的[[数学]]学科中，'''图标号'''（{{lang-en|Graph labeling}}）是对图的[[邊 (圖論)|边]]和/或[[顶点 (图论)|顶点]]的编号（传统上用[[整数]]表示）进行赋值<ref name="mathw">{{cite mathworld|LabeledGraph|Labeled graph}}</ref>。

其正式定义为：给定图{{nowrap|1=''G'' = (''V'', ''E'')}}，'''顶点标号'''（Vertex labeling）是''V'' 中一个标号集的函数。这样定义出来的函数图被称为'''顶点标号图'''（Vertex-labeled graph）。同样地，'''边标号'''（Edge labeling）是''E''中一个标号集的函数，其对应函数图被称为'''边标号图'''（Edge-labeled graph）。

当边标号是有序集（例如[[实数]]）的成员时，它可被称为'''加权图'''（Weighted graph）。

在没有限定条件时，术语'''标号图'''通常是指所有标号都不同的顶点标号图。这样的图可以等价地用连续整数{1，…，|V|}来标记，其中|V|是图中顶点的数量<ref name="mathw">{{cite mathworld|LabeledGraph|Labeled graph}}</ref>。在许多应用中，边或顶点常常被赋予在关联域中有意义的标号。例如可以为边指定遍历事件顶点的表示“花费”的权重<ref>"Different Aspects of Coding Theory", by Robert Calderbank (1995) {{ISBN|0-8218-0379-4}}, [https://books.google.com/books?id=TcOzdq3nDp4C&pg=PA57&dq=%22labeled+graph%22&lr=#PPA53,M1 p. 53]"</ref>。

在以上定义中，图被看作是一个有限的无向简单图。然而，标号的概念可以应用于图的所有扩展和泛化领域。例如，在[[自动机理论]]和[[形式语言]]理论中，对带标号的[[多重图]]进行研究会更方便，其中标号指的是连队顶点对之间带标号的边<ref>"[[Developments in Language Theory]]", Proc. 9th. Internat.Conf., 2005, {{ISBN|3-540-26546-5}}, [https://books.google.com/books?id=QPgojKbuuUEC&pg=PA314&dq=%22labeled+graph%22#PPA313,M1 p. 313] </ref>。

== 历史 ==
大多数图标号的起源可以追溯到亚历克斯·罗萨（Alex Rosa）在1967年的论文中提出的标号问题<ref name="Gallian">{{Cite journal|title=A Dynamic Survey of Graph Labelings, 1996-2005|last=Gallian, J.|publisher=The Electronic Journal of Combinatorics}}</ref>。他确定了三种类型的标号，分别称为α-、β-和ρ-标号。β-labelings后来被[[所羅門·格倫布|所罗门·格伦布]]更名为优美（Graceful），之后这个名称开始变得流行起来<ref name="Rosa">{{Cite journal|title=On certain valuations of vertices in a graph|last=Rosa, A.}}</ref>。

== 特殊案例 ==

=== 优美标号 ===
[[File:Graceful_labeling.svg|缩略图|300x300像素|优美标号实例之一，其中顶点标号为黑色的，边标号为红色的。]]
当一个图的顶点被从0到|V|（所有顶点）标号时，该图被认为是优美的，这些标号还使得边拥有了从1到|E|的边标号。对于任意边e, e的标号是其两个顶点之间的编号差的绝对值。换句话说，如果e与编号为i和j的顶点相关联，e将被标记为|i - j|。因此，当且仅当存在一个输入能使得边集E所映射的正数最大值不超过一个{{abs|''E''}}时认为图{{nowrap|1=''G'' = (''V'', ''E'')}}是优美的。

罗萨在他的原始论文中证明了所有大小[[等价关系|等价于]]1或2（除以4取模）的[[欧拉图]]都不是优美的。图的某些族是否优美是图论研究的一个重要领域。可以说，图标号中最大的未经证实猜想是Ringel-Kotzig猜想，其假设了所有的树都是优美的。这个猜想目前已经在[[道路 (图论)|道路]]结构、[[毛虫树]]结构和一些其他无限树族中被证明。Kotzig自己也把努力证明这个猜想的过程称为“疾病”<ref>{{Cite journal|title=Sailing towards, and then against, the graceful tree conjecture: some promiscuous results|last=Vietri|first=Andrea|journal=Bull. Inst. Comb. Appl.|year=2008|volume=53|pages=31–46|issn=1183-1278|zbl=1163.05007}}</ref>。

=== 边优美标号 ===
在简单图（没有[[自环]]或[[重边]]）中，针对p个顶点和q条边的边优美标号是指将边分别标号为{{nowrap|{1, …, ''q''}}} ，并取定顶点标号为与其直接连接的边数，因此所有顶点标号的取值范围为从0到{{nowrap|''p'' − 1}}。如果图G使用的标号为边优美标号，那么该图被称为边优美。

边优美标号是由S. Lo在1985年首次引入的<ref>{{Cite journal|title=On edge-graceful labelings of graphs|last=Lo|first=Sheng-Ping|journal=Congressus Numerantium|year=1985|volume=50|pages=231–241|zbl=0597.05054}}</ref>。

在Lo的理论中，判断一个图是边优美的有以下必要条件：

: <math>q(q + 1) = p/(p - 1)2 \mod p.</math>

=== 协调标号 ===
图G的协调标号是指从G的顶点集输入到整数系数''k''（G的边数），通过将边（x，y）的边标号取为两个顶点x，y的标号之和（除以k取模），在G的边与整数系数''k''之间形成一个映射。协调图是指有协调标号的图。正如[[佩特森图]]所示，奇数周期是和谐的。据推测如果一个顶点标签允许被重复使用，那么所有树都是和谐的<ref>Guy (2004) pp.190–191</ref>。七页的[[书 (图论)|书图]]中，{{math|''K''<sub>1,7</sub> &times; ''K''<sub>2</sub>}}提供了一个图为不和谐的例子<ref>{{Citation|last=Gallian|first=Joseph A.|author-link=Joseph Gallian|journal=[[Electronic Journal of Combinatorics]]|mr=1668059|page=Dynamic Survey 6|title=A dynamic survey of graph labeling|url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6|volume=5|year=1998|accessdate=2019-05-27|archive-date=2019-11-08|archive-url=https://web.archive.org/web/20191108105416/https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6|dead-url=no}}.</ref>。

=== 图着色 ===
图着色是图标号的一个子类。顶点着色为对相邻顶点分配不同的标号;边着色为对相邻边分配不同的标号。

=== 幸运标号 ===
图G的幸运标号是将正整数赋值给G的顶点，如果用''S''（''v''）表示v邻域上的标号之和，那么S便是G的顶点着色。若G的最小幸运数字为''k''，那么其幸运标号为整数{1,…,k}的集合<ref>{{Cite journal|title=Lucky labelings of graphs|last=Czerwiński|first=Sebastian|last2=Grytczuk|first2=Jarosław|journal=Inf. Process. Lett.|year=2009|volume=109|pages=1078–1081|zbl=1197.05125|last3=Ẓelazny|first3=Wiktor}}</ref>。

==參考文獻==
{{Reflist}}
* Rosa, A. (1967). On certain valuations of the vertices of a graph. Theory of Graphs, Int. Symp. Rome July 1966. Gordon and Breach. pp. 349–355. Zbl 0193.53204.
* {{Cite book |author={{le|理查德·蓋伊|Richard K. Guy|Guy, Richard K.}} |title=Unsolved problems in number theory |url=https://archive.org/details/unsolvedproblems0003guyr |publisher=[[施普林格科学%2B商业媒体]] |edition=3rd |year=2004 |isbn=0-387-20860-7 |at=C13 |zbl=1058.11001 }}

{{圖論}}
[[Category:图论组成结构]]