The STEM Methodology and Graph Theory: Some Practical Examples

Abstract

In this paper, we highlight that Graph Theory is certainly well suited to an applications approach. One of the basic problems that this theory solves is finding the shortest path between two points. For this purpose, we propose two real-world problems aimed at STEM undergraduate students to be solved by using shortest path algorithms from Graph Theory after previous modeling.

1. Introduction

The term STEM is the acronym for Science, Technology, Engineering, and Mathematics. The biggest advantage of STEM education is that it involves issues that affect students in their day-to-day lives, so focusing the lesson on real-world problems can motivate them. Furthermore, understanding the problem and learning the basic concepts can lead the students to innovate, which is a powerful skill for their future.

Graph Theory has proven to be a powerful tool for modeling real-world problems, experiencing a boom in the last few decades due to its high applicability. The mathematical structures of Graph Theory are widely applied in several research areas such as biology [1,2], engineering [3,4], chemistry [5], economics [6], social networks [7], image processing [8], and education [9], among others. This shows that graphs provide an interdisciplinary approach that builds connections between content and real-world context. In addition, given its intuitive graphical representation, basic concepts from Graph Theory could already be included in secondary school, since it is a relevant subject for providing the students awareness that studying mathematics is more than just applying methods. It also provides them with a set of tools to model problems, which we consider fundamental for the student due to its interdisciplinary applications. For these reasons, we believe that it is important to propose to the student problems whose modeling is not trivial.

Despite the proven utility of Graph Theory in real-world applications, this subject, which is usually present in university studies of mathematics, computer science, and data science, is still taught without paying enough attention to modeling. Although, as we commented before, examples of direct applications of Graph Theory algorithms are proposed in the literature, it is not easy to find academic problems in a real context whose resolution is not limited to applying an algorithm to a graph, but rather, it is necessary to modify and adapt it in order to solve the problem.

In relation to the methodology used in the teaching of graphs, educational innovations have been carried, out as can be found in the existing literature [10,11,12], although modeling does not appear frequently. In our opinion, this should be the main objective of teaching this subject. Thus, the methodology for which we advocate is based on starting the issues with the statement of a real context problem and, then, in view of the proposed issues, developing the theoretical basis necessary for their resolution. Once the necessary concepts, properties, and algorithms have been established, we proceed to the resolution of the initial problem. In this way, teaching becomes eminently practical, without losing rigor throughout its approach, moving away from passive, theoretical, and repetitive learning, allowing the students to develop critical thinking by choosing the information that allows them to achieve a solution.

As an example of what has been mentioned, in this paper, we present two problems aimed at students of mathematics, computer science, and data science. These problems would be interesting for teaching the topic of weighted graphs and the associated problem of shortest paths. The first proposed problem consists of an application of Dijkstra’s algorithm in an iterative process. In the second one, the student must make an effort to find an adequate modeling using negative weights, so the appropriate algorithm in this case will be the Bellman–Ford algorithm.

2. Preliminaries

In this section, we recall the concepts necessary to understand the two problems presented. The first ones are supposed to be known by the students. A nondirected graph $G=(V,E)$ is given by a nonempty set V whose elements are called vertices and a set E of unordered pairs of distinct vertices V, which are called edges. Two vertices joined by an edge are said to be adjacent. A directed graph $G=(V,E)$ is given by a set of vertices V and a set E of ordered pairs of vertices called arcs. If an arc or an edge connects the node u with the node v, we simply denote it by $(u,v)$. Their graphical representation based on points and lines (arrows) for nondirected (directed) graphs is known by the students. A graph $H=(V_H,E_H)$ is called a subgraph of $G=(V_G,E_G)$ if $V_H\subseteq V_G$ and $E_H\subseteq E_G$.

A path W from a vertex $v_0$ to a vertex $v_l$ in a graph $G=(V,E)$ is an alternate sequence of vertices and edges (respectively, vertices and arcs), say $v_0,e_1,v_1,e_2,v_2,\dots e_l,v_l$ where $e_i=(v_{i-1},v_i)\in E$, $1\le i\le l$. To simplify, we denote it as $v_0,v_1,v_2,\dots v_l$. A path $W=v_0,v_1,v_2,\dots ,v_l$ is said to be a cycle if $l\ge 2$, $v_0=v_l$, and the vertices $v_i$, $0<i<l$, are distinct from each other and $v_0$. A graph is connected if for every pair $v_i$ and $v_j$ of distinct vertices, there is a path from $v_i$ to $v_j$.

