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...

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

embizze's profile pic

embizze | High School Teacher | (Level 1) Educator Emeritus

Posted on

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).

Sources:

We’ve answered 318,957 questions. We can answer yours, too.

Ask a question