哈希与图边删除问题的深入剖析

### 哈希与图边删除问题的深入剖析 #### 1. c-理想哈希函数族的界 在哈希领域，c-理想哈希函数族的研究至关重要。对于c-理想哈希函数族，有定理表明其最小哈希函数数量存在上界。具体来说，定理4指出，对于常数α，存在一个函数，能使每个大小为n的键集在哈希表单元格中的分布至少达到最优解的c倍，这样的函数数量上界与m呈指数增长关系，与n的平方根相关，与全域大小呈对数关系。不过，目前得到的上下界并不匹配，因此Hc在给定界内的精确行为仍不明确。 为了进一步分析，我们可以考虑特殊情况的改进。例如，定理5给出了Hc的一个下界：$Hc \geq \frac{\ln(u) - \ln(c\alpha)}{\ln(m)}$ ，这个下界有意义地引入了全域大小u。而对于较大的c值，定理6（Yao界）表明，对于$c \in \omega(\frac{t \ln n}{\ln \ln n})$ （其中$t \geq 1$ ），有$Hc \in O(\frac{\ln |S_n|}{\ln t})$ ，特别地，当$t \in O(1)$ 时，$Hc \in O(n \ln u)$ 。 #### 2. 哈希的建议复杂度 将哈希视为一个在线问题，我们可以利用Hc的界来确定c-竞争算法的建议复杂度。定理7指出，对于哈希算法Alg，如果其建议比特数少于$\ln(\ln(u) - \ln(c\alpha)) - \ln(\ln(m))$ ，则无法达到低于$cost(Alg) = c\alpha$ 的成本，也就不是c-竞争的。 进一步地，定理8给出了一个更强的下界。对于任意固定的$\epsilon > 0$ ，每个哈希算法Alg要达到c-竞争，至少需要$\log((1 - \epsilon) \exp(\frac{m}{e\alpha (1 - \epsilon)}(\frac{\alpha}{c\alpha + 1})^{c\alpha + 1}))$ 个建议比特。通过分析$(\frac{\alpha}{c\alpha + 1})^{c\alpha + 1}$ 的渐近行为，我们可以得到该下界为$\Omega(\frac{m}{e\alpha}(\frac{1}{c})^{c\alpha + 1})$ 。 而上界方面，定理9表明存在一个c-竞争算法，其读取的建议比特数为$\log upperboundHc \in upperboundHcOnotation$ 。当$c = \alpha = 1$ 时，m后面的因子最小，但仍大于1.002，所以这个上界至少与m呈线性关系。对于$c = \omega(\frac{\ln(n)}{\ln(\ln(n))})$ ，根据定理6可以进一步改进，得到定理10：对于$c \in \omega(\frac{t \ln n}{\ln \ln n})$ （$t > 1$ ），存在一个c-竞争算法，其读取$O(\log(\frac{\ln |S_n|}{\ln t}))$ 个建议比特；特别地，当$t \in O(1)$ 时，存在一个$\frac{\ln n}{\ln \ln n}$ -竞争算法，其读取$O(\ln \ln u + \ln n)$ 个建议比特。 从这些结果可以看出，哈希的建议复杂度与哈希表大小m呈线性关系，与n呈对数关系，与u呈双对数关系。而且，α和c在下界中的影响是指数级的，这意味着稍微放宽对完美性的追求，c-理想哈希函数族的大小可能会呈指数级减小。 #### 3. 图边删除问题的背景与定义 在图论中，Th + 1 - 自由边删除问题有着重要的实际应用。例如，在疾病传播网络中，我们可以将图的节点看作牲畜农场，边表示农场之间牲畜的共同移动路线。通过删除一些边，使得得到的图中每个连通分量的顶点数最多为h，这有助于限制疾病的传播。 具体来说，Th + 1 - 自由边删除问题的输入是一个无向图$G = (V, E)$ 和两个正整数k和h，问题是是否存在一个边集$E' \subseteq E(G)$ ，且$|E'| \leq k$ ，使得$G \setminus E'$ 中每个连通分量的顶点数最多为h，即$G \setminus E'$ 不包含任何h + 1个顶点的树作为子图。 其在有向图中的自然推广是Th + 1 - 自由弧删除问题，输入是一个有向图$G = (V, E)$ 和两个正整数k和h，问题是是否存在一个边集$E' \subseteq E(G)$ ，且$|E'| \leq k$ ，使得在$G \setminus E'$ 中从任何给定起始顶点可达的最大顶点数最多为h。 #