The following concepts are the objective of the present work and are motivated by the problems we propose. When each edge (respectively arc) $(u,v)$ has a value $w(u,v)$ associated, we say that the graph is weighted. The weight of a path W in a weighted graph is defined as the sum of all the weights associated with the edges contained in it, the length of W being the number of edges (arcs) that form it. The shortest path problem on a graph $G=(V,E,w)$ consists of finding the path with the least weight between each pair of vertices $u,v\in V$. The solution of this problem can be found by using different well-known algorithms such as Dijkstra’s algorithm, when all the weights are positives, the Bellman–Ford algorithm, when the weights are not necessarily positive, but there are no cycles whose weight is negative, or the Floyd–Warshall algorithm when looking for the shortest path between any pair of vertices in the graph. For further information about them, we refer the reader to [13,14,15].

3. Real-World Problems via Shortest Path Algorithms

In this section, we propose a couple of problems that serve as an introduction to weighted graphs.

In Section (a) of Problem 1, we present a typical shortest path problem. Once the objective is exposed, we introduce the concept of the weighted graph, and we make the students observe that we are looking for the shortest path between two vertices. This serves to introduce Dijkstra’s algorithm.

The following sections of the problem lead students to delve deeper into the concept of the shortest path and its scope, forcing them to subdivide the problem into smaller ones, so that with the studied tools, they can obtain a solution.

Problem 1.

A freelance photographer visiting Africa by jeep wants to move from city A to city S. His jeep has a capacity of 40 L of fuel. In Figure 1, the gasoil consumption in liters for direct connections between all the cities is depicted.

(a)

Can you find a route from A to S with the lowest gasoil consumption?

The photographer’s jeep has broken down, and he cannot fix it until one week later. He still wants to go from A to S. A friend leaves him an old car with a fuel capacity of only 20 L, although it has the same consumption per 100 km as his own. Since the capacity of the new car is lower, he wants to make sure that he will find enough gas stations along the way. Otherwise, he will have to bring a gasoil can. Since he would prefer not to carry it due to the space it occupies and how much it weighs, as well as the potential risk involved, he studies the cities of the area, the roads that connect them, and the estimated amount of fuel to cover them, as well as the locations of the gas stations. He confirms that there are open gas stations in cities $A,E,F,I,K$, and M. Considering the small tank of his vehicle (20 L), answer the following question:

(b)

Is there a route that allows the photographer to go from A to S without having to carry a gasoil can? If there is more than one, which route uses the least amount of fuel?

Proof. 

After the students have modeled the context of the problem as a graph $G=(V,E)$, where V = {cities} and $E=\left\{\right(x,y)$ with $x,y\in V$ such that there is a direct road between x and $y\}$, we ask them what will be the natural way to represent the gasoil consumption on each of the roads, which will allow us to introduce the concept of a weighted graph. Therefore, we assume that the graph is nondirected and the weight of each edge corresponds to the gasoil consumption when traveling between two cities, as can be seen in Figure 2:

(a)

The problem consists of finding the path from A to S for which we need the least gasoil consumption. Since the weights are all positive, this example serve to introduce Dijkstra’s algorithm for obtaining the path of minimum weight from A to S, which corresponds to route $AJKS$ with a gasoil consumption of 29 L. Since the capacity of the jeep is 40 L, the photographer will arrive at city S without any problem;

(b)

In this new situation, we consider again the weighted graph from Figure 2. From the results obtained in Section (a), there is no possibility to travel from A to S directly without refueling due to the new car’s capacity since the shortest route from A to S needs 29 L of gasoil.

The problem can be analyzed as follows. We must first look for the shortest paths to all gas stations from A and analyze which of these paths are feasible. Then, in the second stage, we consider whether it is possible to reach the gas stations not reached in the previous stage by considering another path different from the shortest one. Finally, in the third stage, we look for the shortest paths from the reachable gas stations to S. Below, we explain in detail the development of these steps, pointing out the hints, clues, or observations that we use to guide the students, helping them to solve the problem.

First stage:

