**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

Ideas:

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.

Euler

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

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

vertex

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

edge

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**

A

B

C

D

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.

Summary

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

v

and the branches as

v-1

.

Trees and Graph Theory

**Trees and Graphs**

Observations

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

A

rooted tree

is one in which exactly one vertex is distinguished (called the root).

A

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.