Emparejamiento de aristas de diferentes árboles de expansión

Question

Hace un tiempo me topé con este teorema

Dejemos que $S$ et $T$ sean dos árboles de expansión sobre el mismo conjunto de vértices. Entonces existe una biyección $F: E(S) \to E(T)$ que satisface la siguiente propiedad de intercambio de aristas: $S - e + F(e)$ es un árbol de expansión para todos los $e \in E(S)$ .

Me parece bastante interesante ya que resume algunas buenas propiedades sobre los Spanning Trees. Se me ha ocurrido una prueba para este teorema, pero no estoy 100% seguro de que la prueba sea realmente correcta. ¿Alguien puede verificar si es correcta? Además, si crees que hay una manera más fácil de demostrarlo, házmelo saber.

Prueba. Dejemos que $n = | E(S)\setminus E(T) | $ sea el número de aristas que difieren de cada árbol de expansión. Demostramos el teorema por inducción en $n$ . El caso $n = 0$ es trivial ya que entonces tenemos $S = T.$ Supongamos ahora que tenemos $n+1$ bordes en $S$ que no están incluidos en $T$ y que la suposición se mantiene para $n$ . Sea $e$ sea cualquier arista en $T - S$ (esta arista existe ya que ambos árboles de expansión contienen el mismo número de aristas). Dado que $S$ es un árbol de expansión, existe un círculo fundamental $C$ en $ S+ e$ . Desde $T$ es un árbol de expansión, tenemos $C \not \subseteq T$ . Sea $e^\prime \in C$ sea cualquier arista que no esté incluida en T. Ahora podemos definir $F(e^\prime) := e$ . La condición del enunciado se cumple ahora para este par de $e$ et $e^\prime $ por la construcción. Sea $S^\prime := S -e^\prime + e$ . Entonces, por la hipótesis de inducción, encontramos una biyección $G: E(S^\prime) \to E(T)$ satisfaciendo la propiedad de intercambio de bordes. Basta con demostrar que $S - f^\prime + G(f^\prime)$ es un árbol de expansión también para todas las aristas $f^\prime \in E(S) \cap E(S^\prime)$ (podemos ampliar $F$ por $G$ entonces). Dejemos que $f^\prime \in E(S) \cap E(S^\prime)$ sea una arista de este tipo y $f:= G(f^\prime)$ . Para ver esto, podemos dividir el conjunto de vértices: Obsérvese que $S - e^\prime - f^\prime $ contiene exactamente tres componentes conectados. Las etiquetamos con $S_1, S_2, S_3$ tal que $e^\prime$ es un puente entre $S_1$ et $S_2$ et $f^\prime$ es un puente entre $S_2$ et $S_3$ . Sabemos que $S - e^\prime + e$ es un árbol de expansión. Por lo tanto, $e$ debe ser un puente entre $S_1$ et $S_2$ . Desde $S - e^\prime + e - f^\prime + f$ es un árbol de expansión por la hipótesis inductiva, se da exactamente uno de los siguientes casos:

1. $G(f^\prime) = f$ es un puente entre $S_1$ et $S_3$ .
2. $G(f^\prime) = f$ es un puente entre $S_2$ et $S_3$ .

De cualquier manera, podemos sustituir $e^\prime$ de nuevo para $e$ y aún así obtener un Spanning Tree. Así, $S - f^\prime + f$ es un árbol de expansión. q.e.d.

Hazme saber lo que piensas sobre el teorema y esta demostración. Creo que tiene algunas buenas aplicaciones, por ejemplo, para los árboles de extensión mínima se deduce que la biyección preserva la función de coste, es decir. $c(f(e)) = c(e)$ para todas las aristas $e \in E(S)$ . También hay que tener en cuenta que la prueba es muy constructiva y se puede construir fácilmente un algoritmo para calcular la biyección. No dudes en comentar si se te ocurren otras aplicaciones.

Answer 1

El resultado es muy bonito. Sin embargo, hay un problema con su prueba: $e$ también puede ir entre $S_1$ et $S_3$ Esto aún haría que $S - e' + e$ un árbol de expansión. En este caso, es posible que $f$ va entre $S_1$ et $S_2$ y luego $S - f' + f$ no es un árbol. Soy escéptico en cuanto a si esta prueba puede ser corregida, ya que implica que podemos elegir la biyección de una "manera codiciosa", lo que me parece un poco demasiado optimista.

La demostración de este teorema se encuentra en el libro Conexiones en la optimización combinatoria de András Frank (es el teorema 5.3.4 en mi versión del libro). Dice lo siguiente. Basta con encontrar una biyección entre $X = E(S) - E(T)$ et $Y = E(T) - E(S)$ . Consideremos el grafo bipartito $G'$ en $X \cup Y$ donde $xy$ es una arista si y sólo si $x$ está en el circuito fundamental de $y$ con respecto a $S$ (es decir, en el circuito único de $S + y$ ). Entonces, encontrar una biyección adecuada es equivalente a encontrar una correspondencia perfecta de $G'$ . Utilizamos el teorema de Hall para demostrar que efectivamente existe una correspondencia perfecta en $G'$ . Sea $Y' = \{y_1, \ldots, y_j\} \subseteq Y$ sea un subconjunto de vértices de $G'$ (nota que $y_1,\ldots,y_j$ son aristas del grafo original) y dejemos que $C_1, \ldots, C_j$ sean los circuitos fundamentales de $y_1,\ldots,y_j$ con respecto a $S$ . Sea $K = \cup_i C_i$ . A partir de las definiciones se puede comprobar que el conjunto de vecinos de $Y'$ en $G'$ es $K - T$ , mientras que $Y' = K - S$ . Por lo tanto, queremos mostrar $|K - T| \geq |K - S|$ o, por el contrario $|K \cap T| \leq |K \cap S|$ . Para ver esto, observe que $K \cap S$ es un bosque de extensión en el subgrafo de $G$ inducido por $K$ : añadiendo cualquier arista de $K - S = Y'$ crearía un ciclo. Por otro lado $K \cap T$ es claramente un bosque en este subgrafo, por lo que tiene como máximo el tamaño de un bosque de extensión.

Nótese que esta prueba es constructiva, ya que podemos encontrar una correspondencia perfecta de $G'$ de manera eficiente. En el libro, el resultado se establece para los matroides en general, y de hecho la misma prueba funciona en el caso general después de sustituir "árbol de expansión" por "base" y "bosque" por "conjunto independiente".