Teoría de Grafos+ Teoría de Números.

Question

El problema: Dejemos que $G$ sea un gráfico conectado. Sea $T$ sea un árbol de expansión de $G.$ Demostrar que $T$ contiene un subgrafo de extensión $T'$ tal que, para cada vértice $ v$ El grado de $v$ en $G$ y el grado de $v$ en $T'$ son iguales en el módulo $2.$

He probado un par de ejemplos pero no he conseguido intuir este problema, cualquier pista/sugerencia será muy apreciada.

Answer 1

Aquí hay una prueba algebraica. ¿Has aprendido alguna vez Estructura de Datos (me especializo en ciencias de la computación...)? Un tipo de matriz llamada matriz de incidencia se define como sigue: Es una $|V|*|E|$ matriz en $GF(2)$ .Si el borde $e_i=(v_i,v_j)$ entonces $(v_i,e_i)=1 , (v_i,e_j)=1 $ ,si no $(v,e)=0$ .

Es noche profunda en China y tengo mucho sueño, pero realmente quiero ofrecer ayuda.Así que hago un dibujo para usted sin usar Latex para ilustrar la matriz y el gráfico, fácil de ver, se corresponden entre sí.

$\textbf{Lemma 1}$ ：Las columnas de la matriz del árbol de expansión $T$ (que está rodeado por la línea de puntos) es el conjunto lineal independiente máximo del espacio de columnas de la matriz de incidencia de G(denotado por $M$ ).

$\textbf{Proof}$ Son linealmente independientes porque no hay círculos en un árbol (si las columnas son linealmente dependientes, esas aristas formarán un círculo).

$\textbf{Lemma2}$ Hay $|V|-1$ columnas en la matriz del árbol de expansión.

$\textbf{Proof}$ Es fácil. Para un árbol, $|E|=|V|-1$ .

$\textbf{Lemma3}$ Si $M$ es una matriz (de incidencia) de un árbol de expansión, entonces no contiene una fila cero.

¿Por qué? Porque en un árbol de expansión, cada vértice está conectado al menos a una arista, y sólo a una.

$M$ se denota como la matriz de incidencia de $G$ . Entonces nuestro objetivo es: $\textbf{Select columns from spanning tree matrix and form them into a new matrix N,such that}$ $\textbf{for every row of $ M,N $,the sum of elements of $ M $ equals the sum of elements of $ N $.}$ La suma significa aquí exclusiva o $\oplus$ Porque la suma de filas indica el grado de los vértices. Por ejemplo, en la imagen proporcionada, $deg(v_1)=3$ y la suma de la primera fila es $3$ Si en $GF(2)$ , $3$ mod $2$ = $1$ y $1 \oplus 1 \oplus 1 = 1$ .

Si la primera fila no satisface nuestro objetivo, elija una columna $j$ que $M_{1,j}$ =1 (Como se demostró en el lema 3, no hay fila cero) y eliminar esa columna (Así que la primera fila debe satisfacer).Y hacer lo mismo de nuevo en la segunda fila...

A veces $T^{'}$ tiene que ser un gráfico vacío, por ejemplo, $G$ es un triángulo. Tres vértices, tres aristas.