Sharing tea on a graph

研究問題：平均竟然也有策略

在圖G上，每個頂點放有非負茶量w(x)。一次分享選一個有限連通頂點集合T，把其中的總茶量平均分給T，其餘位置不動。給定起始分布與目標頂點v，能把多少茶集中到v？平均會減少差異，但操作次序仍可影響目標濃度。本文證明單一來源的精確距離界，並研究多來源上界、有限圖的最佳策略存在性與來源—目標對偶。

主定理與一個必要區分

若一開始只有r放有1單位茶，則任何可達狀態都滿足w(v)≤1/(d(r,v)+1)。一般分享只需選一條r到v的最短路徑一次平均，即可達界。邊操作只准相鄰兩點平均，雖也受同一上界限制，卻不一定有限次達到。例如三點路徑末端的最佳上確界是1/3；從整數初態做有限次兩點平均只會產生分母為2冪的數，因此只能逼近1/3。

證明亮點：控制所有集合的茶量

令ρ_r(S)=Π_(x∈S)d(r,x)/(d(r,x)+1)，作者以w(S)≤1−ρ_r(S)作歸納不變量。初態δ_r立刻符合。若平均邊xy跨越S邊界，平均後w(S)恰為舊w(S−x)與w(S+y)的平均。相鄰距離a、b滿足a≤b+1，而1+ab/((a+1)(b+1))−2a/(a+1)=(b+1−a)/((a+1)(b+1))≥0，剛好使集合上界被保留。取S={v}即得主定理。

一般分享與多個目標

一般連通集合平均可用邊平均逼近，因而保留相同上界；附錄A另給直接的加權乘積證明，利用連通集合上的距離標記形成整數區間。集合不變量也控制多目標總量：若兩個目標距離r分別為1、2，總茶量不超過1−(1/2)(2/3)=2/3。不過單點可以最短路徑達界，不代表所有多目標集合的上界都可達。

任意起始分布的距離potential

對目標v及來源x，定義h_x(a)=a+(w(x)−a)/(d(x,v)+1)。選出初始w(x)>w(v)的來源，按茶量遞增依序組合h_x，從w(v)開始，得到任何可達目標茶量的上界。兩個來源的交換差值是(w(y)−w(x))/((d_x+1)(d_y+1))，所以由淡到濃最有利。這是一般圖的分析potential，不應直接宣稱每個映射組合都能用實際分享達成。

星狀圖展示排序與達界

星狀圖各來源都是目標中心的鄰居，且未使用的葉子保持原值，因此由淡到濃逐片平均確實能達到potential。中心0、葉子1、2、4時，依序得到1/2、5/4、21/8，比全圖一次平均的7/4大；反序則只得3/2。本文也指出無限星狀圖可能沒有有限最佳策略：中心0、葉子i茶量2^(−i)，用前k片由小到大平均得到(1−4^(−k))/3，逼近但不達1/3；此公式是導讀補算。

有限圖的可達集是緊緻的

對有限圖，一般分享的可達集R(w)不僅有界，也封閉，故任何連續目標函數都能取得最大值。核心是把平均寫成對稱正交投影A_T；平方範數下降量等於集合內偏離均值的平方和。無限操作鏈的極限，在反覆操作集合的連通分量內成為均勻分布，可由有限前綴再平均各分量實現。要處理不在同一操作鏈的任意收斂序列，作者另以可達偏序、距離函數與Zorn引理證閉性。

存在性不等於快速求出策略

緊緻性保證最佳值能由有限次一般操作取得，但沒有直接給出通用的短策略或有效率演算法。可達集也不一定凸：兩點圖從(1,0)出發，只能到原態或(1/2,1/2)。文中樹圖反例顯示，不能一概禁止早期平均集合包含於較晚集合；某些最佳策略必須有這種包含。這些現象提醒我們：局部平均的可達幾何比單純守恆或凸組合直覺更細緻。

對偶性把多來源換成多目標

每個平均矩陣對稱，所以〈c,A_Tk⋯A_T1 w〉=〈w,A_T1⋯A_Tk c〉。對所有序列取上確界，就得到交換初始分布w與目標權重c的對偶。從X每點放1單位、最大化v，等同從v放1單位、最大化X總茶量。操作次序反轉不是逆操作，因為平均通常不可逆。若准許邊上的部分平均，線性目標上確界不變，因其乘積可展開成普通邊操作序列的凸組合；可達集本身仍可能不同。

國際合作與研究延伸

本文連結圖距離、組合不變量、投影動力學與最優化；後續可探討短最優策略、特殊圖類及多目標達界條件。九位作者為J. Pascal Gollin、Kevin Hendrey、Hao Huang、Tony Huynh、Bojan Mohar、Sang-il Oum、Ningyuan Yang、Wei-Hsuan Yu、Xuding Zhu。致謝提及2024中研院Pacific Rim Graph Theory Group Workshop。導讀依Sharing tea on a graph，arXiv:2405.15353v2（2025年9月），不把來源版本的研究問題當成已核實的最新狀態。