Graph Theory: New Applications
http://www.maplesoft.com/applications/category.aspx?cid=141
en-us2017 Maplesoft, A Division of Waterloo Maple Inc.Maplesoft Document SystemThu, 30 Mar 2017 08:58:01 GMTThu, 30 Mar 2017 08:58:01 GMTNew applications in the Graph Theory categoryhttp://www.mapleprimes.com/images/mapleapps.gifGraph Theory: New Applications
http://www.maplesoft.com/applications/category.aspx?cid=141
Prim’s Minimum Spanning Tree: Step by Step
http://www.maplesoft.com/applications/view.aspx?SID=153972&ref=Feed
Prim's MST Algorithm is a well known solution to the Minimum Spanning Tree (MST) problem, which consists in finding a subset of the edges of a connected weighed graph, such that it satisfies two properties: it maintains connectivity, and the sum of the weights of the edges in the set is minimized. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153975">Kruskal’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153974">Ford-Bellman’s Shortest Path</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153973">Dijkstra’s Shortest Path</A>.<img src="/view.aspx?si=153972/prim.PNG" alt="Prim’s Minimum Spanning Tree: Step by Step" align="left"/>Prim's MST Algorithm is a well known solution to the Minimum Spanning Tree (MST) problem, which consists in finding a subset of the edges of a connected weighed graph, such that it satisfies two properties: it maintains connectivity, and the sum of the weights of the edges in the set is minimized. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153975">Kruskal’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153974">Ford-Bellman’s Shortest Path</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153973">Dijkstra’s Shortest Path</A>.153972Tue, 16 Feb 2016 05:00:00 ZDaniel MichelDaniel MichelDijkstra's Shortest Path Algorithm: Step by Step
http://www.maplesoft.com/applications/view.aspx?SID=153973&ref=Feed
Dijkstra's Shortest Path Algorithm is a well known solution to the Shortest Paths problem, which consists in finding the shortest path (in terms of arc weights) from an initial vertex r to each other vertex in a directed weighted graph with nonnegative weights. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153972">Prim’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153974">Ford-Bellman’s Shortest Path</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153975">Kruskal’s Minimum Spanning Tree</A>.<img src="/view.aspx?si=153973/dijkstra.PNG" alt="Dijkstra's Shortest Path Algorithm: Step by Step" align="left"/>Dijkstra's Shortest Path Algorithm is a well known solution to the Shortest Paths problem, which consists in finding the shortest path (in terms of arc weights) from an initial vertex r to each other vertex in a directed weighted graph with nonnegative weights. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153972">Prim’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153974">Ford-Bellman’s Shortest Path</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153975">Kruskal’s Minimum Spanning Tree</A>.153973Tue, 16 Feb 2016 05:00:00 ZFernando MichelFernando MichelFord-Bellman’s Shortest Path Algorithm: Step by Step
http://www.maplesoft.com/applications/view.aspx?SID=153974&ref=Feed
The Ford-Bellman Shortest Path Algorithm is a well known solution to the Shortest Paths problem, which consists in finding the shortest path (in terms of arc weights) from an initial vertex r to each other vertex in a directed weighted graph. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153975">Kruskal’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153972">Prim’s Minimum Spanning Tree</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153973">Dijkstra’s Shortest Path</A>.<img src="/view.aspx?si=153974/FordBellman.PNG" alt="Ford-Bellman’s Shortest Path Algorithm: Step by Step" align="left"/>The Ford-Bellman Shortest Path Algorithm is a well known solution to the Shortest Paths problem, which consists in finding the shortest path (in terms of arc weights) from an initial vertex r to each other vertex in a directed weighted graph. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153975">Kruskal’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153972">Prim’s Minimum Spanning Tree</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153973">Dijkstra’s Shortest Path</A>.153974Tue, 16 Feb 2016 05:00:00 ZFernando MichelFernando MichelKruskal's Minimum Spanning Tree: Step by Step
http://www.maplesoft.com/applications/view.aspx?SID=153975&ref=Feed
Kruskal's MST Algorithm is a well known solution to the Minimum Spanning Tree (MST) problem, which consists in finding a subset of the edges of a connected weighed graph, such that it satisfies two properties: it maintains connectivity, and the sum of the weights of the edges in the set is minimized. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153972">Prim’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153974">Ford-Bellman’s Shortest Path</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153973">Dijkstra’s Shortest Path</A>.<img src="/applications/images/app_image_blank_lg.jpg" alt="Kruskal's Minimum Spanning Tree: Step by Step" align="left"/>Kruskal's MST Algorithm is a well known solution to the Minimum Spanning Tree (MST) problem, which consists in finding a subset of the edges of a connected weighed graph, such that it satisfies two properties: it maintains connectivity, and the sum of the weights of the edges in the set is minimized. This implementation shows the step-by-step progress of the algorithm.
<BR><BR>
This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. See also applications for <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153972">Prim’s Minimum Spanning Tree</A>, <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153974">Ford-Bellman’s Shortest Path</A>, and <A HREF="http://www.maplesoft.com/applications/view.aspx?SID=153973">Dijkstra’s Shortest Path</A>.153975Tue, 16 Feb 2016 05:00:00 ZDaniel MichelDaniel MichelKnight's Tour
http://www.maplesoft.com/applications/view.aspx?SID=153842&ref=Feed
A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once.
This application presents the implementation of this task in Maple.<img src="/view.aspx?si=153842/26f19bd457ac566083dec1b86db8b91b.gif" alt="Knight's Tour" align="left"/>A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once.
This application presents the implementation of this task in Maple.153842Thu, 13 Aug 2015 04:00:00 ZYury ZavarovskyYury ZavarovskyOptimize the Flight Path of a Pan-US Delivery Drone
http://www.maplesoft.com/applications/view.aspx?SID=153536&ref=Feed
<p>You run a pan-US drone delivery service for a popular online retailer. You're given a list of zip codes across the US at which you need to drop off parcels, and want to optimize its journey so it travels the shortest distance.</p>
<p>This application extracts the latitude and longitude of those zip codes from an SQLlite database (the application includes the database, which cross-references US zip codes against their latitude, longitude, city and state). The application then performs a traveling salesman optimization and plots the shortest path on a map of the US.</p>
<p>This application uses background plot images, and SQLLite integration, two new features introduced in Maple 18.</p><img src="/view.aspx?si=153536/pan-us_drone.jpg" alt="Optimize the Flight Path of a Pan-US Delivery Drone" align="left"/><p>You run a pan-US drone delivery service for a popular online retailer. You're given a list of zip codes across the US at which you need to drop off parcels, and want to optimize its journey so it travels the shortest distance.</p>
<p>This application extracts the latitude and longitude of those zip codes from an SQLlite database (the application includes the database, which cross-references US zip codes against their latitude, longitude, city and state). The application then performs a traveling salesman optimization and plots the shortest path on a map of the US.</p>
<p>This application uses background plot images, and SQLLite integration, two new features introduced in Maple 18.</p>153536Mon, 31 Mar 2014 04:00:00 ZSamir KhanSamir KhanInternet Page Ranking Algorithms
http://www.maplesoft.com/applications/view.aspx?SID=153532&ref=Feed
In this guest article in the Tips and Techniques series, Dr. Michael Monagan explains how internet pages are ranked.<img src="/view.aspx?si=153532/thumb.jpg" alt="Internet Page Ranking Algorithms" align="left"/>In this guest article in the Tips and Techniques series, Dr. Michael Monagan explains how internet pages are ranked.153532Thu, 20 Mar 2014 04:00:00 ZProf. Michael MonaganProf. Michael MonaganClassroom Tips and Techniques: Bivariate Limits - Then and Now
http://www.maplesoft.com/applications/view.aspx?SID=145979&ref=Feed
An introductory overview of the functionalities in Maple's GraphTheory package.<img src="/view.aspx?si=145979/thumb.jpg" alt="Classroom Tips and Techniques: Bivariate Limits - Then and Now" align="left"/>An introductory overview of the functionalities in Maple's GraphTheory package.145979Wed, 17 Apr 2013 04:00:00 ZDr. Robert LopezDr. Robert LopezSimulating the Spread of an Infection
http://www.maplesoft.com/applications/view.aspx?SID=144175&ref=Feed
<p>In the problem below I take advantage of Maple's Graph Theory package to simulate how an infection might spread throughout a small community of 15 individuals.</p>
<p>This is a computer simulation project rather than a biology project! For example, the infection may not be a biological infection at all. The 15 vertices could represent 15 different computers, and the "infection" that spreads could be interpreted as a computer virus rather than a biological virus.</p><img src="/view.aspx?si=144175/siminfection_thumb.png" alt="Simulating the Spread of an Infection" align="left"/><p>In the problem below I take advantage of Maple's Graph Theory package to simulate how an infection might spread throughout a small community of 15 individuals.</p>
<p>This is a computer simulation project rather than a biology project! For example, the infection may not be a biological infection at all. The 15 vertices could represent 15 different computers, and the "infection" that spreads could be interpreted as a computer virus rather than a biological virus.</p>144175Mon, 04 Mar 2013 05:00:00 ZDouglas LewitDouglas LewitClassroom Tips and Techniques: Introduction to Maple's GraphTheory Package
http://www.maplesoft.com/applications/view.aspx?SID=142357&ref=Feed
An introductory overview of the functionality in Maple's GraphTheory package.<img src="/view.aspx?si=142357/thumb.jpg" alt="Classroom Tips and Techniques: Introduction to Maple's GraphTheory Package" align="left"/>An introductory overview of the functionality in Maple's GraphTheory package.142357Thu, 17 Jan 2013 05:00:00 ZProf. Michael MonaganProf. Michael MonaganGraph Theory Editor
http://www.maplesoft.com/applications/view.aspx?SID=141905&ref=Feed
<p>A component for editing Maple Graphs, along with tools for visualization and for import/export from GraphML.</p><img src="/view.aspx?si=141905/GraphEditor.jpg" alt="Graph Theory Editor" align="left"/><p>A component for editing Maple Graphs, along with tools for visualization and for import/export from GraphML.</p>141905Sat, 29 Dec 2012 05:00:00 ZJeff KnisleyJeff KnisleyBipartite Degree Sequences
http://www.maplesoft.com/applications/view.aspx?SID=135974&ref=Feed
<p>Given the degree sequence of one vertex set of a bipartite graph, this application allows the user to obtain information about the degree sequence of the other vertex set. Tools for generating all of the possible degree sequences of the unknown set are included. Without generating these degree sequences, we may also place bounds on any given position in the unknown degree sequence; procedures for bounding any given position in the unknown degree sequence, including the median, are given.</p><img src="/view.aspx?si=135974/135974_thumb.jpg" alt="Bipartite Degree Sequences" align="left"/><p>Given the degree sequence of one vertex set of a bipartite graph, this application allows the user to obtain information about the degree sequence of the other vertex set. Tools for generating all of the possible degree sequences of the unknown set are included. Without generating these degree sequences, we may also place bounds on any given position in the unknown degree sequence; procedures for bounding any given position in the unknown degree sequence, including the median, are given.</p>135974Fri, 20 Jul 2012 04:00:00 ZSamuel PineSamuel PineHollywood Math
http://www.maplesoft.com/applications/view.aspx?SID=6611&ref=Feed
Over its storied and intriguing history, Hollywood has entertained us with many mathematical moments in film. John Nash in “A Beautiful Mind,” the brilliant janitor in “Good Will Hunting,” the number theory genius in “Pi,” and even Abbott and Costello are just a few of the Hollywood “mathematicians” that come to mind. This document highlights just a few examples of mathematics in film, and how Maple can work with them.<img src="/view.aspx?si=6611/thumb.jpg" alt="Hollywood Math" align="left"/>Over its storied and intriguing history, Hollywood has entertained us with many mathematical moments in film. John Nash in “A Beautiful Mind,” the brilliant janitor in “Good Will Hunting,” the number theory genius in “Pi,” and even Abbott and Costello are just a few of the Hollywood “mathematicians” that come to mind. This document highlights just a few examples of mathematics in film, and how Maple can work with them.6611Fri, 23 Sep 2011 04:00:00 ZMaplesoftMaplesoftThe Traveling Salesman’s US Roadtrip
http://www.maplesoft.com/applications/view.aspx?SID=89020&ref=Feed
<p class="MsoNormal">This application</p>
<ul>
<li>plots the location of user-specified US zip codes on a map by querying a database of longitudes and latitudes</li>
<li>calculates the optimal path, or Hamiltonian cycle, for the Traveling Salesman Problem with Maple graph theory functionality,</li>
<li>and draws an undirected graph highlighting the Hamiltonian cycle.</li>
</ul>
<p class="MsoNormal">You will need to install PostreSQL to query the zip code database provided with this application.</p><img src="/view.aspx?si=89020/0\map.png" alt="The Traveling Salesman’s US Roadtrip" align="left"/><p class="MsoNormal">This application</p>
<ul>
<li>plots the location of user-specified US zip codes on a map by querying a database of longitudes and latitudes</li>
<li>calculates the optimal path, or Hamiltonian cycle, for the Traveling Salesman Problem with Maple graph theory functionality,</li>
<li>and draws an undirected graph highlighting the Hamiltonian cycle.</li>
</ul>
<p class="MsoNormal">You will need to install PostreSQL to query the zip code database provided with this application.</p>89020Fri, 04 Jun 2010 04:00:00 ZMaplesoftMaplesoftClassroom Tips and Techniques: A Note on Parametric Plotting
http://www.maplesoft.com/applications/view.aspx?SID=87605&ref=Feed
<p>Under suitable conditions, the equations f(x, y, t) = g(x, y, t) and g(x, y, t) = 0 define the curve x = x(t), y = y(t) parametrically. If the algebra permits an explicit solution, the resulting curve can be drawn with Maple's basic parametric plotting functionality. However, when the algebra is recalcitrant, the equations must be solved numerically for a sequence of points, or converted to differential equations that are solved numerically. All three of these alternatives are explored in this month's article.</p><img src="/view.aspx?si=87605/thumb.jpg" alt="Classroom Tips and Techniques: A Note on Parametric Plotting" align="left"/><p>Under suitable conditions, the equations f(x, y, t) = g(x, y, t) and g(x, y, t) = 0 define the curve x = x(t), y = y(t) parametrically. If the algebra permits an explicit solution, the resulting curve can be drawn with Maple's basic parametric plotting functionality. However, when the algebra is recalcitrant, the equations must be solved numerically for a sequence of points, or converted to differential equations that are solved numerically. All three of these alternatives are explored in this month's article.</p>87605Wed, 05 May 2010 04:00:00 ZDr. Robert LopezDr. Robert LopezSecret Santa Selection
http://www.maplesoft.com/applications/view.aspx?SID=34985&ref=Feed
<p>Every year my extended family does a "secret santa" gift exchange. Each person draws another person at random and then gets a gift for them. At first, none of my siblings were married, and so the draw was completely random. Then, as people got married, we added the restriction that spouses should not draw each others names. This restriction meant that we moved from using slips of paper on a hat to using a simple computer program to choose names.</p><img src="/view.aspx?si=34985/thumb.jpg" alt="Secret Santa Selection" align="left"/><p>Every year my extended family does a "secret santa" gift exchange. Each person draws another person at random and then gets a gift for them. At first, none of my siblings were married, and so the draw was completely random. Then, as people got married, we added the restriction that spouses should not draw each others names. This restriction meant that we moved from using slips of paper on a hat to using a simple computer program to choose names.</p>34985Thu, 17 Dec 2009 05:00:00 ZMaplesoftMaplesoftClassroom Tips and Techniques: Plotting a Slice of a Vector Field
http://www.maplesoft.com/applications/view.aspx?SID=19202&ref=Feed
This month's article answers a user's question about plotting a "slice" of a vector field, and superimposing this graph on a density plot of the underlying scalar field. The "slice" of the vector field is a graph of the field arrows emanating from a coordinate plane.<img src="/view.aspx?si=19202/thumb.png" alt="Classroom Tips and Techniques: Plotting a Slice of a Vector Field" align="left"/>This month's article answers a user's question about plotting a "slice" of a vector field, and superimposing this graph on a density plot of the underlying scalar field. The "slice" of the vector field is a graph of the field arrows emanating from a coordinate plane.19202Fri, 06 Mar 2009 00:00:00 ZDr. Robert LopezDr. Robert LopezOptions with Foreign Exchange Adjustment
http://www.maplesoft.com/applications/view.aspx?SID=6874&ref=Feed
The document presents the methods used by market practitioners to adjust the financial instruments processes and options valuations when payoffs are converted into different currency. Foreign exchange adjustment in the financial options universe brings in additional stochastic factor that extends the traditional univariate space into bi-variate or even multi-variate setting. We show that key tool to handle this scenario is an appropriate change of probability measure. In this context we also discuss the essence of the Siegel Paradox and show the way to resolve it.<img src="/view.aspx?si=6874/Quanto Options_95.gif" alt="Options with Foreign Exchange Adjustment" align="left"/>The document presents the methods used by market practitioners to adjust the financial instruments processes and options valuations when payoffs are converted into different currency. Foreign exchange adjustment in the financial options universe brings in additional stochastic factor that extends the traditional univariate space into bi-variate or even multi-variate setting. We show that key tool to handle this scenario is an appropriate change of probability measure. In this context we also discuss the essence of the Siegel Paradox and show the way to resolve it.6874Mon, 10 Nov 2008 00:00:00 ZIgor HlivkaIgor HlivkaTraveling Salesman Problem
http://www.maplesoft.com/applications/view.aspx?SID=6873&ref=Feed
The Traveling Salesman Problem (TSP) is a fascinating optimization problem in which a salesman wishes to visit each of N cities exactly once and return to the city of departure, attempting to minimize the overall distance traveled. For the symmetric problem where distance (cost) from city A to city B is the same as from B to A, the number of possible paths to consider is given by (N-1)!/2. The exhaustive search for the shortest tour becomes very quickly impossible to conduct. Why? Because, assuming that your computer can evaluate the length of a billion tours per second, calculations would last 40 years in the case of twenty cities and would jump to 800 years if you added one city to the tour [1]. These numbers give meaning to the expression "combinatorial explosion". Consequently, we must settle for an approximate solutions, provided we can compute them efficiently. In this worksheet, we will compare two approximation algorithms, a simple-minded one (nearest neighbor) and one of the best (Lin-Kernighan 2-opt).<img src="/view.aspx?si=6873/TSgif.gif" alt="Traveling Salesman Problem" align="left"/>The Traveling Salesman Problem (TSP) is a fascinating optimization problem in which a salesman wishes to visit each of N cities exactly once and return to the city of departure, attempting to minimize the overall distance traveled. For the symmetric problem where distance (cost) from city A to city B is the same as from B to A, the number of possible paths to consider is given by (N-1)!/2. The exhaustive search for the shortest tour becomes very quickly impossible to conduct. Why? Because, assuming that your computer can evaluate the length of a billion tours per second, calculations would last 40 years in the case of twenty cities and would jump to 800 years if you added one city to the tour [1]. These numbers give meaning to the expression "combinatorial explosion". Consequently, we must settle for an approximate solutions, provided we can compute them efficiently. In this worksheet, we will compare two approximation algorithms, a simple-minded one (nearest neighbor) and one of the best (Lin-Kernighan 2-opt).6873Mon, 10 Nov 2008 00:00:00 ZBruno GuerrieriBruno GuerrieriClassroom Tips and Techniques: Context-Menu Plotting
http://www.maplesoft.com/applications/view.aspx?SID=6816&ref=Feed
The Context Menu for a Maple mathematical expression in a single variable provides two distinct options for plotting. In this month's article, we examine these options and provide a rationale for guiding the choice between them.<img src="/view.aspx?si=6816/1.jpg" alt="Classroom Tips and Techniques: Context-Menu Plotting" align="left"/>The Context Menu for a Maple mathematical expression in a single variable provides two distinct options for plotting. In this month's article, we examine these options and provide a rationale for guiding the choice between them.6816Tue, 28 Oct 2008 00:00:00 ZDr. Robert LopezDr. Robert Lopez