Send the link below via email or IMCopy
Present to your audienceStart remote presentation
- Invited audience members will follow you as you navigate and present
- People invited to a presentation do not need a Prezi account
- This link expires 10 minutes after you close the presentation
- A maximum of 30 users can follow your presentation
- Learn more about this feature in the manual
Do you really want to delete this prezi?
Neither you, nor the coeditors you shared it with will be able to recover it again.
Make your likes visible on Facebook?
Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.
Application of Graph Theory in real world
Sanjay pandeyon 22 September 2012
Transcript of Application of Graph Theory in real world
In 2009 the US company Netflix awarded $1 million to the people who best improved their recommendation algorithm. Making recommendations Google sees the internet is a giant graph.
Each webpage is a node, and two pages are joined by an edge if there is a link from one page to the other.
Note: the edges in the internet graph have a direction.
The algorithm that Google uses to rank its searches is called PageRank. The internet to Google How does Google work? Heuristic algorithms can find solutions to TSP with millions of cities in a fairly short amount of time.
Caveat: these solutions may not always be the best possible. Methods of solving the TSP Heuristics: find ‘good’ solutions which are highly likely to be close to the perfect solution. For example,
The nearest neighbour algorithm lets the salesman pick the nearest unvisited city every time.
Find any route, then rearrange edges to find a shorter one. Methods of solving the TSP Branch and bound algorithms – divide the problem into smaller graphs and try to eliminate edges that can’t be part of the solution.
The record set with this kind of exact method is 85,900 cities, which took over 126 CPU years to compute in 2006. Methods of solving the TSP This is the poster for a contest run by Proctor & Gamble in 1962.
There were 33 cities in this problem. One critic said
“A good mathematical proof is like a poem. This is a telephone directory!”
However, the proof is now widely accepted and computers are used in many areas of pure mathematics. The 4-colour problem can be phrased in terms of graphs.
Each region of the map becomes a node, with two nodes being connected by an edge if and only if the regions are adjacent on the map.
The problem becomes: can you colour the nodes with 4 colours so that an edge never connects two nodes of the same colour? It was proved by 1890 that every map can be coloured with at most 5 colours.
The difficult part of the problem was to show that there was no map sufficiently complicated as to need 5 colours.
Martin Gardner set the following graph as a problem to his readers. Can you colour it using only 4 colours? Why not 5 colours? Example of a 4-colouring The Four Colour Theorem That Graph Theory is an incredibly important part of modern-day life.
That a solution to a single graph theory problem can have many different real-world applications.
That problems in graph theory can be worth a lot of money! Conclusion People who understand PageRank can make it very lucrative for them.
For example, businesses or individuals with a high page rank can sell links to those wishing to boost their page rank.
Businesses have also used similar algorithms to rank universities in the job market. Using PageRank to make money! Example Idea: the more links a page has pointing to it, the more important it is.
Second idea: if an important page links to your page, this is worth more than if an unimportant page links to you.
For example, Microsoft referencing you is worth more than Sharda you. How does PageRank work? The Travelling Salesman Problem has lots of applications in our lives:
Logistics of delivering goods
Drilling holes in circuit boards
Programming space telescopes like Hubble
Collecting post from postboxes every day
Making travel itineraries Applications Brute force – try all possible routes and pick the fastest one.
Caveat: using today’s fastest supercomputer, solving the 33-city problem using this method would take about 100 trillion years! Martin Gardner’s map Proposed by Francis Guthrie in 1852 and remained unsolved for more than a century.
Can any map be coloured with 4 colours so that no two adjacent regions have the same colour? The Four-Colour Problem Social networks Examples of graphs Train maps Examples of graphs Euler’s Eureka! moment was realising that whenever you cross into a bit of land, you also have to cross back out of it.
Therefore, for a bridge tour to be possible, there must be an even number of bridges coming out of every bit of land.
(Except for the starting and finishing points.) Conditions for a solution In 1736 Euler turned his mind to the problem of the bridges of Königsberg.
He realised that it didn’t matter how you walked around the land, or where exactly the bridges were.
It only mattered how many bridges there were between each bit of land, and in what order you crossed them. Königsberg… The residents of Königsberg wondered whether they could wander around the city, crossing each of the seven bridges once and only once.
Can you find a way? The Seven Bridges of Königsberg Running through the city was the River Pregel.
It separated the city into two mainland areas and two large islands.
There were 7 bridges connecting the various areas of land. The Seven Bridges of Königsberg Once upon a time there was a city called Königsberg in Prussia.
The capital of East Prussia until 1945.
It was a centre of learning for centuries, being home to Goldbach, Hilbert, Kant and Wagner. The Seven Bridges of Königsberg What was the famous Königsberg bridge problem?
Why was the 4-colour theorem controversial?
Why is it so hard for salesmen to be efficient?
How does Google work? Topics to be discussed Graphs are also important to social networking sites like Facebook.
By analysing the preferences of your ‘friends’ and pages that you ‘like’, Facebook can target its advertising very effectively. Social networking If, instead, you are a travelling salesman, you wish to find the route that allows you to visit each town exactly once (and then return to the start).
This problem was posed as long ago as 1800 by the Iris mathematician Hamilton, and rose drastically in popularity in the 1950s and 60s. The travelling salesman problem They had made a computer program to check the 4-colouring of all possible examples (1,936 of them!).
It was the first mathematical theorem to be proved with computer help, and aroused much controversy. Chemical models Examples of graphs A simple example shows that it impossible to always colour a map with only 3 colours. Why not 3 colours? D C B If we look again at the map of Königsberg, we see that there are an odd number of bridges coming out of every bit of land, so such a walk around the city is impossible. An impossible problem! A D C B A With this observation, we can re-draw the bridges of Königsberg as follows: Reformulating the problem edge node It doesn’t matter how long the edges are or where the nodes are; it only matters which edges are connected to which nodes. By solving the problem the way he did, Euler invented the subject of graph theory.
A graph is a collection of nodes and edges. The beginning of graph theory Königsberg bridge problem 4-colour theorem Travelling Salesman Problem In terms of graphs In 1976, two men called Kenneth Appel and Wolfgang Haken announced that they had a proof of the conjecture. A proof? A controversial result An inelegant result Maps to graphs: example Methods of solving the TSP Google