Labeling

替一張圖的各個元件標記數值或者符號。一張圖的標記情形，稱作一種「標號」。

根據元件的不同，標號可分為許多種類型，例如點標號（vertex labeling）、邊標號（edge labeling）。

《Pearls in Graph Theory: A Comprehensive Introduction》

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 ...的數字分別標記每一條邊，讓每一個點接觸的數字和皆相異。

尚未證實：K₂以外的連通圖皆有Antimagic Labeling。
尚未證實：K₂以外的樹皆有Antimagic 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

無向圖上，用1 2 3 ...的數字分別標記每一條邊，並且設定方向（即是Orientation的概念），讓每個點的流入數字和等於流出數字和（類似Flow的概念）。

Kirchhoff's Current Law即是在說總流入等於總流出的性質。

Strongly Conservative Labeling

改用n+1 n+2 n+3 ...的數字，必須支援各種n。

一張圖可以拆成兩個Hamilton Cycle，則此圖有Strongly Conservative Labeling。

Minimum Linear Arrangement

用1 2 3 ...的數字分別標記每一個點，讓每一條邊等於其兩端點的差值，所有邊權重總和盡量小。