Hamiltonian Circuits and Complete Graphs

This video tutorial explains the concepts of routes and circuits in complete graphs. It begins with an introduction to complete graphs, where every vertex is connected to every other vertex. The tutorial then demonstrates how to calculate the number of routes visiting each city once using factorials and tree diagrams. It further explains how to convert these routes into circuits, accounting for duplicates. An example with a complete graph of seven vertices is provided, illustrating the calculation of routes and circuits. The video concludes with insights into the complexity of circuits in graph theory, highlighting the inefficiency of brute force algorithms.

What is a complete graph?

• A graph with a single edge.

• A graph where each vertex is connected to every other vertex.

• A graph with no edges.

• A graph with only one vertex.

In a complete graph with five vertices, how many routes visit each city once?

• 24

• 48

• 12

• 60

What is the factorial notation for the number of routes in a complete graph with four choices?

• 3!

• 5!

• 6!

• 4!

How do Hamiltonian circuits differ from routes in a complete graph?

• They include all possible routes.

• They do not return to the starting point.

• They return to the starting point and have no duplicates.

• They return to the starting point and have duplicates in reverse order.

How many unique Hamiltonian circuits are there in a complete graph with five vertices?

• 24

• 12

• 60

• 48

What is the formula for calculating the number of routes in a complete graph with n vertices?

• n factorial

• (n-1) factorial

• n squared

• n cubed

In a complete graph with seven vertices, how many possible routes are there?

• 120

• 360

• 720

• 840

How many Hamiltonian circuits are there in a complete graph with seven vertices?

• 180

• 360

• 720

• 540

Why is the brute force algorithm not efficient for listing all possible circuits?

• It only works for graphs with even numbers of vertices.

• It cannot handle graphs with more than 10 vertices.

• It is too slow for large graphs.

• It requires too much memory.

How long would it take a computer to examine all possible circuits with 20 cities at one billion circuits per second?

• Almost two years

• Almost two months

• Almost two weeks

• Almost two days