Graph Theory: New Applications
https://www.maplesoft.com/applications/category.aspx?cid=205
en-us2021 Maplesoft, A Division of Waterloo Maple Inc.Maplesoft Document SystemTue, 26 Oct 2021 07:45:02 GMTTue, 26 Oct 2021 07:45:02 GMTNew applications in the Graph Theory categoryhttps://www.maplesoft.com/images/Application_center_hp.jpgGraph Theory: New Applications
https://www.maplesoft.com/applications/category.aspx?cid=205
Game of Thrones and Graph Theory
https://www.maplesoft.com/applications/view.aspx?SID=154529&ref=Feed
Graph theory can help you understand the social landscape of the television series Game of Thrones, based upon the A Song of Ice and Fire books. With the judicious use of Maple, you can ask yourself really pressing questions like
<UL>
<LI>Who is the most influential person in Westeros? How has their influence changed over each season?</LI>
<LI>How are Eddard Stark and Randyll Tarly connected?</LI>
<LI>What do eigenvectors have to do with the battle for the Iron Throne, anyway?</LI>
</UL>
This application uses data from the television series. See <A HREF="https://www.maplesoft.com/applications/view.aspx?SID=154530">A Song of Ice and Fire and Graph Theory</A> to ask these types of questions using data for the books.<img src="https://www.maplesoft.com/view.aspx?si=154529/thumb.png" alt="Game of Thrones and Graph Theory" style="max-width: 25%;" align="left"/>Graph theory can help you understand the social landscape of the television series Game of Thrones, based upon the A Song of Ice and Fire books. With the judicious use of Maple, you can ask yourself really pressing questions like
<UL>
<LI>Who is the most influential person in Westeros? How has their influence changed over each season?</LI>
<LI>How are Eddard Stark and Randyll Tarly connected?</LI>
<LI>What do eigenvectors have to do with the battle for the Iron Throne, anyway?</LI>
</UL>
This application uses data from the television series. See <A HREF="https://www.maplesoft.com/applications/view.aspx?SID=154530">A Song of Ice and Fire and Graph Theory</A> to ask these types of questions using data for the books.https://www.maplesoft.com/applications/view.aspx?SID=154529&ref=FeedWed, 27 Mar 2019 04:00:00 ZSamir KhanSamir KhanA Song of Ice and Fire and Graph Theory
https://www.maplesoft.com/applications/view.aspx?SID=154530&ref=Feed
Graph theory can help you understand the social landscape of the books in the series A Song of Ice and Fire by G. R. R. Martin. With the judicious use of Maple, you can ask yourself <i>really</i> pressing questions like
<UL>
<LI>Who is the most influential person in Westeros? How has their influence changed over the five books?</LI>
<LI>How are Eddard Stark and Randyll Tarly connected?</LI>
<LI>What do eigenvectors have to do with the battle for the Iron Throne, anyway?</LI>
</UL>
This application uses data from the books. See <A HREF="https://www.maplesoft.com/applications/view.aspx?SID=154529">A Game of Thrones and Graph Theory</A> to ask these types of questions using data for the television series.<img src="https://www.maplesoft.com/view.aspx?si=154530/thumb.png" alt="A Song of Ice and Fire and Graph Theory" style="max-width: 25%;" align="left"/>Graph theory can help you understand the social landscape of the books in the series A Song of Ice and Fire by G. R. R. Martin. With the judicious use of Maple, you can ask yourself <i>really</i> pressing questions like
<UL>
<LI>Who is the most influential person in Westeros? How has their influence changed over the five books?</LI>
<LI>How are Eddard Stark and Randyll Tarly connected?</LI>
<LI>What do eigenvectors have to do with the battle for the Iron Throne, anyway?</LI>
</UL>
This application uses data from the books. See <A HREF="https://www.maplesoft.com/applications/view.aspx?SID=154529">A Game of Thrones and Graph Theory</A> to ask these types of questions using data for the television series.https://www.maplesoft.com/applications/view.aspx?SID=154530&ref=FeedWed, 27 Mar 2019 04:00:00 ZSamir KhanSamir KhanClique Finding with SAT
https://www.maplesoft.com/applications/view.aspx?SID=154502&ref=Feed
A clique of a graph is a subset of its vertices that are all mutually connected. Finding a clique of a given size in a graph is a difficult problem in general.
In this worksheet we demonstrate how to solve the clique finding problem by translating it into Boolean logic and using Maple's built-in efficient SAT solver. This approach even can out-perform the built-in Maple function FindClique which also solves the clique finding problem.<img src="https://www.maplesoft.com/view.aspx?si=154502/graph20.png" alt="Clique Finding with SAT" style="max-width: 25%;" align="left"/>A clique of a graph is a subset of its vertices that are all mutually connected. Finding a clique of a given size in a graph is a difficult problem in general.
In this worksheet we demonstrate how to solve the clique finding problem by translating it into Boolean logic and using Maple's built-in efficient SAT solver. This approach even can out-perform the built-in Maple function FindClique which also solves the clique finding problem.https://www.maplesoft.com/applications/view.aspx?SID=154502&ref=FeedThu, 15 Nov 2018 05:00:00 ZCurtis BrightCurtis BrightKnight's Tour
https://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="https://www.maplesoft.com/view.aspx?si=153842/26f19bd457ac566083dec1b86db8b91b.gif" alt="Knight's Tour" style="max-width: 25%;" 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.https://www.maplesoft.com/applications/view.aspx?SID=153842&ref=FeedThu, 13 Aug 2015 04:00:00 ZYury ZavarovskyYury ZavarovskyClassroom Tips and Techniques: Bivariate Limits - Then and Now
https://www.maplesoft.com/applications/view.aspx?SID=145979&ref=Feed
An introductory overview of the functionalities in Maple's GraphTheory package.<img src="https://www.maplesoft.com/view.aspx?si=145979/thumb.jpg" alt="Classroom Tips and Techniques: Bivariate Limits - Then and Now" style="max-width: 25%;" align="left"/>An introductory overview of the functionalities in Maple's GraphTheory package.https://www.maplesoft.com/applications/view.aspx?SID=145979&ref=FeedWed, 17 Apr 2013 04:00:00 ZDr. Robert LopezDr. Robert LopezClassroom Tips and Techniques: Introduction to Maple's GraphTheory Package
https://www.maplesoft.com/applications/view.aspx?SID=142357&ref=Feed
An introductory overview of the functionality in Maple's GraphTheory package.<img src="https://www.maplesoft.com/view.aspx?si=142357/thumb.jpg" alt="Classroom Tips and Techniques: Introduction to Maple's GraphTheory Package" style="max-width: 25%;" align="left"/>An introductory overview of the functionality in Maple's GraphTheory package.https://www.maplesoft.com/applications/view.aspx?SID=142357&ref=FeedThu, 17 Jan 2013 05:00:00 ZProf. Michael MonaganProf. Michael MonaganHollywood Math
https://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="https://www.maplesoft.com/view.aspx?si=6611/thumb.jpg" alt="Hollywood Math" style="max-width: 25%;" 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.https://www.maplesoft.com/applications/view.aspx?SID=6611&ref=FeedFri, 23 Sep 2011 04:00:00 ZMaplesoftMaplesoftClassroom Tips and Techniques: Plotting a Slice of a Vector Field
https://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="https://www.maplesoft.com/view.aspx?si=19202/thumb.png" alt="Classroom Tips and Techniques: Plotting a Slice of a Vector Field" style="max-width: 25%;" 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.https://www.maplesoft.com/applications/view.aspx?SID=19202&ref=FeedFri, 06 Mar 2009 00:00:00 ZDr. Robert LopezDr. Robert LopezTraveling Salesman Problem
https://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="https://www.maplesoft.com/view.aspx?si=6873/TSgif.gif" alt="Traveling Salesman Problem" style="max-width: 25%;" 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).https://www.maplesoft.com/applications/view.aspx?SID=6873&ref=FeedMon, 10 Nov 2008 00:00:00 ZBruno GuerrieriBruno GuerrieriOptions with Foreign Exchange Adjustment
https://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="https://www.maplesoft.com/view.aspx?si=6874/Quanto Options_95.gif" alt="Options with Foreign Exchange Adjustment" style="max-width: 25%;" 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.https://www.maplesoft.com/applications/view.aspx?SID=6874&ref=FeedMon, 10 Nov 2008 00:00:00 ZIgor HlivkaIgor HlivkaClassroom Tips and Techniques: Context-Menu Plotting
https://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="https://www.maplesoft.com/view.aspx?si=6816/1.jpg" alt="Classroom Tips and Techniques: Context-Menu Plotting" style="max-width: 25%;" 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.https://www.maplesoft.com/applications/view.aspx?SID=6816&ref=FeedTue, 28 Oct 2008 00:00:00 ZDr. Robert LopezDr. Robert LopezStratum and Compactness Maplet
https://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="https://www.maplesoft.com/view.aspx?si=5565/img1.jpg" alt="Stratum and Compactness Maplet" style="max-width: 25%;" 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.https://www.maplesoft.com/applications/view.aspx?SID=5565&ref=FeedWed, 19 Dec 2007 00:00:00 ZDr. Tolga GuyerDr. Tolga GuyerKruskals Algorithm for Finding a Minimum Spanning Tree
https://www.maplesoft.com/applications/view.aspx?SID=5087&ref=Feed
An implementation of Kruskal's Algorithm for finding a minimum spanning tree.<img src="https://www.maplesoft.com/view.aspx?si=5087/kruskal_v1_0_maple11_5.jpg" alt="Kruskals Algorithm for Finding a Minimum Spanning Tree" style="max-width: 25%;" align="left"/>An implementation of Kruskal's Algorithm for finding a minimum spanning tree.https://www.maplesoft.com/applications/view.aspx?SID=5087&ref=FeedWed, 11 Jul 2007 00:00:00 ZJay PedersenJay PedersenDijkstras Shortest Path Algorithm
https://www.maplesoft.com/applications/view.aspx?SID=4969&ref=Feed
An implementation of Dijkstra's Shortest Path algorithm as a Maple package.<img src="https://www.maplesoft.com/view.aspx?si=4969/dijkstra_v2_maple11_4.jpg" alt="Dijkstras Shortest Path Algorithm" style="max-width: 25%;" align="left"/>An implementation of Dijkstra's Shortest Path algorithm as a Maple package.https://www.maplesoft.com/applications/view.aspx?SID=4969&ref=FeedTue, 29 May 2007 00:00:00 ZJay PedersenJay PedersenSkeleton/Medial Axis of a Convex Polygon
https://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="https://www.maplesoft.com/view.aspx?si=1664/Medical Axis2a.JPG" alt="Skeleton/Medial Axis of a Convex Polygon" style="max-width: 25%;" 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.https://www.maplesoft.com/applications/view.aspx?SID=1664&ref=FeedFri, 09 Sep 2005 00:00:00 ZDr. Bruno GuerrieriDr. Bruno GuerrieriChromial
https://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="https://www.maplesoft.com/view.aspx?si=1653//applications/images/app_image_blank_lg.jpg" alt="Chromial" style="max-width: 25%;" 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.https://www.maplesoft.com/applications/view.aspx?SID=1653&ref=FeedFri, 19 Aug 2005 00:00:00 ZProf. gary haggardProf. gary haggardDijkstra's Algorithm for Determining Shortest Paths
https://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="https://www.maplesoft.com/view.aspx?si=1468/dijkstra_2.gif" alt="Dijkstra's Algorithm for Determining Shortest Paths" style="max-width: 25%;" align="left"/>An implementation of Dijkstra's Algorithm to determine shortest paths in a network.
Uses forward-star structure to process graph definitions.https://www.maplesoft.com/applications/view.aspx?SID=1468&ref=FeedFri, 13 May 2005 00:00:00 ZJay PedersenJay PedersenGraph Analysis Maplet
https://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="https://www.maplesoft.com/view.aspx?si=4587//applications/images/app_image_blank_lg.jpg" alt="Graph Analysis Maplet" style="max-width: 25%;" align="left"/>Takes a graph (in Maple syntax) and allows the user to compute a variety of graph invariants and polynomials for it.https://www.maplesoft.com/applications/view.aspx?SID=4587&ref=FeedMon, 01 Nov 2004 00:00:00 ZPatti BodkinPatti BodkinDirected vs Undirected RootedTrees
https://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="https://www.maplesoft.com/view.aspx?si=4589/thumb.gif" alt="Directed vs Undirected RootedTrees" style="max-width: 25%;" 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.5https://www.maplesoft.com/applications/view.aspx?SID=4589&ref=FeedMon, 01 Nov 2004 00:00:00 ZLaurie LaceyLaurie LaceyMax Flow - Min Cut
https://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="https://www.maplesoft.com/view.aspx?si=4513//applications/images/app_image_blank_lg.jpg" alt="Max Flow - Min Cut" style="max-width: 25%;" 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.https://www.maplesoft.com/applications/view.aspx?SID=4513&ref=FeedWed, 07 Jul 2004 09:19:33 ZLaurie LaceyLaurie Lacey