定义
一个“大小为k的避难所” 是指对于一个无向图 G = (V, E)，一个函数 H，它将 V 的所有子集映射到一个集合，满足以下条件：
- H(X) ⊆ X，对于所有 X ⊆ V（避难所的结果必须是X的子集）。
- 如果 |X| ≤ k，那么 H(X) ≠ ∅ （如果X的大小不超过k，那么避难所的结果不能为空）。
- 对于任意 X ⊆ V，如果 Y ⊆ X，则 H(X) ⊆ H(Y) 。
如果存在一个大小为 k 的避难所，那么图 G 被称为具有一个大小为 k 的避难所。 避难所与“分支分解（Branch Decomposition）”的概念密切相关，在许多情况下，它提供了一种评估图复杂性的方式。
性质和应用
避难所的概念常用于分析图的各种性质，比如图的“树宽（Treewidth）”。 树宽是衡量图有多像树的一个指标。拥有大避难所的图通常具有较高的树宽。反过来，如果一个图的树宽很小，那么它就不会有大的避难所。
避难所也被用于研究图的“博弈论（Game theory）”性质。 例如，在某些博弈中，避难所可以用来确定玩家是否有策略可以确保胜利。避难所的存在性可以帮助我们理解游戏的可解性。
避难所还与“嵌入（Embedding）”问题相关。例如，在一个图中找到另一个较小图的嵌入。
与其他概念的关系
避难所与图的其他概念如“树分解（Tree decomposition）”、“分支分解（Branch decomposition）”等相关。这些分解方法可以将复杂的图分解成更简单的部分，从而更容易分析。 避难所的存在可以限制图的树宽，表明图的结构比较复杂。
避难所的大小和结构揭示了图的某些结构特性。 它们能够帮助我们了解图的“局部结构”和“全局结构”。
结论
避难所是图论中一个重要的概念，它提供了一种分析和理解图结构的强大工具。 它们与树宽、博弈论和嵌入问题等多个领域相关联。 通过研究避难所，我们可以更深入地了解图的复杂性，并找到解决相关问题的有效方法。