AMDM - Unit 4 Test Part I

Front

What is a Hamiltonian Circuit?

Back

A Hamiltonian Circuit is a path in a graph that visits each vertex exactly once and returns to the starting vertex.

Front

What is a Hamiltonian Path?

Back

A Hamiltonian Path is a path in a graph that visits each vertex exactly once but does not return to the starting vertex.

Front

What is an Euler Circuit?

Back

An Euler Circuit is a path in a graph that visits every edge exactly once and returns to the starting vertex.

Front

What is an Euler Path?

Back

An Euler Path is a path in a graph that visits every edge exactly once but does not return to the starting vertex.

Front

What condition must be met for a graph to have an Euler Circuit?

Back

A graph has an Euler Circuit if all vertices have even degree.

Front

What condition must be met for a graph to have an Euler Path?

Back

A graph has an Euler Path if it has exactly two vertices of odd degree.

Front

What is the degree of a vertex?

Back

The degree of a vertex is the number of edges connected to it.

Front

Can a graph with more than two odd vertices have an Euler Path?

Back

No, a graph with more than two odd vertices cannot have an Euler Path or Circuit.

Front

What is the significance of the starting and ending vertex in a circuit?

Back

In a circuit, the starting and ending vertex must be the same.

Front

What is the significance of the starting and ending vertex in a path?

Back

In a path, the starting and ending vertex can be different.