Network Concepts

Question 1

Walk

Answer 1

connected sequence of edges where the edges and vertices may be visited multiple times

Question 2

Trail

Answer 2

walk with no repeated edges (but repeated vertices)

Question 3

Path

Answer 3

walk with no repeated vertices or edges

Question 4

Circuit

Answer 4

walk with no repeated edges that starts and ends at the same vertex (but repeated vertices)

Question 5

Cycle

Answer 5

walk with no repeated edges or vertices that starts and end at the same vertex

Question 6

Traversable Graph

Answer 6

trail that includes every edge without repeating an edge or taking pen off paper

(used in practical problems)

Question 7

Eulerian trail

Answer 7

uses every edge exactly once, starts and ends at DIFFERENT vertices

(exist if: graph has exactly 2 vertices with an odd degree OR all even degrees)

Question 8

Eulerian circuit

Answer 8

uses every edge exactly once, starts and ends at SAME vertex

exist if: every vertex has an even degree

Question 9

Hamilton path

Answer 9

passes through every vertex of a graph once and only once

Question 10

Hamilton cycle

Answer 10

hamilton path that starts and finishes at same vertex