圖論數學學科中,圖標號(英語: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的頂點,如果用Sv)表示v鄰域上的標號之和,那麼S便是G的頂點着色。若G的最小幸運數字為k,那麼其幸運標號為整數{1,…,k}的集合[10]

參考文獻

  1. ^ 1.0 1.1 Weisstein, Eric W. (編). Labeled graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英語). 
  2. ^ "Different Aspects of Coding Theory", by Robert Calderbank (1995) ISBN 0-8218-0379-4, p. 53"
  3. ^ "Developments in Language Theory", Proc. 9th. Internat.Conf., 2005, ISBN 3-540-26546-5, p. 313
  4. ^ Gallian, J. A Dynamic Survey of Graph Labelings, 1996-2005. The Electronic Journal of Combinatorics. 
  5. ^ Rosa, A. On certain valuations of vertices in a graph. 
  6. ^ 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. 
  7. ^ Lo, Sheng-Ping. On edge-graceful labelings of graphs. Congressus Numerantium. 1985, 50: 231–241. Zbl 0597.05054. 
  8. ^ Guy (2004) pp.190–191
  9. ^ 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) .
  10. ^ Czerwiński, Sebastian; Grytczuk, Jarosław; Ẓelazny, Wiktor. Lucky labelings of graphs. Inf. Process. Lett. 2009, 109: 1078–1081. Zbl 1197.05125.