Paths and cycles

Question 1

What is a network?

Answer 1

A graph that represents real life applications (eg: a road network)

Question 2

What is a walk?

Answer 2

Any route through a graph from vertex to vertex along connecting edges

Question 3

What is an open walk?

Answer 3

A route through a graph that starts and finishes at different vertices

Question 4

What is a closed walk?

Answer 4

A route through a graph that starts and finishes at the same vertex

Question 5

What is the length of a walk?

Answer 5

The number of edges of the walk

Question 6

What is a trail?

Answer 6

A route through a graph with no repeated edges

Question 7

What is an open trail?

Answer 7

A route through a graph with no repeated edges which starts and finishes different vertices

Question 8

What is a closed trail?

Answer 8

A route through a graph with no repeated edges which starts and finishes at the same vertex

Question 9

What is a closed trail also called?

Answer 9

A circuit

Question 10

What is a path?

Answer 10

A route through a graph with no repeat use of edges or vertices (except start/end vertex)

Question 11

What is an open path?

Answer 11

A route through a graph with no repeat use of edges or vertices which starts and finishes at different vertices

Question 12

What is a closed path?

Answer 12

A route through a graph with no repeat us of edges or vertices which starts and finishes at the same vertex

Question 13

What is the length of a path?

Answer 13

The number of edges of the path

Question 14

What is a bridge?

Answer 14

An edge in a connected graph that leaves the graph disconnected if removed

Question 15

What is a Eulerian trail?

Answer 15

A route through a connected graph with no repeated edges

Question 16

What is a Eulerian circuit?

Answer 16

A route through a connected graph with no repeated edges that starts and finishes at the same vertex

Question 17

What are the features of a Eulerian graph?

Answer 17

• Connected
• Has a closed trail (every edge travelled only once, starts and finished at same vertex)
• Only has even vertices

Question 18

What is a semi-Eulerian trail?

Answer 18

A route through a connected graph with no repeated edges that starts and finishes at different vertices

Question 19

What are the features of a semi-Eulerian graph?

Answer 19

• Has semi-Eulerian trail (connected, no repeated edges, starts and finishes at different vertices)
• Exactly 2 odd vertices

Question 20

What is a Hamiltonian path?

Answer 20

• A route through a graph with no repeated edges or vertices that includes every vertex in the graph
• Starts and finishes at different vertices

Question 21

What is a Hamiltonian cycle?

Answer 21

• A route through a graph with no repeated edges of vertices that includes every vertex in the graph
• Starts and finishes at the same vertex

Question 22

What are the features of a Hamiltonian graph?

Answer 22

• Has Hamiltonian cycle (starts and finishes at same vertex, includes every vertex only once)
• Connected

Question 23

What are the features of a semi-Hamiltonian graph?

Answer 23

• Connected
• Contains Hamiltonian path (starts and finishes at different vertices, includes every vertex only once) but not Hamiltonian cycle