Review for Test 3 (Chapters 4-5)

Question 1

Path

Answer 1

• Movement from one vertex to another by traversing edges

Question 2

Circuit

Answer 2

• Circuit

- When a path ends at the same vertex it started

Question 3

Euler Path

Answer 3

• A path that uses every edge once and only once but does not end up where it started

Question 4

Euler Circuit

Answer 4

• A circuit that uses every edge but never the same edge twice; begins and ends at the same vertex

Question 5

Hamiltonian Circuit

Answer 5

• A path that uses each vertex of the graph exactly once

Question 6

Planar Graph

Answer 6

• A graph that can be drawn so that no edges intersect each other

Question 7

Greedy Algorithm

Answer 7

• Start at a vertex
• Travel across the smallest number
• Don’t close circuit too quick
• Finish graph

Question 8

Edge-Picking Algorithm

Answer 8

• Start at the smallest number
• Keep picking small numbers until the circuit is complete
• Don’t end it too soon

Question 9

What is the difference between a path and a circuit?

Answer 9

• A path cannot repeat verticals or edges

- A circuit can repeat verticals but not edges

Question 10

Differences and similarities between a Euler Path and a Euler Circuit.

Answer 10

• They both travel every edge and hit every vertex
• The path starts at one vertex and ends at another
• The circuit starts at one vertex and ends at the one that it started at