圖標號
在圖論的數學學科中，圖標號（英語：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]。
歷史
[編輯]大多數圖標號的起源可以追溯到亞歷克斯·羅薩（Alex Rosa）在1967年的論文中提出的標號問題[4]。他確定了三種類型的標號，分別稱為α-、β-和ρ-標號。β-labelings後來被所羅門·格倫布更名為優美（Graceful），之後這個名稱開始變得流行起來[5]。
特殊案例
[編輯]優美標號
[編輯]
當一個圖的頂點被從0到|V|（所有頂點）標號時，該圖被認為是優美的，這些標號還使得邊擁有了從1到|E|的邊標號。對於任意邊e, e的標號是其兩個頂點之間的編號差的絕對值。換句話說，如果e與編號為i和j的頂點相關聯，e將被標記為|i - j|。因此，當且僅當存在一個輸入能使得邊集E所映射的正數最大值不超過一個|E|時認為圖G = (V, E)是優美的。
羅薩在他的原始論文中證明了所有大小等價於1或2（除以4取模）的歐拉圖都不是優美的。圖的某些族是否優美是圖論研究的一個重要領域。可以說，圖標號中最大的未經證實猜想是Ringel-Kotzig猜想，其假設了所有的樹都是優美的。這個猜想目前已經在道路結構、毛蟲樹結構和一些其他無限樹族中被證明。Kotzig自己也把努力證明這個猜想的過程稱為「疾病」[6]。
邊優美標號
[編輯]在簡單圖（沒有自環或重邊）中，針對p個頂點和q條邊的邊優美標號是指將邊分別標號為{1, …, q} ，並取定頂點標號為與其直接連接的邊數，因此所有頂點標號的取值範圍為從0到p − 1。如果圖G使用的標號為邊優美標號，那麼該圖被稱為邊優美。
邊優美標號是由S. Lo在1985年首次引入的[7]。
在Lo的理論中，判斷一個圖是邊優美的有以下必要條件：
協調標號
[編輯]圖G的協調標號是指從G的頂點集輸入到整數係數k（G的邊數），通過將邊（x，y）的邊標號取為兩個頂點x，y的標號之和（除以k取模），在G的邊與整數係數k之間形成一個映射。協調圖是指有協調標號的圖。正如佩特森圖所示，奇數周期是和諧的。據推測如果一個頂點標籤允許被重複使用，那麼所有樹都是和諧的[8]。七頁的書圖中，K1,7 × K2提供了一個圖為不和諧的例子[9]。
圖着色
[編輯]圖着色是圖標號的一個子類。頂點着色為對相鄰頂點分配不同的標號;邊着色為對相鄰邊分配不同的標號。
幸運標號
[編輯]圖G的幸運標號是將正整數賦值給G的頂點，如果用S（v）表示v鄰域上的標號之和，那麼S便是G的頂點着色。若G的最小幸運數字為k，那麼其幸運標號為整數{1,…,k}的集合[10]。
參考文獻
[編輯]- ^ 1.0 1.1 Weisstein, Eric W. (編). Labeled graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）.
- ^ "Different Aspects of Coding Theory", by Robert Calderbank (1995) ISBN 0-8218-0379-4, p. 53"
- ^ "Developments in Language Theory", Proc. 9th. Internat.Conf., 2005, ISBN 3-540-26546-5, p. 313
- ^ Gallian, J. A Dynamic Survey of Graph Labelings, 1996-2005. The Electronic Journal of Combinatorics.
- ^ Rosa, A. On certain valuations of vertices in a graph.
- ^ Vietri, Andrea. Sailing towards, and then against, the graceful tree conjecture: some promiscuous results. Bull. Inst. Comb. Appl. 2008, 53: 31–46. ISSN 1183-1278. Zbl 1163.05007.
- ^ Lo, Sheng-Ping. On edge-graceful labelings of graphs. Congressus Numerantium. 1985, 50: 231–241. Zbl 0597.05054.
- ^ Guy (2004) pp.190–191
- ^ Gallian, Joseph A., A dynamic survey of graph labeling, Electronic Journal of Combinatorics, 1998, 5: Dynamic Survey 6 [2019-05-27], MR 1668059, （原始內容存檔於2019-11-08）.
- ^ Czerwiński, Sebastian; Grytczuk, Jarosław; Ẓelazny, Wiktor. Lucky labelings of graphs. Inf. Process. Lett. 2009, 109: 1078–1081. Zbl 1197.05125.
- 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.
- Guy, Richard K.. Unsolved problems in number theory 3rd. 施普林格科學+商業媒體. 2004. C13. ISBN 0-387-20860-7. Zbl 1058.11001.