We first apply Dijkstra’s algorithm to graph G to determine the path with the lowest weight from A to the towns with a gas station, that is $E,F,I,K$, and M. The result of applying it is:

–

$P_{AE}=ACE$ with weight $w\left(P_{AE}\right)=16$;

–

$P_{AF}=ACEGF$ with weight $w\left(P_{AF}\right)=34$;

–

$P_{AI}=ABI$ with weight $w\left(P_{AI}\right)=24$;

–

$P_{AK}=AJK$ with weight $w\left(P_{AK}\right)=26$;

–

$P_{AM}=ACEM$ with weight $w\left(P_{AM}\right)=38$.

Observe that the photographer can go to E without any problem since the gasoil consumption for the route $ACE$ is 16 L. At this moment, we ask the students if it is sufficient to check if the gasoil consumption of the obtained paths is greater than 20 to discard them. We have to try to make them realize they have to analyze among all the routes those that contain an intermediate gas station.

Indeed, the routes $ACEGF$ and $ACEM$ contain intermediate gas stations. Therefore, we must study the two paths in which each gas station divides the route. In the case of $ACEGF$, the path $ACE$ has a weight of 16 L and $EGF$ has a weight of 18 L. Consequently, that route will be possible since the photographer can refuel in city E despite $w(P_{AF}=34)$. Conversely, the route $ACEM$ will not be possible since $w\left(ACE\right)=16$, but $w\left(EM\right)=22>20.$

To sum up, we can reach E and F considering the paths $ACE$ and $ACEGF$ with weights $w\left(ACE\right)=16$ and $w\left(ACEGF\right)=34$.

Second stage:

Before further solving the problem, we point out to the students that the shortest path from A to S does not need to be the concatenation of the shortest one from A to a gas station together with the shortest path from it to S.

The shortest paths from A to I and K provided by Dijkstra’s algorithm do not contain any intermediate gas station, and they have a weight whose value is greater than 20. Consequently, I and K should be analyzed separately together with M since it could happen that by means of a longer route that included one of the gas stations E or F, it could be possible to reach them from A. We analyze them:

–

Gas station I: Since the graph is nondirected, we encourage the students, instead of applying Dijkstra’s algorithm to the different gas stations from which I can be reached, to apply it to I to obtain the paths:

*

$P_{IF}=IEGF$ with weight $w\left(P_{IF}\right)=28$;

*

$P_{IE}=IE$ with weight $w\left(P_{IE}\right)=10$.

We note that the paths we have to analyze are $EI$ and $FGEI$. In the last one, to get to I, we pass through the intermediate gas station E. Therefore, to determine whether it is valid or not, we must analyze if the corresponding subroutes have a weight smaller than 20. Indeed, since $w\left(FGEI\right)=w\left(FGE\right)+w\left(EI\right)=18+10$ and both paths $FGE$ and $EI$ weigh less than 20, routes $FGEI$ and $EI$ will be possible. Since $EI$ is shorter than $FGEI$, the shortest path that allows us to reach I from a gas station is $P_{EI}=EI$ with $w\left(P_{EI}\right)=10$.

Then, the shortest route from A to I will be $ACEI$ with a consumption of 26 L;

–

Gas station M: Following the same analysis as before, we look for the shortest paths from M to E and F. Applying Dijkstra’s algorithm, we obtain the following routes:

*

$P_{ME}=ME$ with weight $w\left(P_{ME}\right)=22$;

*

$P_{MF}=MEGF$ with weight $w\left(P_{MF}\right)=40$.

Since the gasoil consumption along $ME$ is greater than 20 L, this route will not be valid. On the other hand, $w\left(MEGF\right)=w\left(ME\right)+w\left(EGF\right)=22+18$, and then, $MEGF$ cannot be considered. Consequently, the photographer will not be able to get from E or F to M;

–

Gas station K: We observe that all the routes from E and F to K pass through A or S, so it will not be possible to move from them to K.

At this point, following the same reasoning stated at the beginning of Stage 2, we ask the students if there are alternative routes to reach M or K from I.

The shortest route from I to M that does not pass through A or S is given by $IEM$ with $w\left(IEM\right)=w\left(IE\right)+w\left(EM\right)=10+22$. On the other hand, all routes from I to K pass through A or S, so we discard all of them.

