Ciclos de escritura de una gráfica como una combinación lineal de ciclos fundamentales.

Question

Es el folclore de que lo fundamental en los ciclos (correspondiente a aparticular spanning tree) de un gráfico constituyen una base para su ciclo de espacio, mientras que la prueba utiliza el lineal colonial fundamentales de los ciclos, así como algunos ortogonalidad argumentos (véase el capítulo 1 de Diestel del libro de Texto para obtener más contexto).

Pero no podía encontrar una manera constructiva para la escritura de un arbitrario ciclo como una combinación lineal de los fundamentales de los ciclos en la litrature, y mi esfuerzo personal también no llegar a ninguna parte.

Es allí cualquier manera de escribir la precisa combinación lineal, de preferencia puramente combinatoria?

Todas las respuestas y comentarios son apreciados.

Answer 1

Conocer el árbol de expansión $T$ que nos da el fundamental de los ciclos de $\{C_e : e \notin T\}$, no es un algoritmo simple: debido a un arbitrario ciclo de $C$, podemos escribir $C$ como la suma $$ C = \sum_{e \C \setminus T} C_e. $$ Es decir, tomamos todas las fundamentales de los ciclos correspondientes a los bordes de $C$ que no son bordes del árbol de $T$.

Esto funciona porque:

• Si $e \in C \setminus T$, luego nos deben incluir los fundamentales del ciclo de $C_e$, porque es la única fundamental ciclo que contiene el borde de la $e$, y debemos conseguir que el borde de algún lugar.
• Si $e \notin C \cup T$, entonces nosotros no incluyen los fundamentales del ciclo de $C_e$, debido a que contiene el borde de la $e$, que no pertenecen en $C$ y no puede ser cancelada por cualquier otro fundamentales del ciclo.

Por lo que la suma dada anteriormente es el único que podría funcionar. Por otro lado, tenemos algún tipo de prueba de que lo fundamental en los ciclos de la forma de la base, o al menos Diestel. Entonces hay una cierta suma que hace el trabajo, y por lo tanto es este.