圖標號
在圖論的數學學科中,圖標號(英語: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]。
特殊案例
[編輯]優美標號
[編輯]![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/97/Graceful_labeling.svg/300px-Graceful_labeling.svg.png)
當一個圖的頂點被從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.
|