In a graph, I understand a cycle to be a traversal from Node A, traversing each (but not every) vertex once, and returning to Node A. Now I THINK a distinct cycle is where they don't share any vertices, but I might be wrong. Can someone clear this up for me?
Asked
Active
Viewed 3,129 times
1
-
2No matter what the mathematical objects in question, ‘$x$ and $y$ are distinct widgets’ normally means simply that $x$ and $y$ are widgets, and $x\ne y$. You’re thinking of vertex-disjoint cycles; one can also have edge-disjoint cycles and cycles that are disjoint in both senses. – Brian M. Scott Jan 12 '13 at 20:57
-
So you're saying, for example the Cycle S = {2,3,4,5,2} and Cycle P = {2,3,4,2} are distinct because S /= P? – notverygoodatmaths Jan 12 '13 at 20:59
-
Yes, as the word distinct is normally used. – Brian M. Scott Jan 12 '13 at 21:02
1 Answers
1
(Expanding the comment by Brian M. Scott): being distinct is not a property of a cycle, but a relation between two cycles. Two cycles are distinct if they are not the same cycle.
Usage example: "For all $n\ge 3$, the number of distinct Hamilton cycles in the complete graph $K_n$ is $(n−1)!/2$."
Related story from MathOverflow:
Q: "Are the groups $G_1$ and $G_2$ isomorphic?"
A: "$G_1$ is, but $G_2$ isn't."
ˈjuː.zɚ79365
- 3,004