Graph Theory: New Applications
http://www.maplesoft.com/applications/category.aspx?cid=205
en-us2016 Maplesoft, A Division of Waterloo Maple Inc.Maplesoft Document SystemThu, 11 Feb 2016 06:29:49 GMTThu, 11 Feb 2016 06:29:49 GMTNew applications in the Graph Theory categoryhttp://www.mapleprimes.com/images/mapleapps.gifGraph Theory: New Applications
http://www.maplesoft.com/applications/category.aspx?cid=205
Knight'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 ZDr. Yury ZavarovskyDr. Yury ZavarovskyClassroom 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 LopezClassroom 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 MonaganHollywood 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 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 LopezTraveling 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 GuerrieriOptions 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 HlivkaClassroom 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 LopezStratum and Compactness Maplet
http://www.maplesoft.com/applications/view.aspx?SID=5565&ref=Feed
This maplet allows the user to compute the two useful measures for the hyperdocuments: Stratum and Compactness. These concepts arose from the modelling studies of the hyperdocument (or Web, in general) and user navigation based on the graph theory. It will also draw the graph and display the adjacency and distance matrices.<img src="/view.aspx?si=5565/img1.jpg" alt="Stratum and Compactness Maplet" align="left"/>This maplet allows the user to compute the two useful measures for the hyperdocuments: Stratum and Compactness. These concepts arose from the modelling studies of the hyperdocument (or Web, in general) and user navigation based on the graph theory. It will also draw the graph and display the adjacency and distance matrices.5565Wed, 19 Dec 2007 00:00:00 ZDr. Tolga GuyerDr. Tolga GuyerKruskals Algorithm for Finding a Minimum Spanning Tree
http://www.maplesoft.com/applications/view.aspx?SID=5087&ref=Feed
An implementation of Kruskal's Algorithm for finding a minimum spanning tree.<img src="/view.aspx?si=5087/kruskal_v1_0_maple11_5.jpg" alt="Kruskals Algorithm for Finding a Minimum Spanning Tree" align="left"/>An implementation of Kruskal's Algorithm for finding a minimum spanning tree.5087Wed, 11 Jul 2007 00:00:00 ZJay PedersenJay PedersenDijkstras Shortest Path Algorithm
http://www.maplesoft.com/applications/view.aspx?SID=4969&ref=Feed
An implementation of Dijkstra's Shortest Path algorithm as a Maple package.<img src="/view.aspx?si=4969/dijkstra_v2_maple11_4.jpg" alt="Dijkstras Shortest Path Algorithm" align="left"/>An implementation of Dijkstra's Shortest Path algorithm as a Maple package.4969Tue, 29 May 2007 00:00:00 ZJay PedersenJay PedersenSkeleton/Medial Axis of a Convex Polygon
http://www.maplesoft.com/applications/view.aspx?SID=1664&ref=Feed
This worksheet introduces the reader to a simple (non-optimal) algorithm for determining the Skeleton/Medial Axis of a convex polygon. The skeleton is the locus of the centers of all maximal discs within the polygon. We use the graph structure available in Maple's networks package to manage the information.<img src="/view.aspx?si=1664/Medical Axis2a.JPG" alt="Skeleton/Medial Axis of a Convex Polygon" align="left"/>This worksheet introduces the reader to a simple (non-optimal) algorithm for determining the Skeleton/Medial Axis of a convex polygon. The skeleton is the locus of the centers of all maximal discs within the polygon. We use the graph structure available in Maple's networks package to manage the information.1664Fri, 09 Sep 2005 00:00:00 ZDr. Bruno GuerrieriDr. Bruno GuerrieriChromial
http://www.maplesoft.com/applications/view.aspx?SID=1653&ref=Feed
An effective algorithm for computing chromatic polynomials of connected graphs is presented. The range and speed of this algorithm are substantially beyond otheralgorithms for this purpose.<img src="/view.aspx?si=1653//applications/images/app_image_blank_lg.jpg" alt="Chromial" align="left"/>An effective algorithm for computing chromatic polynomials of connected graphs is presented. The range and speed of this algorithm are substantially beyond otheralgorithms for this purpose.1653Fri, 19 Aug 2005 00:00:00 ZProf. gary haggardProf. gary haggardDijkstra's Algorithm for Determining Shortest Paths
http://www.maplesoft.com/applications/view.aspx?SID=1468&ref=Feed
An implementation of Dijkstra's Algorithm to determine shortest paths in a network.
Uses forward-star structure to process graph definitions.<img src="/view.aspx?si=1468/dijkstra_2.gif" alt="Dijkstra's Algorithm for Determining Shortest Paths" align="left"/>An implementation of Dijkstra's Algorithm to determine shortest paths in a network.
Uses forward-star structure to process graph definitions.1468Fri, 13 May 2005 00:00:00 ZJay PedersenJay PedersenGraph Analysis Maplet
http://www.maplesoft.com/applications/view.aspx?SID=4587&ref=Feed
Takes a graph (in Maple syntax) and allows the user to compute a variety of graph invariants and polynomials for it.<img src="/view.aspx?si=4587//applications/images/app_image_blank_lg.jpg" alt="Graph Analysis Maplet" align="left"/>Takes a graph (in Maple syntax) and allows the user to compute a variety of graph invariants and polynomials for it.4587Mon, 01 Nov 2004 00:00:00 ZPatti BodkinPatti BodkinDirected vs Undirected RootedTrees
http://www.maplesoft.com/applications/view.aspx?SID=4589&ref=Feed
When this maplet is run, it allows the student to examine various aspects of rooted trees. The results from Dijkstra's algorithm for shortest path spanning tree, Floyd's allpairs shortest path algorithm, and Prim's Algorithm may be examined. The maplet opens with a window asking the student to input either a directed or undirected graph. A different Maplet appears depending on the student's response. The maplet was constructed using Maple 9.5<img src="/view.aspx?si=4589/thumb.gif" alt="Directed vs Undirected RootedTrees" align="left"/>When this maplet is run, it allows the student to examine various aspects of rooted trees. The results from Dijkstra's algorithm for shortest path spanning tree, Floyd's allpairs shortest path algorithm, and Prim's Algorithm may be examined. The maplet opens with a window asking the student to input either a directed or undirected graph. A different Maplet appears depending on the student's response. The maplet was constructed using Maple 9.54589Mon, 01 Nov 2004 00:00:00 ZLaurie LaceyLaurie LaceyMax Flow - Min Cut
http://www.maplesoft.com/applications/view.aspx?SID=4513&ref=Feed
When this maplet is run, it allows the student to examine the Max Flow - Min Cut Theorem. Students can compare the value of the maximum flow to the value of the minimum cut, and determine the edges of the minimum cut as well as the saturated edges. Students can observe the graph with the minimum cut edges removed. The maplet was constructed using Maple 9.5. A sample graph has been loaded into the first textfield so the student can see the syntax.<img src="/view.aspx?si=4513//applications/images/app_image_blank_lg.jpg" alt="Max Flow - Min Cut" align="left"/>When this maplet is run, it allows the student to examine the Max Flow - Min Cut Theorem. Students can compare the value of the maximum flow to the value of the minimum cut, and determine the edges of the minimum cut as well as the saturated edges. Students can observe the graph with the minimum cut edges removed. The maplet was constructed using Maple 9.5. A sample graph has been loaded into the first textfield so the student can see the syntax.4513Wed, 07 Jul 2004 09:19:33 ZLaurie LaceyLaurie LaceyA Maplet for Graph Drawing
http://www.maplesoft.com/applications/view.aspx?SID=4406&ref=Feed
When this maplet is run, it allows the student to examine a graph and its spanning tree visually. The student may also examine the adjacency matrix, the chromatic polynomial, the degree sequence, and the diameter of the graph. The maplet was built using the Maple 9 Classic worksheet.<img src="/view.aspx?si=4406//applications/images/app_image_blank_lg.jpg" alt="A Maplet for Graph Drawing" align="left"/>When this maplet is run, it allows the student to examine a graph and its spanning tree visually. The student may also examine the adjacency matrix, the chromatic polynomial, the degree sequence, and the diameter of the graph. The maplet was built using the Maple 9 Classic worksheet.4406Thu, 14 Aug 2003 09:29:49 ZLaurie LaceyLaurie LaceyA Drawing Routine for Symmetric Graphs in the Plane
http://www.maplesoft.com/applications/view.aspx?SID=4394&ref=Feed
This Maple application provides a routine for drawing some interesting symmetric graphs in the plane. Nodes can be drawn with any radius, and edge lines stop at the boundaries of the nodes.<img src="/view.aspx?si=4394/graph.gif" alt="A Drawing Routine for Symmetric Graphs in the Plane" align="left"/>This Maple application provides a routine for drawing some interesting symmetric graphs in the plane. Nodes can be drawn with any radius, and edge lines stop at the boundaries of the nodes.4394Fri, 06 Jun 2003 16:48:47 ZStephen LockeStephen LockeIntroduction to Graph Theory
http://www.maplesoft.com/applications/view.aspx?SID=4097&ref=Feed
Explore the world of graphs, create graphs in Maple and generate diagrams and adjacency matrices, examine equivalency of graphs, and the concepts of connected and unconnected graphs.
<img src="/view.aspx?si=4097//applications/images/app_image_blank_lg.jpg" alt="Introduction to Graph Theory " align="left"/>Explore the world of graphs, create graphs in Maple and generate diagrams and adjacency matrices, examine equivalency of graphs, and the concepts of connected and unconnected graphs.
4097Fri, 17 Aug 2001 13:32:46 ZGregory MooreGregory Moore