我們證明，對于任意連通弦圖 G，γ_b(G) ≤ ?(3/2)mp(G)?。我們還通過構造一個連通弦圖無限族，證明 γ_b(G) - mp(G) 可以任意大，使得比率 γ_b(G)/mp(G) = 10/9，且 mp(G) 可任意大。這一結果表明，對于弦圖，我們無法將 γ_b(G) ≤ ?(3/2)mp(G)? 這一界改進為形式如 γ_b(G) ≤ c₁· mp(G) + c₂的界，其中 c₁< 10/9 且 c₂為任意常數。此外，我們證明 γ_b(G) ≤ ?(3/2)mp(G) + 2δ? 對所有 δ-雙曲圖都成立。我們還提供了一個多項式時間算法，用于構造一個 δ-雙曲圖 G 的多包，其大小至少為 ?(2mp(G) - 4δ)/3?。

覆蓋與打包問題是圖論和算法中的基本問題。在本文中，我們研究兩個稱為廣播控制（broadcast domination）和多包（multipacking）的對偶覆蓋與打包問題。廣播控制問題在電信網絡中有自然的動機：設想一個帶有無線電發射塔的網絡，其中每個塔可以以任意半徑 r 廣播信息，成本為 r。目標是以最小的總成本覆蓋整個網絡。多包問題是其自然的打包對應物，并推廣了各種其他標準打包問題。與許多標準打包和覆蓋問題不同，這兩個問題涉及圖中任意距離，這使得它們具有挑戰性。本文的目標是研究這兩個參數在弦圖類和 δ-雙曲圖類中的關系。

廣播控制可以被視為經典支配集問題的推廣。對于一個頂點集為 V、邊集為 E、直徑為 diam(G) 的圖 G = (V, E)，一個函數 f : V → {0, 1, 2, ..., diam(G)} 稱為 G 上的廣播。如果對于每個頂點 u ∈ V，都存在圖 G 中的一個頂點 v（可能 u = v），使得 f(v) > 0 且 d(u, v) ≤ f(v)，那么 f 被稱為 G 上的支配廣播。支配廣播 f 的成本是 σ(f) = Σ_v∈Vf(v)。支配廣播的最小成本是 G 的廣播控制數，記為 γ_b(G)。

最優廣播或最優支配廣播是指成本等于 γ_b(G) 的支配廣播。如果一個支配廣播中沒有頂點從兩個不同的頂點聽到廣播，則稱其為高效的。因此，在高效廣播中，沒有塔可以從另一個塔聽到廣播。有一個定理指出，對于每個圖都存在一個同時也是高效的最優支配廣播。將半徑為 r 圍繞頂點 v 的球定義為 N_r[v] = {u ∈ V(G) : d(v, u) ≤ r}。多包是圖 G = (V, E) 中的一個集合 M ? V，使得對于每個頂點 v ∈ V(G) 和每個整數 r ≥ 1，有 |N_r[v] ∩ M| ≤ r。圖 G 的多包數是其多包的最大基數，記為 mp(G)。最大多包是指滿足 |M| = mp(G) 的多包 M。最大多包問題是最優支配廣播問題的對偶整數規劃。

簡要綜述： Erwin 在其 2001 年的博士論文中引入了廣播控制。多包由 Teshima 在其 2012 年的碩士論文中引入。對于一般圖，令人驚訝的是，可以在 O(n?) 時間內找到最優支配廣播。同一問題可以在線性時間內解決。然而，迄今為止，還沒有已知的多項式時間算法來尋找一般圖的最大多包（該問題也未知是否為 NP 困難問題）。不過，對于樹以及更一般的強弦圖，已知存在多項式時間算法。關于這兩個問題的其他算法結果的參考文獻見 [18]。