Combining all the previous results, the possible routes from A to a gas station are $ACE$, $ACEI$, and $ACEGF$ with weights $w\left(ACE\right)=16,w\left(ACEI\right)=26$, and $w\left(ACEGF\right)=34$, respectively.

Third stage:

Finally, once we know the reachable gas stations, we ask the students how to obtain the solution of the problem.

We must therefore find the shortest routes from the towns $E,I$, and F to S. Therefore, since graph G is nondirected we can simply apply Dijkstra’s algorithm to S and obtain the shortest path to them:

–

$P_{SE}=SHE$ with weight $w\left(P_{SE}\right)=16$;

–

$P_{SF}=SGF$ with weight $w\left(P_{SF}\right)=13$;

–

$P_{SI}=SLI$ with weight $w\left(P_{SI}\right)=8$.

Thus, all possible routes from A to S without the need to carry a gasoil can are $ACEHS$, $ACEILS$, and $ACEGFGS$ with weights $w\left(ACEHS\right)=w\left(ACE\right)+w\left(EHS\right)=32$, $w\left(ACEILS\right)=w\left(ACEI\right)+w\left(ILS\right)=34$, and $w\left(ACEGFGS\right)=w\left(ACEGF\right)+w\left(FGS\right)=47.$

We will clearly recommend the photographer take route $ACEHS$ because it is the least costly or, in other words, the one for which he will have to travel the least kilometers without having to carry the gasoil can.

□

After solving the previous problem, the students are expected to be able to tackle the new problem posed below. When weighting the graph to model the situation, they should include all the restrictions about the costs/benefits that appear in the statement.

Thus, the students should realize that they should represent the costs with positive weights and, in contrast, the benefits with negative ones. As a particularity, they should note that the weight of the arc $(i,j)$ does not have to coincide with that of the arc $(j,i)$, which will lead to modeling the situation using a directed graph. The graph defined will have a matrix of weights with negative values to which Dijkstra’s algorithm cannot be applied. In this way, the introduction of the Bellman–Ford algorithm is motivated.

Problem 2.

The owner of a van is going to make a trip from city A to J. Studying the map, she realizes she can make the journey by stopping to sleep in towns where she knows a friend, thereby saving the cost of accommodation. In Figure 3, the kilometers between each pair of towns are shown, and in Figure 4, the cost of accommodation in each city is collected. In addition, she has the possibility of transporting some packages of a medium and small size in the surroundings of some of the cities. The benefit that this would represent is reflected in Figure 5. She wants to travel a maximum number of kilometers on the day of departure since she wants to arrive early the next day, but due to the time at which she leaves and the obligatory rest stops, she calculates that she will be able to drive at most 525 km. On the other hand, she does not want to spend the night in $B,C$, or F since there are local races in these cities the next day, and they will be shut down.

If the cost of fuel is approximately EUR 8 per 100 km, determine the path she should follow and if she should accept any of the job offers to make the cost of the trip between A and J as economical as possible.

Proof. 

This problem can be analyzed in two stages. In the first one, we analyze all the possible cities she can reach the first day, given the maximum number of kilometers and the restrictions on the statement of the problem. Then, on the possible paths, we compute the minimal cost for each destination taking into account the benefits of the jobs. In the second stage, we consider a new graph for the second day, where we reflect the paths obtained in the previous step and take into consideration the accommodation cost and the job benefits without a limitation on the number of kilometers this day.

Specifically, we start the modeling of the problem by considering a graph $G=(V,E)$, where V = {cities} and $E=\left\{\right(x,y)$, $x,y\in V$ such that there is a direct road between x and $y\}$. From the context of the problem, and it being most common that roads are two-way, it seems that we should assume that G is nondirected. It is necessary to make the student observe that we must reflect through the weightings the costs of accommodation and the earnings from transporting packages, so the weight assigned to the pair $(i,j)$ will not always be the same as the one assigned to the pair $(j,i)$. Therefore, we must consider that G is directed. We assign G different weights as we develop the problem.

First stage:

We encourage the students to analyze the statement in order to conclude that the first thing to determine is where the owner of the van should spend the night, taking into account that she wants to travel at most 525 km before stopping to sleep.

