论文标题
图中最大匹配的平均大小
The average size of maximal matchings in graphs
论文作者
论文摘要
我们研究了最大匹配的平均大小的比率$ \ avm（g）$，以达到图$ g $中最大匹配的大小。如果许多最大匹配的尺寸接近$ \ maxm（g）$，则此图不变的值接近1。相反，如果许多最大匹配尺寸较小，则$ \ avm（g）$接近$ \ frac {1}} {2} $。 我们提出了一种通用技术，以确定各类图的$ \ avm（g）$的渐近行为。为了说明该技术的使用，我们首先展示如何找到通常使用生成功能获得的已知渐近值（g）$的已知渐近值，然后我们确定其他图形家庭的$ \ avm（g）$的渐近价值，以$ \ freac和$ \ freac $ \ freac and $ \ freac and $ \ frac}之间的图形值spectrum spectrum。
We investigate the ratio $\avM(G)$ of the average size of a maximal matching to the size of a maximum matching in a graph $G$. If many maximal matchings have a size close to $\maxM(G)$, this graph invariant has a value close to 1. Conversely, if many maximal matchings have a small size, $\avM(G)$ approaches $\frac{1}{2}$. We propose a general technique to determine the asymptotic behavior of $\avM(G)$ for various classes of graphs. To illustrate the use of this technique, we first show how it makes it possible to find known asymptotic values of $\avM(G)$ which were typically obtained using generating functions, and we then determine the asymptotic value of $\avM(G)$ for other families of graphs, highlighting the spectrum of possible values of this graph invariant between $\frac{1}{2}$ and $1$.
