12. Graph Theory

Using the graph below, determine if the sequence of vertices describes a Hamilton path (H.P.), a Hamilton circuit (H.C.), or neither.

$Q,P,U,R,S,T$

The weights on the graph below represent distances (in miles). Find the total distance (weight) of each path or circuit.

Home, Grocery Store, Post Office, Bank

Determine if the graph must have Hamilton circuits. If so, how many?

Note: We will be using the formula below.

Complete? ☐

# of vertices: ___

# of Hamilton circuits: ___

How many Hamilton circuits exist in a complete graph with the given number of vertices, $n$?

Note: We will be using the formula below.

$n=3$

The weights on the graph below represent distances (in miles). Find the total distance (weight) of each path or circuit.

Home, Grocery Store, Post Office, Bank, Home

How many Hamilton circuits exist in a complete graph with the given number of vertices, $n$ ?

Note: We will be using the formula below.

$n=12$

Using the graph below, determine if the sequence of vertices describes a Hamilton path (H.P.), a Hamilton circuit (H.C.), or neither.

$Q,U,P,Q,T,S,R$

Using the graph below, determine if the sequence of vertices describes a Hamilton path (H.P.), a Hamilton circuit (H.C.), or neither.

$P,Q,T,S,R,U,P$