论文标题
在F衍生物和将双分解图分解为路径上
On f-Derangements and Decomposing Bipartite Graphs into Paths
论文作者
论文摘要
令$ f：\ {1，...，n \} \ rightarrow \ {1，...，n \} $为函数（不一定是一对一）。 $ f-derangement $是置换$ g：\ {1，...，n \} \ rightArrow \ {1，...，...，n \} $，使每个$ g（i）\ neq f（i）的$ i = 1，...，...，n $。当$ f $本身是一个排列时，这是标准乱伦。我们检查了F衍生产品的属性，并表明，当我们修复$ f $以下任何项目的最大预映率时，无论是$ f $的选择，F-drangements的排列部分往往趋于$ 1/e $。然后，我们使用此结果分析一种将两分图分解为长度路径5的启发式方法
Let $f: \{1, ..., n\} \rightarrow \{1, ..., n\}$ be a function (not necessarily one-to-one). An $f-derangement$ is a permutation $ g:\{1,...,n\} \rightarrow \{1,...,n\}$ such that $g(i) \neq f(i)$ for each $ i = 1, ..., n$. When $f$ is itself a permutation, this is a standard derangement. We examine properties of f-derangements, and show that when we fix the maximum number of preimages for any item under $f$, the fraction of permutations that are f-derangements tends to $ 1/e$ for large $n$, regardless of the choice of $f$. We then use this result to analyze a heuristic method to decompose bipartite graphs into paths of length 5
