- WELCOME TO INTRODUCTION TO GRAPH THEORY.
IN THIS LESSON WE WILL DEFINE GRAPHS
AND ALSO DEFINE COMMON GRAPH THEORY VOCABULARY.
IN THE MODERN WORLD PLANNING EFFICIENT ROUTES IS ESSENTIAL
FOR BUSINESS AND INDUSTRY
WITH APPLICATIONS AS VARIED AS PRODUCT DISTRIBUTION,
LAYING NEW FIBER OPTIC LINES FOR BROADBAND INTERNET,
AND SUGGESTING NEW FRIENDS WITHIN SOCIAL NETWORK SITES
LIKE FACEBOOK.
THE FIELD OF GRAPH THEORY STARTED NEARLY 300 YEARS AGO,
AS A LOOK INTO A MATHEMATICAL PUZZLE
CALLED THE SEVEN BRIDGES PROBLEM.
THE FIELD HAS EXPLODED IN IMPORTANCE IN THE LAST CENTURY,
BOTH BECAUSE OF THE GROWING COMPLEXITY OF BUSINESS
IN A GLOBAL ECONOMY
AND BECAUSE OF THE COMPUTATIONAL POWER
THAT COMPUTERS CAN PROVIDE US.
AS AN EXAMPLE, CONSIDER A POLICE OFFICER
PATROLLING A NEIGHBORHOOD ON FOOT.
THAT YIELD PATROL ROUTE WOULD NEED TO COVER EACH BLOCK
WITH THE LEAST AMOUNT OF BACKTRACKING OR NO BACKTRACKING
TO MINIMIZE THE AMOUNT OF WALKING.
THE ROUTE SHOULD ALSO BEGIN AND END AT THE SAME POINT
WHERE THE OFFICER PARKS HIS OR HER VEHICLE.
WE'LL USE THIS EXAMPLE TO COVER SOME OF THE BASIC GRAPH THEORY
OR NETWORK ANALYSIS VOCABULARY.
A GRAPH IS A FINITE SET OF DOTS IN CONNECTING LENGTHS.
THE DOTS ARE CALLED VERTICES OR NOTES,
AND THE LENGTHS ARE CALLED EDGES.
A GRAPH CAN BE USED TO SIMPLIFY A REAL LIFE MODEL
AND IS THE BASIC STRUCTURE USED IN GRAPH THEORY.
SO THIS IS A DIAGRAM OF THE NEIGHBORHOOD
THE OFFICER MUST PATROL.
WE COULD USE THIS GRAPH TO REPRESENT THIS MODEL.
NOTICE HOW EACH INTERSECTION WOULD BE A DOT,
WHICH WE CALL A VERTEX,
AND EACH STREET WOULD BE AN EDGE IN THE GRAPH.
NOTICE HOW HERE WE HAVE SIX VERTICES AND EIGHT EDGES.
SO, AGAIN, A VERTEX OR NOTE IS A DOT ON THE GRAPH
WHERE EDGES MEET.
A VERTEX COULD REPRESENT AN INTERSECTION OF STREETS,
A LAND MASS, OR A GENERAL LOCATION LIKE WORK OR SCHOOL.
NOTE THAT VERTICES ONLY OCCUR WHERE A DOT IS EXPLICITLY PLACED
NOT WHEREVER TWO EDGES CROSS.
LOOKING AT THIS GRAPH HERE,
NOTICE HOW WE HAVE TWO EDGES THAT CROSS
BUT BECAUSE THERE'S NO DOT THERE'S NO VERTEX HERE.
AS AN EXAMPLE, IMAGINE A FREEWAY OVERPASS.
THE FREEWAY AND THE SIDE STREETS CROSS
BUT IT IS NOT POSSIBLE TO CHANGE FROM THE SIDE STREET
TO THE FREEWAY AT THAT POINT,
SO THERE'S NO INTERSECTION AND NO VERTEX WOULD BE PRESENT.
NORMALLY WE USE CAPITAL LETTERS FOR THE VERTICES AS WE SEE HERE.
EDGES CONNECT PAIRS OF VERTICES.
AN EDGE CAN REPRESENT A PHYSICAL CONNECTION
BETWEEN LOCATIONS LIKE A STREET
OR SIMPLY A ROUTE CONNECTING THE TWO LOCATIONS
LIKE AN AIRLINE FLIGHT.
EDGES ARE NORMALLY LABELED WITH LOWER CASE LETTERS
AS WE SEE HERE IN BLUE.
SO, AGAIN, WE USE CAPITAL LETTERS FOR THE VERTICES
AND LOWER CASE LETTERS FOR THE EDGES NORMALLY.
AND DEPENDING ON THE PROBLEM BEING SOLVED,
SOMETIMES WEIGHTS ARE ASSIGNED TO THE EDGES.
THE WEIGHTS COULD REPRESENT THE DISTANCE BETWEEN TWO LOCATIONS,
THE TRAVEL TIME, OR THE TRAVEL COST,
OR SEVERAL OTHER POSSIBILITIES.
IT IS IMPORTANT TO NOTE
THAT THE DISTANCE BETWEEN THE VERTICES IN A GRAPH
DOES NOT NECESSARILY CORRESPOND TO THE WEIGHT OF AN EDGE.
SO LOOKING AT OUR GRAPH HERE NOTICE HOW EDGE AF AND EDGE CD
ARE THE SAME LENGTH
BUT THEIR WEIGHTS ARE DIFFERENT.
SO GRAPHS DO NOT HAVE TO BE DRAWN TO SCALE.
SO IT'S IMPORTANT THAT WE PAY ATTENTION TO THE WEIGHTS
OF THE EDGES WHEN THEY'RE GIVEN.
A LOOP IS A SPECIAL TYPE OF EDGE
THAT CONNECTS A VERTEX TO ITSELF.
SO LOOKING AT THIS GRAPH HERE,
THIS WOULD BE A LOOP FROM THIS VERTEX.
NOW, THE DEGREE OR VALENCE OF A VERTEX
IS THE NUMBER OF EDGES MEETING AT THAT VERTEX.
IT IS POSSIBLE FOR A VERTEX TO HAVE A DEGREE OF ZERO OR LARGER.
SO HERE ARE SEVERAL EXAMPLES.
HERE'S A VERTEX WITH DEGREE 0, DEGREE 1, DEGREE 2, DEGREE 3,
AND DEGREE 4.
A PATH IS A SEQUENCE OF VERTICES USING EDGES.
USUALLY WE'RE INTERESTED IN A PATH BETWEEN TWO VERTICES.
FOR EXAMPLE, A PATH FROM VERTEX "A" TO VERTEX E.
SO ONE POSSIBLE PATH FROM VERTEX "A" TO VERTEX E
MIGHT LOOK SOMETHING LIKE THIS.
BUT, OF COURSE, THERE ARE SEVERAL OTHER PATHS
FROM VERTEX "A" TO VERTEX E.
FOR EXAMPLE, THIS WOULD BE ANOTHER PATH
FROM VERTEX "A" TO VERTEX E.
AND OF COURSE THERE ARE OTHERS.
A CIRCUIT IS A PATH THAT BEGINS AND ENDS AT THE SAME VERTEX.
SO STARTING AT VERTEX "A" WE CAN FORM SEVERAL CIRCUITS.
FOR EXAMPLE, WE COULD GO FROM VERTEX "A" TO VERTEX B TO C,
TO D, TO E, TO F, AND THEN BACK TO "A".
ANOTHER CIRCUIT MIGHT BE FROM "A" TO B, TO E, TO F,
BACK TO "A".
THIS IS ANOTHER CIRCUIT CONTAINING VERTEX "A".
A GRAPH IS CONNECTED
IF THERE'S A PATH FROM ANY VERTEX TO ANY OTHER VERTEX.
SO THIS FIRST GRAPH HERE IS CONNECTED
BECAUSE IF WE START AT ANY VERTEX,
LET'S SAY THIS VERTEX HERE,
AND THEN WE SELECT ANOTHER VERTEX,
LET'S SAY THIS VERTEX HERE,
THERE WILL ALWAYS BE A PATH FROM THIS VERTEX TO THIS VERTEX
OR ANY OTHER TWO VERTICES WE DECIDE TO SELECT.
ONE POSSIBLE PATH WILL JUST BE LIKE THIS.
BUT THE GRAPH ON THE BOTTOM HERE IS DISCONNECTED
BECAUSE THERE'S NO WAY TO GET FROM THE VERTICES ON THE LEFT
TO THE VERTICES ON THE RIGHT,
MEANING THERE'S NO PATH
FROM, LET'S SAY, THIS VERTEX TO THIS VERTEX
BECAUSE THIS GRAPH IS DISCONNECTED.
SO TO FINISH, LET'S GO BACK TO OUR OPENING EXAMPLE.
A POLICE OFFICER'S PATROLLING A NEIGHBORHOOD ON FOOT.
THE IDEAL PATROL ROUTE WOULD NEED TO COVER EACH BLOCK
THE LEAST AMOUNT OF BACKTRACKING OR NO BACKTRACKING
TO MINIMIZE THE AMOUNT OF WALKING.
THE ROUTE SHOULD ALSO BEGIN AND END AT THE SAME POINT.
LET'S SEE IF WE CAN FIND A ROUTE WITH NO BACKTRACKING.
WE FIRST NEED TO DECIDE
WHERE THE PATROL OFFICER WAS GOING TO--
WE WOULD FIRST NEED TO DETERMINE WHERE THE--
WE WOULD FIRST WANT TO DETERMINE
WHERE THE OFFICER'S GOING TO PARK THE CAR.
FOR EXAMPLE, LET'S SAY
THE PATROL OFFICER PARKED AT VERTEX "A".
LET'S SEE IF WE CAN RETURN TO "A"
BY USING EVERY EDGE ONCE AND ONLY ONCE.
WE COULD GO FROM "A" TO B,
THEN B TO E, THEN E TO B,
THEN FROM B TO C, C TO D, D TO E, E TO F,
AND FINALLY BACK TO "A".
NOTICE HOW WE STARTED AND ENDED AT "A,"
AND WE USED EACH EDGE ONCE,
THEREFORE WE DID MINIMIZE THE AMOUNT OF WALKING
THE POLICE OFFICER HAD TO DO.
IN FACT, THE POLICE OFFICER HAD NO BACKTRACKING.
THIS IS ACTUALLY A SPECIAL TYPE OF PATH
THAT WE'LL TALK ABOUT MORE LATER.
A PATH THAT USES EVERY EDGE IN A GRAPH WITH NO REPEATS
IS CALLED AN EULER PATH.
I HOPE YOU FOUND THIS INTRODUCTION HELPFUL.