Discrete Math Review of 4.5 to 4.7

Front

A Hamilton Circuit must touch every __________ once and only once

Back

Vertex

Front

A graph in which every vertex is directly connected by a single edge to each of the other vertices is called a __________.

Back

Complete graph

Front

What is the Hamilton circuit using the nearest neighbor algorithm starting from vertex A?

Back

ADFECBA

Front

What is the difference between Euler circuits and Hamilton circuits?

Back

Euler circuits use every edge once and Hamilton circuits use every vertex once.

Front

The brute force algorithm for solving a Hamilton circuit is __________.

Back

optimal and inefficient

Front

What is a Hamiltonian cycle?

Back

A cycle in a graph that visits every vertex exactly once and returns to the starting vertex.

Front

Define an Euler circuit.

Back

A circuit that visits every edge of a graph exactly once and returns to the starting vertex.

Front

What is the main characteristic of a complete graph?

Back

Every pair of distinct vertices is connected by a unique edge.

Front

What is the nearest neighbor algorithm used for?

Back

To find an approximate solution for the Hamiltonian circuit problem.

Front

What does it mean for a graph to be isomorphic?

Back

Two graphs are isomorphic if there is a one-to-one correspondence between their vertices and edges that preserves adjacency.