Tip:
Highlight text to annotate it
X
- WELCOME TO A LESSON ON HAMILTONIAN CIRCUITS.
INSTEAD OF LOOKING FOR A CIRCUIT THAT COVERS EVERY EDGE ONCE,
SOMETIMES WE'RE INTERESTED IN A CIRCUIT
THAT VISITS EVERY VERTEX ONCE.
THIS CONCEPT WOULD BE HELPFUL, FOR EXAMPLE,
FOR A DELIVERY PERSON WANTING TO STOP AT EVERY DELIVERY LOCATION
RATHER THAN GOING DOWN EVERY STREET.
FOR EXAMPLE, IF A DELIVERY PERSON NEEDED TO VISIT
EACH VERTEX EXACTLY ONCE FOR DELIVERIES
THEY MIGHT START HERE, GO IN THIS DIRECTION,
TURN, GO IN THIS DIRECTION,
TURN, AND THEN GO IN THIS DIRECTION.
NOTICE HOW THIS WOULD BE A PATH RATHER THAN A CIRCUIT
BECAUSE THE STARTING VERTEX AND ENDING VERTEX ARE NOT THE SAME.
AND NOTICE HOW THE DELIVERY PERSON
COULD ALSO TAKE DIFFERENT ROUTES
AND STILL VISIT EACH VERTEX EXACTLY ONCE.
FOR EXAMPLE, THE DELIVERY PERSON, AGAIN, MIGHT START HERE,
GO IN THIS DIRECTION,
TURN AND GO IN THIS DIRECTION,
TURN AND GO IN THIS DIRECTION,
TURN AND GO IN THIS DIRECTION,
AND TURN AGAIN HERE.
SO THE DELIVERY PERSON WOULD START HERE AND END HERE.
AND, AGAIN, NOTICE HOW THIS IS NOT A CIRCUIT, IT IS A PATH,
BUT IT DOES VISIT EACH VERTEX EXACTLY ONE TIME.
WHICH LEADS US TO THE DEFINITIONS
OF HAMILTONIAN CIRCUITS AND HAMILTONIAN PATHS.
A HAMILTONIAN CIRCUIT IS A CIRCUIT
THAT VISITS EVERY VERTEX ONCE WITH NO REPEATS.
BEING A CIRCUIT, IT MUST START AND END AT THE SAME VERTEX.
A HAMILTONIAN PATH, WHICH WE SAW IN OUR PREVIOUS EXAMPLE,
ALSO VISITS EVERY VERTEX ONCE WITH NO REPEATS,
BUT DOES NOT HAVE TO START AND END AT THE SAME VERTEX.
AND HAMILTONIAN CIRCUITS ARE NAMED AFTER
WILLIAM ROWAN HAMILTON
WHO STUDIED THEM IN THE 1800's.
LET'S TAKE A LOOK AT A COUPLE MORE EXAMPLES.
LET'S TAKE A LOOK AT ANOTHER EXAMPLE.
LET'S SEE IF WE CAN FIND A HAMILTONIAN CIRCUIT
FOR THIS GRAPH HERE.
WHICH MEANS, IF WE START HERE
WE WANT TO VISIT EACH VERTEX EXACTLY ONE TIME
AND RETURN TO THIS VERTEX.
SO WE COULD START IN THIS DIRECTION,
TURN, TURN, TURN, AND KEEP THIS PATTERN GOING.
TURN AND GO ALL THE WAY TO HERE
AND RETURN TO THE STARTING VERTEX.
THIS IS AN EXAMPLE OF A HAMILTONIAN CIRCUIT.
WE STARTED HERE, VISITED EACH VERTEX EXACTLY ONE TIME,
AND ENDED BACK AT THE SAME VERTEX.
A HAMILTONIAN PATH ALSO VISITS EVERY VERTEX ONCE
WITH NO REPEATS,
BUT DOES NOT HAVE TO START AND END AT THE SAME VERTEX.
AND WE SAW A COUPLE OF THESE
USING OUR DELIVERY PERSON EXAMPLE.
LET'S SEE IF WE CAN FIND A HAMILTONIAN PATH FOR THIS GRAPH.
SO WE'LL CLEAR THE HAMILTONIAN CIRCUIT.
SO WE'LL START HERE AGAIN,
AND NOTICE HOW WE CAN GO IN THIS DIRECTION
ALL THE WAY TO THE END.
TURN, GO ALL THE WAY BACK IN THIS DIRECTION,
TURN, AND GO BACK IN THIS DIRECTION.
NOTICE HOW WE STARTED HERE,
VISITED EACH VERTEX EXACTLY ONE TIME,
AND ENDED HERE, A DIFFERENT LOCATION.
THIS IS AN EXAMPLE OF A HAMILTONIAN PATH.
NOW, IT'S IMPORTANT TO RECOGNIZE THAT UNLIKE EULER CIRCUITS,
THERE'S NO NICE THEOREM THAT ALLOWS US TO INSTANTLY DETERMINE
WHETHER OR NOT A HAMILTONIAN CIRCUIT EXIST FOR ALL GRAPHS.
LET'S TAKE A LOOK AT ANOTHER EXAMPLE.
WE WANT TO DETERMINE IF A HAMILTONIAN PATH OR CIRCUIT
EXISTS ON THE GRAPH BELOW.
LET'S FIRST CONSIDER A HAMILTONIAN CIRCUIT.
LOOKING AT THE GRAPH,
NOTICE HOW IF WE WERE TO START AT THIS VERTEX HERE
THERE'S NO WAY THAT WE COULD VISIT EACH VERTEX
EXACTLY ONE TIME
AND RETURN BACK AT THIS VERTEX
BECAUSE OF THIS SINGLE EDGE HERE.
SO A HAMILTONIAN CIRCUIT DOES NOT EXIST.
LET'S SEE IF WE CAN FIND A HAMILTONIAN PATH,
MEANING WE COULD START HERE,
VISIT EACH VERTEX EXACTLY ONE TIME,
BUT WE DON'T HAVE TO END BACK AT THIS VERTEX.
SO WE COULD GO IN THIS DIRECTION,
MAYBE TURN AND GO IN THIS DIRECTION,
TURN AND GO IN THIS DIRECTION.
TURN AND GO IN THIS DIRECTION,
TURN, TURN, AND TURN.
THIS WILL BE A POSSIBLE HAMILTONIAN PATH.
NOTICE HOW WE VISITED EACH VERTEX EXACTLY ONE TIME
WITH NO REPEATS,
AND THEREFORE THIS IS A POSSIBLE HAMILTONIAN PATH.
WITH HAMILTONIAN CIRCUITS OUR FOCUS WILL NOT BE ON EXISTENCE
BUT ON THE QUESTION OF OPTIMIZATION.
GIVEN A GRAPH WHERE THE EDGES HAVE WEIGHTS,
WE WANT TO FIND THE OPTIMAL HAMILTONIAN CIRCUIT,
WHICH WOULD BE THE ONE WITH THE LOWEST TOTAL WEIGHT.
WHICH BRINGS US TO A FAMOUS PROBLEM CALLED
THE TRAVELING SALESMAN PROBLEM, OR TSP FOR SHORT.
THIS PROBLEM IS CALLED THE TRAVELING SALESMAN PROBLEM
BECAUSE THE QUESTION CAN BE FRAMED LIKE THIS,
SUPPOSE A SALES PERSON NEEDS TO GIVE SALES PITCHES
IN FOUR CITIES DIFFERENT FROM THEIR HOME CITY.
HE LOOKS AT THE AIR FAIRS BETWEEN EACH CITY
AND PUTS THE COST IN A GRAPH, AS WE SEE HERE BELOW.
IN WHAT ORDER SHOULD HE TRAVEL TO VISIT EACH CITY ONCE
THEN RETURN HOME WITH THE LOWEST COST?
LET'S LOOK AT ONE POSSIBLE HAMILTONIAN CIRCUIT.
IF THE SALESMAN STARTS HERE IN SEATTLE,
LET'S SAY MAYBE THEY FLY TO L.A., WHICH WOULD COST $70.
AND THEN FROM L.A. LETS SAY TO CHICAGO FOR $100,
THEN MAYBE TO DALLAS FOR $165,
THEN TO ATLANTA,
AND FINALLY BACK HOME TO SEATTLE.
NOTICE USING THIS HAMILTONIAN CIRCUIT,
THE TOTAL COST WOULD BE $70 + $100 + $165 + $85,
AND THEN FINALLY BACK HOME FOR $140.
SO IF THIS TRIP PLAN THE TOTAL COST WOULD BE $560.
BUT THE REAL QUESTION IS
WHICH TRAVEL PLANS WOULD BE THE CHEAPEST FOR THE SALESMAN.
SO WE'LL BE CONSIDERING SEVERAL EXAMPLES SIMILAR TO THIS
IN THE NEXT SEVERAL VIDEOS.
I HOPE YOU FOUND THIS HELPFUL.