About Hamilton Circuits
About Fibonacci Sequence
Hamilton Circuits
Fibonacci Numbers
Randomized
100
What is a HamiltonIan Circuit?
A circuit that must pass through each vertex of the graph once and only once.
100
What is the Fibonacci Sequence?
A sequence in which each number is the sum of the two preceding ones.
100
Circuit Weight
ABCDA 4+13+8+1=26
ABDCA. 4+9+8+2=23
ACBDA. 2+13+9+1=25
what algorithm is this and what is the most optimal circuit
The Brute Force Algorithm and ABDCA
100
Is this a Fibonacci Sequence?
0, 1, 1, 2, 3, 5
100
- List all possible Hamiltonian circuits
- Find the length of each circuit by adding the edge weights
- Select the circuit with minimal total weight.
What is this algorithm called?
Brute Force Algorithm
200
Since it is A circuit what must it do?
It must start and end at the same vertex.
200
If you take the ratio of two successive Fibonacci numbers what is it close to?
The Golden Ratio
200
How can you find unique circuits?
(n-1)!/2
200
Find the Fibonacci number when n = 4, using the recursive formula.
1. F(3) = F(2) + F(1) = 1 + 1 = 2
2. F(4) = F(3) + F(2) = 2 + 1 = 3
So, the Fibonacci number when n = 4 using the recursive formula is F(4) = 3 .
200
Who founded the Fibonacci Sequence?
Leonardo of Pisa
300
What is A Hamiltonian Path?
Visits every vertex once with no repeats but does not have to start and end at the same vertex.
300
What are one of the methods to find the Fibonacci Sequence
Golden Ratio Method or Recursive relation Method
300
How many circuits would a complete graph with 8 vertices have?
A complete graph with 8 vertices would have (8−1)!=7!=7⋅6⋅5⋅4⋅3⋅2⋅1=5040 possible Hamiltonian circuits. Half of the circuits are duplicates of other circuits but in reverse order, leaving 2520 unique routes.
300
Calculate the value of the 12th and the 13th term of the Fibonacci sequence, given that the 9th and 10th terms in the sequence are 21 and 34
The 12th and the 13th term of the Fibonacci sequence are 89 and 144
300
Founder of Hamiltonian Circuits
William Rowan Hamilton
400
What is the optimal Hamiltonian circuit?
The one with the lowest total weight.
400
Formula to calculate the Fibonacci Sequence:
Fn = Fn-1+Fn-2
400
What is the Nearest Neighbor Algorithm?
- Select a starting point.
- Move to the nearest unvisited vertex (the edge with smallest weight).
- Repeat until the circuit is complete.
400
The 14th term in the sequence is 377. Find the next term.
F15 = 377 × 1.618034
≈ 609.99 = 610
400
What else did Sir William Hamilton found
Icosian Calculus
500
What is the traveling salesman problem?
The problem that finds the optimization of the circuit and the lowest total weight.
500
The formula to calculate the Fibonacci numbers using the Golden Ratio is:
Xn = [φn – (1-φ)n]/√5
500
What is the circuit?
The resulting circuit is ADCBA with a total weight of 1+8+13+4=26.
500
What grand structure was built basing Fibonacci numbers
The Great Pyramids
500
What are my sources?
Turito. "Fibonacci Sequence." Turito, Turito, www.turito.com/blog/foundation/fibonacci-sequence.
Lippman, David. "Hamiltonian Circuits and the Traveling Salesman Problem." *Math in Society*, LibreTexts, math.libretexts.org/Bookshelves/Applied_Mathematics/Math_in_Society_(Lippman)/06%3A_Graph_Theory/6.06%3A_Hamiltonian_Circuits_and_the_Traveling_Salesman_Problem.
BYJU'S. "Fibonacci Sequence." BYJU'S, BYJU'S, www.byjus.com/maths/fibonacci-sequence/#Practice%20Problems.