DB posts & replies
See file
Discussion post: Graph theory can be applied to solve numerous real-world optimization problems. The recommended
readings for this module present applications of the Chinese Postman Problem (CPP) and the Traveling
Salesman Problem (TSP) to reduce carbon dioxide emissions. Lukman, Cerinšek, Virtič, and Horvat (2018)
developed an algorithm, based on a solution to the CPP, to optimize the route of heavy-duty vehicles
plowing and salting roads during the winter months, while Doppstadt, Koberstein, and Vigo (2016)
introduced a new optimization problem, extending the TSP, to describe the delivery of goods using a
hybrid electric vehicle.
Your task for this discussion is as follows:
1. Research other applications of graph theory to solve real-world problems and share your
favorite one with the class.
2. Discuss the importance of this application.
My post:
200 words and one scholarly source
Classmate one response: Hi class, Graph theory, as noted in this week’s reading, is not what I had expected. After seeing the graphs Lippman (2013) shared regarding the neighborhood lawn inspections, I see how utilizing graph theory simplifies an every-day task. I immediately thought about shopping, specifically Christmas shopping.
While many people now do their shopping online, which uses graph theory in a different way, think back to doing so in a mall or a series of stores. If the list of items to be purchased as gifts requires visits to a number of stores, the easiest and most efficient way to complete the trip is to visit stores as they are laid out in the mall, rather than running back and forth from one end to the other. For example, the shopping trip requires visits to stores A, B, and C, which are all located in the mall, plus stores X, Y, and Z, located just one block away. Consider the amount of time it would take to visit stores A and B, moving on to store Z, then back to the mall for store C, and leaving again to finish stores X and Y. It makes more sense to visit all of the stores in each location before leaving to stop at another. Planning or mapping out the trip ensures more time efficiency while maximizing productivity. Graph theory is used in a number of ways, sometimes even less obvious ways, like Christmas shopping.
Reference
Lippman, D. (2013). Math in society (2.4 ed.). CC BY-SA. Retrieved from
https://open.umn.edu/opentextbooks/textbooks/math-in-society
My Response to classmate one:
100 words
Classmate Two response: Hello Everyone! I had a lot of fun learning this module, I have a new appreciation for the GPS on my phone and had no idea Hamiltonian graph algorithms could be “greedy.”
1) When I think of a real-world graph theory, I think of a family tree. I’m sure most of you are familiar with a general family tree, where there is a starting person/couple related to you, and then edges extending from them onto more descendants (or vertices for graph terminology) until it reaches you. It is not a circuit, as it does not meet back at the starting vertex, but it is a Euler path because it uses edges in each family tree graph with no repeats (Lippman, 2013). Family trees can help solve real-world problems for genetic predispositions and can even help locate family members or find new ones.
The importance of using this application for a family tree is beneficial for many reasons. In my family we discussed health last weekend, where we talked about our genetic predispositions that other family members have had. This can guide entire families to lead healthier lives in relation to their genetic predispositions. Family trees are also a fun way to study your heritage and world history, it is interesting to know where you came from! Sometimes there can be exciting surprises when studying a family tree graph, such as a famous person or a new culture you never knew you were a part of.
Hope you all are having a great week!
Lippman, D. (2013). Math in society (2.4 ed.). pg, 128, CC BY-SA. Retrieved from
https://open.umn.edu/opentextbooks/textbo (Links to an external site.)
My response to classmate two:
100 words