Therefore, we assume as an initial weighting the values provided in Figure 3, relative to the kilometers between cities, where the position $(i,j)$ denotes the distance in kilometers between i and j (see Figure 6). First of all, to achieve the goal of the first day in relation to the kilometers to be covered, we have to determine all routes with initial vertex A whose weight is less than 525. We discard getting from A to $G,H$, and J since, by Dijkstra’s algorithm, the shortest paths to these vertices have a weight greater than 525.

We ask the students if it is sufficient to calculate the shortest paths from A using Dijkstra’s algorithm, taking into account that our objective is to find the most economical route, which will be influenced by the transport benefits. As they easily see, the answer is negative, and then, the solution is obtained by comparing all possible routes departing from A and whose weight meets the desired conditions.

Thus, the owner of the van will be able to choose between the following paths: $AB$ with 150 km, $ABC$ with 250 km, $AF$ with 300 km, $ABE$ of 520 km, $ABCD$ of 500 km, $ABCE$ of 525 km, $ACD$ of 510 km, and $AFD$ of 480 km. We discard $AB$, $AF$, and $ABC$ since she does not want to spend the night in these cities due to the local races.

In addition, in order to choose the most suitable path among the mentioned ones, we must consider whether the cost in EUR of any of the aforementioned routes can be lowered thanks to the job offers related to the transport received.

To do this, first of all, we ask the students if the previous weights reflect these benefits and costs since they should realize we have to change the costs in kilometers between two cities to costs in EUR (see Figure 6). They should transfer them into a cost matrix, which we call $W^e=(w_{ij}^e)$, only taking into account the fuel price per 100 km given in the statement.

$$W^e=\left[\begin{array}{ccccccccc}0& 12& 20.8& \infty & \infty & 24& \infty & \infty & \infty \\ 12& 0& 8& \infty & 29.6& \infty & \infty & \infty & \infty \\ 20.8& 8& 0& 20& 22& \infty & 24& \infty & \infty \\ \infty & \infty & 20& 0& \infty & 14.4& \infty & 16& \infty \\ \infty & 29.6& 22& \infty & 0& \infty & 16.8& 12& 24\\ 24& \infty & \infty & 14.4& \infty & 0& \infty & \infty & \infty \\ \infty & \infty & 24& \infty & 16.8& \infty & 0& \infty & 28\\ \infty & \infty & \infty & 16& 12& \infty & \infty & 0& 26\\ \infty & \infty & \infty & \infty & 24& \infty & 28& 26& 0\end{array}\right]$$

In order to determine the most economical routes from A to D and from A to E among those mentioned above, we must take into account that, when accepting transport offers, going from B to E or from C to E brings her benefits. At this point, we ask the students how these benefits should be added. We show them that these benefits should be reflected as negative weights, as opposed to costs, represented by positive weights. We therefore consider a second cost matrix $W^{DE}=\left({w_{ij}}^{DE}\right)$ whose values are equal to those of the matrix $W^e={\left(w_{ij}\right)}^e$ except for the entries ${w_{BE}}^{DE}={w_{BE}}^e-15$ and ${w_{CE}}^{DE}={w_{CE}}^e-20$. Moreover, possible accommodation expenses do not increase this cost since she will only stop to sleep in D or E.

Considering the new weighting that includes the gains, we compare the weights of the paths: $ABE$ and $ABCE$, on the one hand, and $ABCD,$ $ACD$ and $AFD$, on the other. We obtain that the least costly path from A to D is $AFD$ with weight $38.4$ and from A to E is $ABCE$ with weight 22.

We now ask the students if the most economical path from A to J can be directly obtained by considering the one with the least weight of the previous ones, that is the path $ABCE$, and then calculating the shortest from E up to J. We reason this conclusion is not necessarily true since we do not know the weight of the paths from D and E up to J.

Second stage:

Next, to analyze the route on the second day, we generate a new graph $G^{\prime }$, whose graphical representation can be seen in Figure 7, where the vertices $B,C,F$ are eliminated from G and the following changes are made as follows:

• $ABCD$, $ACD$ and $AFD$ are replaced by a unique edge $AD$ weighted with $38.4$;
• $ABE$ and $ABCE$ are replaced by a unique edge $AE$ weighted with 22.

