Tomemos Algoritmo de Kruskal uno de los algoritmos para un árbol de máxima extensión. Considera las aristas en orden de mayor a menor peso y, para cada arista, la añade al árbol de expansión siempre que no cree un ciclo.
Pensando en el árbol de máxima extensión del grafo ponderado aleatoriamente de esta manera, las siguientes preguntas son equivalentes:
- ¿Cuántos de los $k$ bordes de mayor peso de $G$ ¿terminan en el árbol de máxima extensión?
- Si elegimos $k$ bordes aleatorios de $G$ ¿cuántas aristas hay en el mayor grafo acíclico que podemos formar con ellas?
En lugar de considerar un grafo bipartito completo, voy a ver primero sólo un grafo completo, porque este caso está más estudiado: es el Modelo de Erdős-Rényi de grafos aleatorios, donde tomamos $n$ vértices y elegir $m$ bordes aleatorios entre ellos. Lo que se sabe es que:
- Supongamos que elegimos $m = cn$ bordes para $c < \frac12$ . Entonces, con alta probabilidad, sólo forman un número constante de ciclos.
- Cuando $c>\frac12$ el gráfico experimenta una transición de fase. El $m$ Los bordes crean un componente gigante con una fracción constante de los vértices, y muchos ciclos. Los componentes restantes son pequeños, y en su mayoría no tienen ciclos, aunque unos pocos tienen uno. Por una aproximación de Poisson, hay alrededor de $e^{-2c}n$ vértices aislados.
- El gráfico se conecta alrededor de $\frac12 n \ln n$ aristas, cuando desaparece el último vértice aislado.
En el mundo del árbol de máxima extensión, esto dice:
- La parte superior $\frac12 n$ las aristas están casi todas en el árbol de máxima extensión.
- De la parte superior $n$ aristas, alguna fracción constante está en el árbol de expansión (más de $\frac12$ por monotonía, pero menos que $1 - e^{-2}$ debido a los vértices aislados, que son parte del problema pero no todo). La constante exacta es molesta.
- La parte superior $\frac12 n \ln n$ contienen casi todas las aristas del árbol de máxima extensión.
Si en lugar de un grafo completo, ponderamos las aristas de un grafo bipartito completo, la imagen general sigue siendo la misma pero las constantes varían. Voy a hacer un par de ejemplos; usted puede interpolar.
En primer lugar, supongamos que nuestro gráfico anfitrión es $K_{n,2n}$ . Pasemos al modelo en el que elegimos cada arista de forma independiente con probabilidad $p = \frac cn$ . Entonces el número esperado de ciclos de longitud $2k$ es aproximadamente $\frac1k n^k (2n)^k p^{2k} = \frac{(2c^2)^k}{k}$ y la suma $\sum_{k \ge 2}\frac{(2c^2)^k}{k}$ converge para $c < \frac{\sqrt2}{2}$ . Así que la transición de fase se produce en $p = \frac{\sqrt 2}{2n}$ cuando elegimos $\sqrt 2 n$ bordes aleatorios.
Mientras tanto, la probabilidad de que un vértice esté aislado es $e^{-2np}$ para un vértice del lado menor y $e^{-np}$ para un vértice del lado mayor. Cuando $p = \frac{c \log n}{n}$ Esto da como resultado $n^{1-2c}$ vértices aislados en el lado menor y $2n^{1-c}$ vértices aislados en el lado mayor, por lo que $c=1$ es el punto en el que han desaparecido casi todos los vértices aislados del lado mayor. En este punto, tenemos $2n \log n$ bordes.
En resumen:
- De la parte superior $\sqrt 2 n$ bordes, casi todos se utilizan;
- De la parte superior $3n$ bordes, se utiliza alguna fracción constante;
- Casi todas las aristas del árbol de expansión están en la parte superior $2n \log n$ bordes.
También es informativo tener en cuenta el gráfico del anfitrión $K_{10,n}$ donde $10$ es fijo y $n$ es grande. Aquí podemos ser más precisos. Los vértices del lado pequeño necesitan un número constante de aristas para conectarse, así que podemos ignorarlos. Sólo queremos saber: ¿cuántos vértices del lado grande están aislados?
Por una aproximación de Poisson, el número medio de tales vértices después de elegir $k$ bordes es $n e^{-k/n}$ . Por lo tanto, después de $cn$ bordes, hay $e^{-c}n$ vértices aislados, por lo que aproximadamente $(1 - e^{-c})n$ de la parte superior $cn$ Las aristas forman parte del árbol de expansión.