我們知道對于任何圖 G，都有 mp(G) ≤ γ_b(G)，因為廣播控制和多包是對偶問題，并且 γ_b(G) ≤ rad(G)，其中 rad(G) 是 G 的半徑。此外，已知 γ_b(G) ≤ 2mp(G) + 3 [2]，并且推測對于每個圖 G，γ_b(G) ≤ 2mp(G) [2]。比值 γ_b(G)/mp(G) 的推測上界 2 對于無限多圖來說是最優的。然而，目前尚不知道存在一個連通圖族，其多包數可以任意大，并且能達到這個比值（事實上，目前尚不知道存在多包數為 3 或更大的圖 [2]，[21]）。

Hartnell 和 Mynhardt [21] 構造了一個連通圖族，使得差值 γ_b(G) - mp(G) 可以任意大，并且事實上，對于該圖族有 γ_b(G)/mp(G) = 4/3。直到最近，這是已知的最佳構造。在我們提交本文之后，Rajendraprasad、Sani、Sasidharan 和 Sen [26] 證明了超立方體在這方面形成了一個有趣的例子族。事實上，已知對于維度為 d 的超立方體 H_d，有 γ_b(H_d) = d - 1 [3]，并且上述作者 [26] 證明了 mp(H_d) ≤ d/2 + 6√(2d)。因此，對于一般連通圖，當 mp(G) → ∞ 時，γ_b(G)/mp(G) 的上確界為 2。一個自然而然的問題是：對于其他連通圖類，這個比值的最大值是多少？已知對于強弦圖，總是有 mp(G) = γ_b(G) [5]。因此，一個自然要研究的圖類是弦圖類。請注意，Hartnell 和 Mynhardt [21] 的構造以及已知的大比值例子——超立方體，都不是弦圖。

我們的貢獻： 弦圖是一個無向簡單圖，其中所有四個或更多頂點的環都有一個弦（即連接環上兩個頂點但不在環上的邊）。弦圖是區間圖的超類。在本文中，我們研究弦圖的多包問題。

我們還對此研究進行了如下推廣。Gromov [20] 引入了 δ-雙曲性度量以通過 Cayley 圖研究幾何群論。設 d 為圖 G 的最短路徑度量。如果對于任意四個頂點 u, v, w, x ∈ V(G)，三個和 d(u, v) + d(w, x), d(u, w) + d(v, x), d(u, x) + d(v, w) 中最大的兩個最多相差 2δ，則圖 G 被稱為 δ-雙曲圖。如果存在常數 δ 使得每個圖 G ∈ G 都是 δ-雙曲的，則圖類 G 被稱為雙曲的。樹是 0-雙曲圖，弦圖是 1-雙曲的。一般來說，雙曲性是圖的距離函數與樹度量偏差的度量。許多其他有趣的圖類包括余可比圖、無星狀三元圖、置換圖、有界弦性或樹長的圖都是雙曲的。此外，雙曲性是捕捉現實世界圖（如互聯網圖或數據庫關系圖）特性的一種度量。在本文中，我們研究雙曲圖的多包問題。

我們首先給出弦圖多包數的界：

如果 G 是連通弦圖，則 γ_b(G) ≤ ?(3/2)mp(G)?。

計算圖的多包數的算法復雜性已被多位作者反復提及，但在過去十年中一直是一個未解決的挑戰。然而，對于樹以及更一般的強弦圖，已知存在多項式時間算法。即使對于樹，尋找最大多包的算法也非常不平凡。弦圖是強弦圖類的超類。在本文中，我們提供了一個 (3/2 + o(1)) 近似算法來尋找弦圖上的多包。

如果 G 是連通弦圖，則存在一個多項式時間算法來構造 G 的一個多包，其大小至少為 ?(2mp(G) - 1)/3?。

這個近似算法基于尋找一條幾乎為半徑兩倍的直徑路徑。取這條路徑上每隔一個的頂點集合即可得到一個多包。

Hartnell 和 Mynhardt [21] 構造了一個連通圖族 H_k，使得 mp(H_k) = 3k 且 γ_b(H_k) = 4k。對于樹以及更一般的強弦圖，不存在這樣的構造，因為對于這些圖類，多包數與廣播控制數是相同的 [5]。