Present Remotely

Send the link below via email or IM

• 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

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

Graph Theory

No description
by

Roxana Popescu

on 30 May 2014

Report abuse

Transcript of Graph Theory

Graph Theory
Roxana Popescu, Dongchen Li, and Celia Karpatkin
The Seven Bridges of Konisburg
Four-Color Map Theorem
It states that no more than four colors are needed to color a map so that adjacent regions of the map do not have the same color.
In order for a map to meet the requirements for the four color theorem:
The regions on the map must be contiguous
The regions on the map must have a finite area and a finite perimeter
The corners where regions meet are not considered adjacent
Using graph theory, each region can be represented by a vertex and each boundary between regions can be represented by an edge.
The Traveling Salesman
If we have a list of cities and the distances between them, what is the shortest path to visit every city once and then return to the first city?
A graph in discrete mathematics is a way of interpreting data as a set of vertices and edges. It is at the origin of the branch of mathematics known as Topology.
Applications
Solving the TSP
Genome Sequencing
NASA Starlight
Art
this image uses 27,846 carefully placed cities to create the Mona Lisa.
The World Tour
this shows a world tour of length 7,516,353,779m through all 1,904,711 cities in the world. It is at most 0.076% off the ideal route.
Sources
http://www.utm.edu/departments/math/graph/
http://jgaa.info/
http://www.ics.uci.edu/~eppstein/pubs/graph.html
http://www.mathpages.com/home/kmath266/kmath266.htm
http://www.huffingtonpost.com/david-h-bailey/kenneth-appel-four-color-theorem_b_3233775.html

As often happens in mathematics, a simple problem began the creation of a new field of mathematics: In the 1700's the townspeople of old Königsberg, East Prussia, wondered if was possible to take a walk around their town in such a way as to cross each of the seven bridges exactly once.
History
The great mathematician Euler began by pointing out that the shapes and sizes of the land masses and bridges did not matter--so he reduced (in words) the drawing above to the following graph.This simple idea began the study of graph theory!
"Is there a path which traverses every edge in this graph exactly once?"
SO here is the new question
Euler's answer is "No. It is impossible."
And here is why...

Theorem
A connected graph has an Euler path (which is not a circuit) if and only if it has exactly two vertices with odd degree.
Proof
The four color map theorem was first conjectured in 1852 by Francis Guthrie.
Several failed attempts were made to prove the theorem until 1976 when it was proven by Kenneth Appel and Wolfgang Haken by using a computer.
However, this proof was met with criticism
In 2005, Werner and Gonthier used a theorem proving software used by mathematicians to finally prove the theorem.

The 1976 proof began with the assumption that if the four color theorem is false then there must be a map with the smallest number of regions that requires four colors.
Using the computer, 1,936 configurations of possible counterexamples were found.
The computer then checked all of these configurations and determined that all of these could be colored by using only four colors.
By proving that there was no counterexample, the theorem was proven to be true.
Origins are unclear, but first formulated as a mathematical problem in the 1800s by W. R. Hamilton and Thomas Kirkman.
became popular in the 1950s and 60s as it was applied to chemistry, physics, and computer science
in the 1990s, four mathematicians created the computer program Concorde to solve TSP problems within 2-3% accuracy
Concorde was used to solve a 85,900-city problem, a microchip layout problem, exactly
We can simply find the brute-force solution by trying every possible route and finding the shortest path. but this gets tedious.
various dynamic programming algorithms exist for solving or approximating the solutions.
the branch-and bound algorithm consists of finding upper and lower bounds for the solution.
the upper bound is the "Nearest Neighbor" algorithm
the lower bound is more complicated to find--find a min spanning tree, add vertice back in
Full transcript