The student may not consider the option of eliminating the vertices $B,C,F$ and reconsidering this new graph $G^{\prime }$, and thus, they will need some previous help from the professor, who will emphasize the advantages of reducing the graph.

In relation to the weighting of $G^{\prime }$, we must make the students keep in mind the cost in EUR per kilometer, per accommodation, and the discount for package transport, as explained below.

To begin, we consider that each edge of this new graph is assigned the weight that we established in matrix $W^e$ except for $AD$ and $AE$, whose values will be $38.4$ and 22, respectively. Note that the new graph $G^{\prime }$ has three fewer vertices than the original, so the matrix of weights of $G^{\prime }$ will be a $6\times 6$ matrix. In Figure 7, we can see the graphical representation of this new graph $G^{\prime }$ with the assigned weights.

It is important that the students think about how to include the weight of the accommodation and the benefits obtained by accepting job offers in the graph. In relation to the cost of the accommodation, if it has a value of $c_i$ in the vertex i, this weight is added to that assigned to the edge with initial vertex i in the previous paragraph. This means this value will affect us if we sleep in i and then move towards j, but not if leaving j, we reach i. Consequently, we consider our graph $G^{\prime }$ as a directed one.

Regarding the benefits, they should make a similar analysis of that of accommodation. The benefit is obtained if we transport the package from i to j, but not vice versa. Therefore, we have to weight the two arcs differently. Thus, if the benefit of transporting the package from i to j is $b_{ij}$, we subtract it from the value assigned to the arc $(i,j)$ until this moment. In case we have a double arc with the same value, it is represented by a single arc with two arrow ends.

Considering the above constraints, we weight the graph $G^{\prime }$ with the matrix $W^{\prime }$ given by:

$$W^{\text{'}}=\left[\begin{array}{cccccc}0& 38.4& 22& \infty & \infty & \infty \\ 38.4& 0& \infty & \infty & -1& \infty \\ 22& \infty & 0& 51.8& 62& 36\\ \infty & \infty & 16.8& 0& \infty & 68\\ \infty & 14& 12& \infty & 0& 26\\ \infty & \infty & 36& 28& 26& 0\end{array}\right]$$

The graphical representation of the graph $G^{\prime }$ with the new weighting can be seen in Figure 7.

Now, we can compute the shortest path from A to J. As there are negative values, we emphasize that Dijkstra’s algorithm cannot be applied, and this serves to introduce the Bellman–Ford algorithm. Applying it, we obtain the shortest path as $AFDHJ$; the owner of the van will sleep at her friend’s house in D and will transport a package from D to H for which she will receive EUR 17, the total cost of the trip being EUR $63.4$. □

Observe that in the previous problem, we can consider new and different constraints. We could now ask the students what would happen if there were a restriction on the maximum kilometers per day assuming that there is no need to arrive at J the next day. Another option could be to ask them what would happen in case there are no local races in $B,C$, or F.

4. Conclusions

We consider Graph Theory to be a part of mathematics that allows the student to discover the close relationship between mathematics and many aspects of the real world, in particular our everyday environment. It is worth noting that its intuitive graphic representation allows its introduction at levels where knowledge in mathematics is limited.

However, if we want this theory to be useful, whether in STEM education or in any educational context where applicability or multidisciplinarity is sought, we must change the classical methodology. In our opinion, it is much more fruitful to start by posing problems, close to and easily understandable by the student, that allow, when trying to find their solution, introducing the different concepts of Graph Theory.

Given the multiple applications of Graph Theory in STEM disciplines, an applied approach to its teaching is necessary. In computer science, graphs are useful in network security, the optimization of database searches, the representation of communication networks, and improving the efficiency of programming, among others. In biology, they are used to study the monitoring of contagious diseases, the evolution of species, metabolic networks, etc. In physics and chemistry, their applicability stands out when describing the connections in molecular structures. In engineering, we can, for example, solve logistic and distribution problems based on Eulerian and Hamiltonian graphs and the theory of networks and flows, being also useful in the design of electrical circuits.

In the present work, we proposed two problems that may be useful for the introduction of weighted graphs and the algorithms to solve the shortest path problem, including weighted graphs with negative weights, which are very rare in the literature. Both problems incorporate trivial questions, but also others that are not, which constitutes a challenge for the student and allows us to meet the objective of developing reasoning skills.