{"id":1196,"date":"2017-01-24T01:52:15","date_gmt":"2017-01-24T01:52:15","guid":{"rendered":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/?post_type=chapter&p=1196"},"modified":"2021-02-05T23:49:32","modified_gmt":"2021-02-05T23:49:32","slug":"putting-it-together-graph-theory","status":"web-only","type":"chapter","link":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/chapter\/putting-it-together-graph-theory\/","title":{"raw":"Putting It Together: Graph Theory","rendered":"Putting It Together: Graph Theory"},"content":{"raw":"At the start of this module, you were thinking about finding the fastest route from one client to another. \u00a0Thankfully, now you know how to use graph theory to figure it out. \u00a0Take another look at the diagram. \u00a0Now you know it is a graph in which each vertex represents a client and each edge represents a path between clients. \u00a0The numbers, or weights, indicate the length of time (minutes) required to travel from one vertex to another.\r\n\r\n\"Graph<\/a>\r\n\r\nOne vertex, A, is degree 1. Some vertices are degree 2, such as C and E, and H. \u00a0Others are degree 3, such as D and G. Still others are degree 4, such as B, F, and I. \u00a0What does that mean for you? \u00a0It means that there are multiple paths leading from each client and several different routes you can take traveling from one to the other.\r\n\r\nYou were faced with the problem of having to get from Client G to Client C using the fastest route. \u00a0Start by marking the ending vertex with a time of 0. \u00a0Then find all vertices leading to the current vertex. \u00a0Calculate their distances to the end.\r\n\r\n\"Graph<\/a>\r\n\r\nMark C as visited, and mark the vertex with the smallest recorded time as current. \u00a0So B will be designated current. \u00a0Again find all vertices leading to the current vertex. \u00a0For each vertex leading to B, and not to a visited vertex, find the time from the end.\r\n\r\n\"Graph<\/a>\r\n\r\nMark B as visited, and mark the vertex with the smallest recorded time as current. \u00a0So D will be designated current. \u00a0Add CD to DE, 10 + 8 = 18.\r\n\r\n\"Graph<\/a>\r\n\r\nCompare the time at E with that at I. \u00a0The time at I is lower so mark E as visited, and mark I as current. \u00a0So C to G through I has a total of 32 minutes. \u00a0But the time at H is only 22 minutes. \u00a0Since it is lower, keep going. Mark I as visited and H as current. \u00a0The total time from C to G through H is 27 minutes. \u00a0This is the fastest route.\r\n\r\n\"Graph<\/a>\r\n\r\n \r\n\r\nSo it will take you 27 minutes to get back to Client C to pick up your sample. \u00a0It may have looked as if a different route, perhaps D, would have been faster but it turns out not to be the case. \u00a0Using the graph confirmed the best route.\r\n\r\nNow you have to get all the way to your next client at H. \u00a0You can tell by the work you have already done that the fast route back to H is from C to B to I to H. \u00a0And how long will that take? \u00a0It will take a speedy 22 minutes. \u00a0Drawing a graph may seem complex, but in the end it really helps you make definite calculations rather than estimating. \u00a0And that can mean the difference between closing the deal or missing the client altogether.\r\n\r\n ","rendered":"

At the start of this module, you were thinking about finding the fastest route from one client to another. \u00a0Thankfully, now you know how to use graph theory to figure it out. \u00a0Take another look at the diagram. \u00a0Now you know it is a graph in which each vertex represents a client and each edge represents a path between clients. \u00a0The numbers, or weights, indicate the length of time (minutes) required to travel from one vertex to another.<\/p>\n

\"Graph<\/a><\/p>\n

One vertex, A, is degree 1. Some vertices are degree 2, such as C and E, and H. \u00a0Others are degree 3, such as D and G. Still others are degree 4, such as B, F, and I. \u00a0What does that mean for you? \u00a0It means that there are multiple paths leading from each client and several different routes you can take traveling from one to the other.<\/p>\n

You were faced with the problem of having to get from Client G to Client C using the fastest route. \u00a0Start by marking the ending vertex with a time of 0. \u00a0Then find all vertices leading to the current vertex. \u00a0Calculate their distances to the end.<\/p>\n

\"Graph<\/a><\/p>\n

Mark C as visited, and mark the vertex with the smallest recorded time as current. \u00a0So B will be designated current. \u00a0Again find all vertices leading to the current vertex. \u00a0For each vertex leading to B, and not to a visited vertex, find the time from the end.<\/p>\n

\"Graph<\/a><\/p>\n

Mark B as visited, and mark the vertex with the smallest recorded time as current. \u00a0So D will be designated current. \u00a0Add CD to DE, 10 + 8 = 18.<\/p>\n

\"Graph<\/a><\/p>\n

Compare the time at E with that at I. \u00a0The time at I is lower so mark E as visited, and mark I as current. \u00a0So C to G through I has a total of 32 minutes. \u00a0But the time at H is only 22 minutes. \u00a0Since it is lower, keep going. Mark I as visited and H as current. \u00a0The total time from C to G through H is 27 minutes. \u00a0This is the fastest route.<\/p>\n

\"Graph<\/a><\/p>\n

 <\/p>\n

So it will take you 27 minutes to get back to Client C to pick up your sample. \u00a0It may have looked as if a different route, perhaps D, would have been faster but it turns out not to be the case. \u00a0Using the graph confirmed the best route.<\/p>\n

Now you have to get all the way to your next client at H. \u00a0You can tell by the work you have already done that the fast route back to H is from C to B to I to H. \u00a0And how long will that take? \u00a0It will take a speedy 22 minutes. \u00a0Drawing a graph may seem complex, but in the end it really helps you make definite calculations rather than estimating. \u00a0And that can mean the difference between closing the deal or missing the client altogether.<\/p>\n

 <\/p>\n","protected":false},"author":21,"menu_order":24,"template":"","meta":{"_candela_citation":"[]","CANDELA_OUTCOMES_GUID":"047c0561-dd6c-461a-8ab1-481920e0c38e","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-1196","chapter","type-chapter","status-web-only","hentry"],"part":1193,"_links":{"self":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/1196","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/wp\/v2\/users\/21"}],"version-history":[{"count":7,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/1196\/revisions"}],"predecessor-version":[{"id":2378,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/1196\/revisions\/2378"}],"part":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/parts\/1193"}],"metadata":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/1196\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/wp\/v2\/media?parent=1196"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapter-type?post=1196"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/wp\/v2\/contributor?post=1196"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/wp\/v2\/license?post=1196"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}