- WELCOME TO A LESSON ON EULERIZATION.
NOT EVERY GRAPH HAS AN EULER PATH OR EULER CIRCUIT.
HOWEVER, THERE IS OFTEN STILL THE GOAL
OF FINDING AN EULER PATH OR CIRCUIT.
IF A GRAPH DOES NOT HAVE AN EULER PATH OR CIRCUIT,
ONE CAN BE CREATED BY DUPLICATING EDGES.
AS AN EXAMPLE, CONSIDER A POLICE OFFICER
PATROLLING A NEIGHBORHOOD ON FOOT
WANTING TO MINIMIZE THE AMOUNT OF WALKING.
IF THIS IS A DIAGRAM WITH A NEIGHBORHOOD
AND THE POLICE OFFICER'S REQUIRED TO WALK DOWN
EACH STREET AT LEAST ONCE.
IF THE POLICE OFFICER WANTS TO MINIMIZE WALKING
THE OFFICER MIGHT WANT TO PARK THEIR VEHICLE HERE,
WALK DOWN EACH STREET EXACTLY ONCE AND RETURN TO THE VEHICLE.
WHICH MEANS, THE OFFICER WOULD LIKE TO FIND AN EULER CIRCUIT
FOR THIS NEIGHBORHOOD.
WE CAN REPRESENT THIS NEIGHBORHOOD
USING THIS GRAPH HERE.
IN ORDER FOR AN EULER CIRCUIT TO EXIST
THE DEGREE OF EACH VERTEX MUST BE EVEN.
LET'S BEGIN BY DETERMINING THE DEGREE OF EACH VERTEX.
NOTICE HOW THESE VERTICES ALL HAVE DEGREE 2.
THIS VERTEX HAS DEGREE 4.
THE REMAINING FOUR VERTICES HAVE DEGREE 3.
SO BECAUSE NOT ALL THE VERTICES HAVE AN EVEN DEGREE,
THERE IS NO EULER CIRCUIT.
WHICH MEANS, IN ORDER TO PATROL THE NEIGHBORHOOD
THE OFFICER IS GOING TO HAVE TO DUPLICATE HIS EFFORTS
AND WALK DOWN CERTAIN STREETS MORE THAN ONCE.
NOW, TO CREATE AN EULER CIRCUIT WE'LL DUPLICATE EDGES
SO ALL THE DEGREES ARE EVEN.
AND WE CANNOT CREATE NEW EDGES.
WE CAN ONLY DUPLICATE EXISTING EDGES.
SO WE CANNOT CONNECT THESE TWO VERTICES HERE
BECAUSE THIS IS CREATING A NEW EDGE, WHICH IS NOT ALLOWED.
WE CAN THINK OF THIS AS TRYING TO CREATE A STREET
THROUGH SOMEONE'S PROPERTY,
WHICH WOULD NOT BE ALLOWED.
AND BECAUSE WE CANNOT CONNECT THE ODD VERTICES DIRECTLY,
WE'LL HAVE TO DUPLICATE EDGES ALONG THE PATH.
SO, FOR EXAMPLE, WE WANT TO CONNECT THIS VERTEX
TO THIS VERTEX,
WE'D HAVE TO DUPLICATE THIS EDGE, AS WELL AS THIS EDGE.
NOTICE NOW THAT A DEGREE OF THIS VERTEX IS 4,
AND SO IS THIS.
THE DEGREE OF THIS VERTEX IS NOW 6.
BUT NOW WE ALSO HAVE TO CONNECT THIS VERTEX TO THIS VERTEX.
SO WE'LL DUPLICATE THIS EDGE AND THIS EDGE.
SO NOW THIS VERTEX HAS DEGREE 4 AND SO DOES THIS.
AND THIS VERTEX NOW HAS DEGREE 8.
AND NOW BECAUSE ALL THE VERTICES HAVE AN EVEN DEGREE
WE CAN CREATE AN EULER CIRCUIT USING THIS GRAPH.
NOTICE HOW THE DUPLICATE EDGES WOULD REPRESENT
WHERE THE OFFICER WOULD HAVE TO WALK DOWN A STREET TWICE.
LET'S GO AHEAD AND FORMALIZE THE EULERIZATION PROCESS.
EULERIZATION IS THE PROCESS OF ADDING EDGES
TO CREATE AN EULER CIRCUIT.
IT CAN ALSO BE USED TO CREATE AN EULER PATH.
TO EULERIZE A GRAPH EDGES ARE DUPLICATED
TO CONNECT PAIRS OF VERTICES WITH ODD DEGREE.
CONNECTING TWO ODD VERTICES
INCREASES THE DEGREE OF EACH BY ONE
GIVING BOTH AN EVEN DEGREE.
WHEN TWO ODD VERTICES ARE NOT DIRECTLY CONNECTED,
AS WE SAW IN OUR EXAMPLE,
WE CAN DUPLICATE ALL THE EDGES IN A PATH CONNECTING THE TWO.
LET'S TAKE A LOOK AT ANOTHER EXAMPLE.
WE WANT TO EULERIZE THE GIVEN GRAPH.
WE WANT TO TRY TO FIND THE SHORTEST PATH
IF THE EDGES REPRESENT DISTANCE AND ARE DRAWN TO SCALE.
THEN FIND AN EULER CIRCUIT.
SO BECAUSE THE EDGES ARE DRAWN TO SCALE AND REPRESENT DISTANCE,
WHEN WE START DUPLICATING EDGES
WE WANT TO TRY TO DUPLICATE THE SHORT EDGES
RATHER THAN LONGER EDGES.
LET'S BEGIN BY CHECKING THE DEGREE OF EACH VERTEX.
NOTICE HOW WE HAVE DEGREE 3, DEGREE 3, 3, 3, 3, 3, 3.
EACH VERTEX HAS DEGREE 3.
BUT NOTICE IN THIS EXAMPLE, UNLIKE THE FIRST,
WE ARE ABLE TO CONNECT THE ODD VERTICES DIRECTLY.
BUT, AGAIN, BECAUSE WE'RE TRYING TO MINIMIZE THE TOTAL DISTANCE
WE WON'T DUPLICATE EDGE AB,
WE'LL DUPLICATE EDGE AH INSTEAD BECAUSE IT'S SHORTER,
IT REPRESENTS THE DISTANCE.
THE DISTANCE WOULD BE LESS.
SO WE'LL DUPLICATE AH HERE.
WE'LL DUPLICATE BG HERE.
WE'LL DUPLICATE CF HERE, AND DUPLICATE DE HERE.
NOTICE BY DOING THIS, NOW EACH VERTEX HAS DEGREE 4,
WHICH IS EVEN, AND NOW WE CAN FIND AN EULER CIRCUIT.
SO LET'S SAY WE START AT VERTEX "A".
WE NOW WANT TO USE EACH EDGE EXACTLY ONCE.
WHEN WE FINISH, RETURN TO VERTEX "A".
SO LET'S GO FROM VERTEX "A" TO VERTEX B TO BEGIN.
THEN LET'S GO FROM B TO G, AND THEN FROM G BACK TO B.
AND THEN FROM B TO C.
AND, AGAIN, LET'S GO FROM C TO F,
F BACK TO C, C TO D.
THAT WOULD BE SEVEN.
AND FROM D TO "A".
FROM "A" TO H.
NOW WE'LL GO AROUND THE INNER SQUARE,
SO H TO E.
THAT WOULD BE TEN.
WE FORGOT TO GO HERE,
SO LET'S GO AHEAD AND GO E TO D, AND THEN D BACK TO E.
AND THEN E TO F, F TO G, G TO H,
AND FINALLY RETURN BACK TO "A".
SO H TO "A".
SO THIS WOULD BE A POSSIBLE EULER CIRCUIT.
LET'S GO AHEAD AND GIVE IT AS A LIST.
AGAIN, WE STARTED AT "A,"
AND B, G BACK TO B, TO C, TO F, TO C,
TO D, AND THEN "A,"
TO H, TO E, TO D, BACK TO E, TO F, TO G, H, AND THEN "A".
AND OF COURSE THERE ARE SEVERAL OTHER POSSIBILITIES.
THE PROBLEM OF FINDING THE OPTIMAL EULERIZATION
IS CALLED THE CHINESE POSTMAN PROBLEM.
A NAME GIVEN BY AN AMERICAN
IN HONOR OF THE CHINESE MATHEMATICIAN MAKO QUAN
WHO FIRST STUDIED THE PROBLEM IN 1962
WHILE TRYING TO FIND OPTIMAL DELIVERY ROUTES
FOR POSTAL CARRIERS.
THIS PROBLEM IS IMPORTANT IN DETERMINING EFFICIENT ROUTES
FOR GARBAGE TRUCKS, SCHOOL BUSES, PARKING METER CHECKERS,
STREET SWEEPERS, AND MANY OTHER APPLICATIONS.
UNFORTUNATELY ALGORITHMS TO SOLVE THIS PROBLEM
ARE FAIRLY COMPLEX.
I THINK WE'LL GO AHEAD AND STOP HERE ON THIS LESSON.
I HOPE YOU FOUND THIS HELPFUL.