what is a fundamental cycle in graph theory? what does it imply? I already looked it up in wikipedia but it says very little
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Let $G$ be a connected graph, and let $T$ be a spanning tree of $G$. Let $e$ be an edge in $G$ between vertices $v$ and $w$ that is not in $T$. Now in $T$ there is a unique path between $v$ and $w$, and since $e$ is not in $T$, that path does not use $e$. Therefore, that path together with $e$ forms a cycle in $G$. A cycle built this way is called a fundamental cycle.
One nice consequence of fundamental cycles is that the set of them forms a basis for the cycle space of the graph. This means that every Eulerian subgraph of $G$ is can be written as the symmetric difference of fundamental cycles. And perhaps more importantly, it quickly gives you the dimension of the cycle space: If $G$ has $n$ vertices and $m$ edges, then there are $m-(n-1)$ edges not in $T$ and so the dimension of the cycle space is $m-n+1$.
If $G$ is not connected, replace above the word "spanning tree" by "maximum spanning forest," where maximum means it uses as many edges as possible, and $m-n+1$ by $m-n+c$, where $c$ is the number of components of $G$.
