Question

Labeling

替一张图的各个元件标记数值或者符号。一张图的标记情形，称作一种“标号”。

根据元件的不同，标号可分为许多种类型，例如点标号（vertex labeling）、边标号（edge labeling）。

Magic Labeling

Magic Labeling

用 1 2 3 ...的数字分别标记每一条边，让每一个点接触的数字和为定值。

Kn,n有 Magic Labeling（n≠2）。
一张二分图如果可以拆成两个 Hamilton Cycle，则有 Magic Labeling。
一张图如果可以拆成两个部分，两个都有 Magic Labeling，且其中一个是 regular，则有 Magic Labeling。

幻方（magic square）可以等价转换成 K_n,n，所以边长大于二的幻方一定都有 Magic Labeling。

Antimagic Labeling

用 1 2 3 ...的数字分别标记每一条边，让每一个点接触的数字和皆相异。

尚未证实：K2以外的连通图皆有 Antimagic Labeling。
尚未证实：K2以外的树皆有 Antimagic Labeling。

Graceful Labeling

Graceful Labeling

用 1 2 3 ...的数字分别标记每一条边，1 2 3 ...的数字分别标记每一个点，让每一条边等于其两端点的差值。

尚未证实：所有树皆有 Graceful Labeling。

ICPC 7663

Consecutive Labeling

用 1 2 3 ...的数字分别标记每一条边与每一个点，让每一条边等于其两端点的差值。

每一种 Graceful Labeling 皆可等价调整成一种 Consecutive Labeling。但是反过来不见得行。

尚未证实：所有树皆有 Consecutive Labeling。

Conservative Labeling

Conservative Labeling

无向图上，用 1 2 3 ...的数字分别标记每一条边，并且设定方向（即是 Orientation 的概念），让每个点的流入数字和等于流出数字和（类似 Flow 的概念）。

Kirchhoff's Current Law 即是在说总流入等于总流出的性质。

Strongly Conservative Labeling

改用 n+1 n+2 n+3 ...的数字，必须支援各种 n。

一张图可以拆成两个 Hamilton Cycle，则此图有 Strongly Conservative Labeling。