What is the rule to determine if a network is traversible or not???
What is the rule that helps to determine if a network is traversible or not, without attempting to draw it?
I think it has something to do with the number of odd and even vertices.
Any help is greatly appreciated! I just need the rule for this.
Thank you!! :)
1 Answer | Add Yours
By traversible, I assume you mean that you can go over each edge exactly once, and return to the starting vertex. This is known as an Euler circuit.
For a graph to have an Euler circuit, the graph must be connected (there must be a path from a vertex to any other vertex on the graph) and the valence of each vertex must be even. (valence is the number of edges coming into a vertex)
If you meant visiting each vertex exactly once and return to the starting vertex, this is a Hamiltonian circuit, and there is no known way to determine the existence of such a circuit without actually finding one, at least in a general graph. There are graphs that definitely have Hamiltonian circuits (complete graphs, for example).
We’ve answered 319,815 questions. We can answer yours, too.Ask a question