Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start 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 our knowledge base article

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 and some Applications

No description

Kaitlyn Philipson

on 15 December 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Graph Theory and some Applications

Applications of Graph Theory
Google sees the internet as a giant graph.

Each webpage is a vertex, and two pages are joined by an edge if there is a link from one page to the other.

The edges in the internet graph have a direction.

The algorithm that Google uses to rank its searches is called PageRank.
The World Wide Web

the more links a page has pointing to it, the more important it is.

if an important page links to your page, this is worth more than if an unimportant page links to you.
How does PageRank work?
Social networks
Examples of graphs
Train maps
Examples of graphs
Euler realized that if 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 realized 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.
The residents of Königsberg wondered whether they could take a tour where they would walk through the city and end up where they started by crossing each bridge only once.
The Seven Bridges of Königsberg
In the city of Königsberg in Prussia there was a river called River Pregel.

There were 7 bridges connecting the various areas of land.
The Seven Bridges of Königsberg
What was the famous Königsberg bridge problem?

How do trees connect graph theory to real world applications?

How does the World Wide Web connect to graph theory?
Topics to be discussed
Graphs are also connected to social networking sites like Facebook which would be considered an acquaintanceship graph.

In an acquiantanceship graph, people are used as the vertices and the edges are the connections between the people who know each other.
Social Networking
Chemical models
Examples of graphs
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!
By solving the problem the way he did, Euler invented the subject of graph theory.
A graph is a collection of vertices and edges.
The beginning of graph theory
It doesn’t matter how long the edges are or where the vertices are; it only matters which edges are connected to which vertices.
Königsberg Bridge Problem
The World Wide Web
Can you find a way?
The world wid web is growing constantly.

Scientists believe that the size of the web can be measured by the average number of connections it takes to link any two websites.

The diameter of the world wide web has been found to be 19.
19 Clicks of Separation
The World Wide Web
Six Degrees of Separation
An acquaintanceship graph links to the idea of the six degrees of separation.

This proved that in the human populaiton, the diameter is six or less, which means you can connect to a specific person by going through six people or less.
The Robot
The piece of software known as a robot tallied the number of links and measured how far the links were from one another.

This was a computer program that traveled the web and documented its encounters.

The data showed it was distributed according to a self-organizing mathematical principle called the power-tail law and no one knows why.
Researchers at the University of Notre Dame found that there were 19 clicks between any two web pages.

This is based on the six degrees of separation.

Trying to figure out how to calculate the diameter of the web, the researchers came up with an interesting search engine called the robot.
Euler and the Königsberg bridge problem sparked the connection to graph theory. Then followed the other exaples of graphs in real world applications.

Trees are one topic of graph theory that also connect to real world applications.

The world wide web can be viewed as a graph and there are many deeper topics within the idea of the two being connnected.
Examples of trees in Graph Theory
Trees and Graph Theory
Basic definition of a tree in graph theory is described as any two vertices that are connected by an edge (or branch).

The vertices can be noted as
and the branches as

Trees and Graph Theory
Trees and Graphs
If you were to remove an edge from a tree, that would create a disconnected graph.

In any connected graph (that is not a tree) you can find at least one edge that when removed will leave the graph still connected.

There is exactly one path between every pair of vertices in a graph, if and only if the graph is a tree.
Theorems on Trees
2. A forest of k trees which has a total of n vertices has (n-k) edges.
1. Any tree with at least two vertices has at least two pendant vertices.
pendant vertices have degree one
Tress, the Web and Nature?
The growth of the world wide web has been found to have the same pattern as nature.

Researchers have stated that the growth of the internet is just like a tree; the more pages, the more likely pages will be added to it.

The tree analogy is not perfect because the web does not take up physical space but the main point is that the web's growth follows some of the same natural laws.
Types of Trees
rooted tree
is one in which exactly one vertex is distinguished (called the root).

binary tree
is a rooted tree with at least three vertices where the root is of degree 2 and all the other vertices are of degree 3.
Another Look at the Problem
Works Cited
Foulds, L.R. Graph Theory Applications. New York: Springer-Verlag, 1992. 3-363. Print.

Hayes, Brian. "Graph Theory in Practice: Part 1." American Scientist. 88.1 (2000): 9-13.

"Tree (graph theory)." Wikipedia. Wikimedia Foundation, 14 Oct. 2013. Web. 18 Oct. 2013. <http://en.wikipedia.org/wiki/Tree_(graph_theory)>.

Wikipedia contributors. "Seven Bridges of Königsberg." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 30 Nov. 2013. Web. 6 Dec. 2013.
Full transcript