- WELCOME TO A LESSON ON THE NUMBER OF ROUTES AND CIRCUITS
OF A COMPLETE GRAPH.
A COMPLETE GRAPH IS A GRAPH
IN WHICH EVERY VERTEX IS CONNECTED TO EVERY OTHER VERTEX.
HERE'S AN EXAMPLE OF SEVERAL COMPLETE GRAPHS.
LOOKING AT THE NOTATION,
THE SUB SCRIPTS REPRESENT THE NUMBER OF VERTICES
AND THE NUMBER AFTER THE COLON REPRESENTS THE NUMBER OF EDGES.
SUPPOSE WE HAD A COMPLETE GRAPH OF FIVE VERTICES
LIKE THE AIR TRAVEL GRAPH BELOW
WHICH WE SAW IN A PREVIOUS LESSON.
HOW MANY ROUTES VISIT EACH CITY ONCE?
WELL IF WE START AT HOME WHICH IS SEATTLE,
NOTICE HOW THERE ARE FOUR CHOICES OR FOUR CITIES
WE CAN VISIT.
L.A., CHICAGO, ATLANTA AND DALLAS.
SO WHEN DETERMINING THE NUMBER OF ROUTES,
WE'RE GOING TO FIND A PRODUCT
WHERE THE FIRST FACTOR IN THIS CASE WOULD BE FOUR.
NOTICE ONCE WE MAKE A SELECTION, AS AN EXAMPLE, LET'S SAY L.A.,
NOTICE HOW NOW THERE ARE THREE CHOICES.
IN THIS CASE, CHICAGO, ATLANTA OR DALLAS.
BECAUSE THERE ARE THREE CHOICES,
THE NEXT FACTOR IS GOING TO BE THREE.
AND NOW LET'S JUST SAY AS AN EXAMPLE WE SELECT CHICAGO
WHICH WOULD MAKE THAT SECOND SELECTION.
NOTICE HOW NOW THERE ARE TWO CHOICES,
IN THIS CASE ATLANTA OR DALLAS
WHICH GIVES US THIS FACTOR OF TWO.
AFTER WE MAKE OUR THIRD CHOICE,
THIS WILL SAY ATLANTA AS AN EXAMPLE.
NOTICE HOW THERE'S ONE REMAINING CHOICE,
IN THIS CASE DALLAS
WHICH GIVES US THIS LAST FACTOR OF ONE.
SO THE TOTAL NUMBER OF ROUTES IS EQUAL TO 4 x 3 x 2 x 1
OR 24 ROUTES.
ANOTHER WAY TO EXPRESS THIS PRODUCT IS FOUR FACTORIAL
WHICH AGAIN MEANS 4 x 3 x 2 x 1.
FOR EXAMPLE FIVE FACTORIAL WOULD BE 5 x 4 x 3 x 2 x 1.
NOW IF WE WANTED TO LIST ALL THE ROUTES TO VISIT EACH CITY
WE COULD MAKE A TREE DIAGRAM PICTURE HERE.
THE NICE THING ABOUT DOING THIS IS WE CAN SEE ALL 24 ROUTES.
THE ONE ROUTE THAT WE USE AS AN EXAMPLE
WAS IF WE START AT SEATTLE,
NOTICE HOW WE HAVE FOUR CHOICES.
SO IF WE SELECT FOR EXAMPLE L.A.,
NOTICE HOW FROM L.A. THERE ARE THREE CHOICES.
SO IF WE SELECT CHICAGO,
NOTICE HOW THERE ARE TWO REMAINING CHOICES
AND IF WE SELECT ATLANTA,
NOTICE HOW THERE'S ONLY ONE CHOICE LEFT WHICH IS DALLAS.
SO AGAIN AS A TREE WE CAN SEE ALL 24 ROUTES.
BUT WE'RE GOING TO BE MORE CONCERNED ABOUT CIRCUITS
SO TO FORM CIRCUITS,
WE ACTUALLY HAVE TO RETURN BACK TO THE HOME CITY OF SEATTLE.
WHEN WE CONVERT ROUTES TO CIRCUITS, WE DO HAVE REPETITION.
HALF OF THE CIRCUITS WILL BE DUPLICATES IN THE REVERSE ORDER.
SO WE'LL HAVE TO DIVIDE THE NUMBER OF ROUTES BY 2
TO DETERMINE THE NUMBER OF CIRCUITS IN A COMPLETE GRAPH.
SO IF WE HAVE -- VERTICES IN A COMPLETE GRAPH,
THERE WILL BE N - 1 FACTORIAL ROUTES
BUT WHEN FORMING CIRCUITS
HALF OF THESE ARE DUPLICATES IN REVERSE ORDER
SO THEY'LL BE N - 1 FACTORIAL
DIVIDED BY 2 UNIQUE HAMILTONIAN CIRCUITS.
FOR EXAMPLE, THE CIRCUIT "A," B, C, D, E, "A"
WOULD BE THE SAME CIRCUIT IN REVERSE ORDER
AS "A," E, D, C, B, "A."
AND AGAIN JUST TO REVIEW THIS EXCLAMATION SYMBOL,
IS RED FACTORIAL AND IN -- FOR THE PRODUCTS SEEN HERE BELOW.
LET'S TAKE A LOOK AT AN EXAMPLE.
HOW MANY ROUTES IN HAMILTONIAN CIRCUITS WITH A COMPLETE GRAPH
WITH SEVEN VERTICES HAVE.
NOTICE HOW THE COMPLETE GRAPH IS PROVIDED FOR US.
NOTICE HOW AS THE NUMBER OF VERTICES INCREASES,
TO COUNT THEM ONE AT A TIME WOULD BE VERY TIME CONSUMING.
SO THE NUMBER OF ROUTES WOULD BE N - 1 FACTORIAL
OR IN THIS CASE, N = 7.
WELL 7 - 1 = 6.
SO THE NUMBER OF ROUTES WOULD BE SIX FACTORIAL
WHICH WOULD BE 6 x 5 x 4 x 3 x 2 x 1.
SO BY HAND 6 x 5 IS 30, x 4 IS 120 x 3 IS 360 x 2 WOULD BE 720.
SO THERE ARE 720 POSSIBLE ROUTES VISITING ALL THE VERTICES.
ON THE CALCULATOR WE CAN JUST ENTER 6
AND THEN MATH ARROW OVER TO PROBABILITY,
ONE, TWO THREE RIGHT ARROWS.
OPTION FOUR IS THE FACTORIAL OPTION AND ENTER.
AND THEREFORE THE NUMBER OF CIRCUITS OR HAMILTONIAN CIRCUITS
WOULD BE N - 1 FACTORIAL DIVIDED BY 2
OR 6 FACTORIAL DIVIDED BY 2
WHICH WOULD BE 720 DIVIDED BY 2 OR 360.
AND IN OUR STUDY OF GRAPH THEORY,
WE'RE GOING TO BE MORE CONCERNED ABOUT HAMILTONIAN CIRCUITS
RATHER THAN ROUTES.
AS YOU CAN SEE FROM THIS TABLE,
NUMBER OF CIRCUITS IS GROWING EXTREMELY QUICKLY
AS THE NUMBER OF CITIES OR VERTICES INCREASE.
IF THE COMPUTER LOOKED AT ONE BILLION CIRCUITS A SECOND,
IT WOULD TAKE ALMOST TWO YEARS
TO EXAMINE ALL THE POSSIBLE CIRCUITS WITH ONLY 20 CITIES.
CERTAINLY THE BRUTE FORCE ALGORITHM
FOR LISTING ALL THE POSSIBLE CIRCUITS OUT
IS NOT AN EFFICIENT ALGORITHM.
I HOPE YOU FOUND THIS HELPFUL.