- WELCOME TO A LESSON ON EULER PATHS AND EULER CIRCUITS.
AN EULER PATH IS A PATH THAT USES EVERY EDGE IN A GRAPH
WITH NO REPEATS.
BEING A PATH,
IT DOES NOT HAVE TO RETURN TO THE STARTING VERTEX.
SO LOOKING AT THIS FIRST GRAPH HERE,
THERE'S MORE THAN ONE WAY TO FORM A EULER PATH.
FOR EXAMPLE, IF WE START AT VERTEX C, WE GO FROM C TO B,
FROM B TO "A," FROM "A" TO C, AND C TO D.
THIS IS AN EULER PATH
BECAUSE WE USED EVERY EDGE EXACTLY ONE TIME
WITH NO REPEATS.
TO SHOW THE PATH WE CAN USE ARROWS LIKE WE DID HERE,
OR SOMETIMES YOU'LL SEE THE EDGES NUMBERED.
FOR EXAMPLE, HERE WE'D HAVE 1, 2, 3, AND 4.
JUST DON'T CONFUSE THIS NUMBERING
WITH THE WEIGHT OF THE EDGES.
LOOKING AT OUR SECOND EXAMPLE HERE,
IF WE START AT VERTEX "A" WE COULD GO FROM "A" TO B,
"B" TO C, C TO "A," "A" TO D, AND D TO C.
SO, AGAIN, WE START AT "A," ENDED AT C,
USED ALL THE EDGES EXACTLY ONCE.
OR, AGAIN, IF WE NUMBER THESE WE'D HAVE 1, 2, 3, 4, AND 5.
ON EULER CIRCUIT IS A CIRCUIT THAT USES EVERY EDGE IN A GRAPH
WITH NO REPEATS.
BEING A CIRCUIT, THAT MEANS IT MUST START AND END
AT THE SAME VERTEX.
SO AN EULER PATH DOES NOT HAVE TO START AND END
AT THE SAME VERTEX
BUT AN EULER CIRCUIT DOES.
SO, FOR EXAMPLE, IF WE START AT LIKE LET'S SAY VERTEX B,
WE COULD GO FROM B TO "A," "A" TO E, BACK TO B, TO C, TO D,
TO E, AND BACK TO B.
NOTICE HOW WE BEGAN AT B, ENDED AT B,
AND USED EACH EDGE EXACTLY ONCE.
SO WE'D HAVE 1, 2, 3, 4, 5, 6, AND 7.
BUT NOT ALL GRAPHS HAVE EULER PATHS AND EULER CIRCUITS,
WHICH LEADS US TO EULER PATH AND CIRCUIT THEOREMS.
A GRAPH WILL CONTAIN AN EULER PATH
IF IT CONTAINS AT MOST TWO VERTICES OF ODD DEGREE.
A GRAPH WILL CONTAIN AN EULER CIRCUIT
IF ALL VERTICES HAVE EVEN DEGREE.
NOTICE HOW THESE THEOREMS DO NOT TELL US
HOW TO FIND THE EULER PATH OR CIRCUIT.
IT JUST TELLS US IF ONE EXIST.
AND JUST TO REVIEW, REMEMBER THE DEGREE OR VALANCE OF A VERTEX
IS A NUMBER OF EDGES MEETING AT THAT VERTEX.
LET'S TAKE A LOOK AT SOME MORE EXAMPLES.
WE WANT TO DETERMINE IF EACH GRAPH HAS AN EULER PATH,
AND IF IT HAS ONE WE WANT TO FIND AN EULER PATH.
SO, AGAIN, REMEMBER WE'RE FIRST GOING TO CHECK TO SEE
IF THERE ARE AT MOST TWO VERTICES OF ODD DEGREE.
SO LOOKING AT OUR FIRST GRAPH HERE,
NOTICE HOW VERTEX B HAS DEGREE 2, SO DOES VERTEX "A," E, AND D.
BUT VERTEX C AND F HAVE DEGREE 3.
NOTICE HOW IT DOES SATISFY THE REQUIREMENT
TO HAVE AN EULER PATH.
IT HAS TWO VERTICES OF ODD DEGREE WHICH IS OKAY.
SO WE CAN SAY THE GRAPH DOES HAVE AN EULER PATH.
AND NOW LETS FIND ONE.
SO WE WANT TO START AT A VERTEX AND FORM A PATH
THAT USES EVERY EDGE EXACTLY ONCE.
LET'S SAY WE TRY BEGINNING AT VERTEX B.
WE COULD GO FROM VERTEX B TO VERTEX "A,"
VERTEX "A" TO VERTEX F,
AND VERTEX F TO VERTEX E, E TO D, D TO C.
AND NOW WE HAVE A PROBLEM.
IF WE GO FROM C TO F WE'LL HAVE TO BACKTRACK,
WE'RE USING EDGE MORE THAN ONCE TO GET BACK TO B.
IF WE GO TO B NOW WE HAVEN'T USED EDGE CF.
SO OUR CURRENT PATH IS NOT GOING TO GIVE US AN EULER PATH.
SO LET'S GO AHEAD AND TRY AGAIN.
REMEMBER THE THEOREM TELLS US IF WE HAVE A PATH,
IT DOESN'T TELL US HOW TO FIND IT.
SO NOW LET'S BEGIN AT VERTEX C.
LET'S TRY GOING TO D, AND THEN E, AND THEN F.
LET'S GO BACK UP TO C, AND THEN FROM C TO B, B TO "A,"
AND "A" TO F.
I THINK WE FOUND IT.
WE STARTED AT C AND ENDED AT F,
AND USED EACH EDGE EXACTLY ONE TIME.
SO, AGAIN, WE HAD 1, 2, 3, 4, 5, 6, 7, AND WE WERE DONE.
SO WE CAN SAY THE EULER PATH WOULD BE C, D, E, F,
BACK TO C, B, A, F.
NOW LETS TAKE A LOOK AT OUR SECOND EXAMPLE.
WE'LL BEGIN BY DETERMINING THE DEGREE OF EACH VERTEX.
SO HERE WE HAVE DEGREE 3, HERE WE HAVE DEGREE 3,
HERE WE HAVE DEGREE 3.
ACTUALLY WE'RE DONE NOW
BECAUSE REMEMBER WE CAN HAVE AT MOST 2 VERTICES OF ODD DEGREE.
SO WE CAN STOP HERE AND SAY THE GRAPH
DOES NOT HAVE AN EULER PATH.
NOW LETS REVISIT EULER CIRCUITS.
A GRAPH WILL CONTAIN AN EULER CIRCUIT
IF ALL VERTICES HAVE EVEN DEGREE.
WE WANT TO DETERMINE IF EACH GRAPH HAS AN EULER CIRCUIT,
AND IF IT HAS ONE WE WANT TO FIND AN EULER CIRCUIT.
WE'LL BEGIN BY DETERMINING THE DEGREE OF EACH VERTEX.
SO WE HAVE DEGREE 2, DEGREE 2, DEGREE 4, DEGREE 4, DEGREE 2,
AND DEGREE 2.
ALL THE VERTICES HAVE EVEN DEGREE.
THEREFORE, THIS GRAPH DOES HAVE AN EULER CIRCUIT.
SO NOW WE'LL FIND AN EULER CIRCUIT.
SO WE'LL BEGIN AT ONE VERTEX,
FORM A PATH USING ALL EDGES EXACTLY ONE TIME,
RETURNING TO THE STARTING VERTEX.
SO IF WE START AT VERTEX C LET'S GO TO VERTEX B, TO "A," TO F,
BACK TO C, TO D, TO E, TO F, AND BACK TO C.
SO WE STARTED AT C, WENT TO B, TO "A," TO F, TO C, TO D, TO E,
TO F, AND BACK TO C.
SO EULER CIRCUIT--
SO THE EULER CIRCUIT,
AGAIN, IS C, B, A, F, C, D, E, F, AND BACK TO C.
AND YOU MAY'VE NOTICED THIS WAS A CIRCUIT, IT'S NOT UNIQUE.
LOOKING AT OUR SECOND GRAPH
CAN QUICKLY SEE THAT VERTEX B HAS TO DEGREE 2,
BUT VERTEX C HAS DEGREE 3.
AS SOON AS WE KNOW A VERTEX HAS AN ODD DEGREE, WE CAN STOP,
THE GRAPH WILL NOT HAVE AN EULER CIRCUIT.
NOW, YOU MIGHT BE ASKING,
WHY DO WE CARE IF AN EULER CIRCUIT EXIST.
THINK BACK TO OUR POLICE OFFICER ON PATROL
FROM A PREVIOUS EXAMPLE.
THE POLICE OFFICER WANTED TO PATROL A NEIGHBORHOOD ON FOOT
BY WALKING AS LITTLE AS POSSIBLE.
THE IDEAL SITUATION WOULD BE A CIRCUIT
THAT COVERS EVERY STREET WITH NO REPEATS,
AND THAT'S AN EULER CIRCUIT.
LUCKILY, WE'LL SOLVE THE QUESTION
OF WHETHER OR NOT AN EULER PATH OR CIRCUIT WILL EXIST.
SO LOOKING AT OUR GRAPH HERE,
NOTICE HOW VERTICES "A," F, C, AND D ALL HAVE DEGREE 2.
VERTICES B AND E HAVE DEGREE 4.
BECAUSE ALL THE VERTICES HAVE AN EVEN DEGREE,
WE CAN EASILY DETERMINE THIS GRAPH
DOES HAVE AN EULER CIRCUIT,
WHICH WE ACTUALLY FOUND BY TRIAL AND ERROR IN A PREVIOUS LESSON.
ONE POSSIBILITY WOULD BE TO START AT E, TO D, TO C, TO B,
BACK TO E, TO F, TO "A," TO B, AND FINALLY BACK TO E.
AGAIN, THE EULER CIRCUIT WAS TO FOLLOW THIS PATH,
1, 2, 3, 4, 5, 6, 7, AND 8.
I HOPE YOU FOUND THIS HELPFUL.