Math Department, Mission College, Santa Clara, California

Go to Math Dept Main
Page | Go to Mission
College Main Page

This paper was written as an
assignment for Ian Walton's Math G - Math for liberal Arts Students - at Mission College. If you use material from this
paper, please acknowledge it.

To explore other such papers go to the Math G
Projects Page

Math G – Final                                                                                   Selena
Gutierrez

Dr.
Walton                                                                                          May 10, 2010

Graph
Theory

I’ve had to use graphs for many different
courses and assignments. Surprisingly, not all of those assignments were for a
math class. Of course, when thinking of graphs, we assume that it will only be
in the area math. But, I’ve also had to use graphs in an English course
and a few of my communications courses. In fact, graphs have popped up in my
studies anytime I had to make comparisons, or connect ideas. Graph Theory is
the study of graphs. Graphs, as defined by Wikipedia, are mathematical
structures used to model pair wise relations between objects from a certain
collection (Wikipedia). This paper will discuss graphs as related to the Graph
Theory. In this case, a graph is a set of vertices (V) and edges (E), which
connect to make pairs of element V (mathematical atlas). In order for these
vertices and edges to connect, there must also be a rule to connect the two,
forming the graph. Graph Theory is used mainly to illustrate networks, and is
extremely in computer science and engineering. We can see instances of Graph
Theory in several different math subjects, as well as in networking problems.
There is even a link between Graph Theory and sociology and biology. A paper written
by Amol Deshpande at the University of Maryland and Sunita Sarawagi of IIT Bombay,
stated that graphical models provide a compact representation of the full joint
distribution of a set of variables as a graph whose nodes are the variables and
whose edges connect variables who interact directly (Deshpande, Sarawagi).

Below
is an image illustrating a simple graph in graph theory.

http://en.wikipedia.org/wiki/File:6n-graf.svg

The history of Graph Theory begins with the town of Konigsberg, Germany. This town was divided into two by the Preger River,
connected by 7 different bridges. The people of Konigsberg frequently wondered if there was a walking route where they would be
able to cross each bridge exactly once. This is when Leonhard Euler (1707
– 1783), a Swiss mathematician, began what is now called the Graph Theory
(Timmons). In order to solve this problem, Euler first took the map of Konigsberg and the bridges, and made a graph similar to the graph shown above. In
his graph, the vertices illustrated the parts of the land of the town, and the
edges illustrated the bridges of the town with the chain becoming the path of
the graph. With this graph, Euler was set out to prove that there was no such
path where a person would be able to take a path and cross each bridge once,
and from this situation the Eulerian path and Eulerian graph was born.  An Eulerian path is when a path is found
where you follow, or “walk” along each path, or edge, exactly once
and the graph for this is called an Eulerian graph. A good example of a
Eulerian path is the childhood game of drawing a house without lifting your
pencil, or duplicating a line.

http://www.mathematische-basteleien.de/haus10.gif

In graph theory, there are two main
data structures – list structure and matrix structure. List structure
matrices are also broken down into two – an incidence list matrix and an
adjacency list matrix. An incidence list is made up of edges represented by
pairs of vertices, with vertices connected by an edge being adjacent (Wiki). An adjacency list
is similar to an incident list, as it also lists the adjacent edges and
vertices, but with an adjacency list there could be instances of redundancy
because each adjacent vertex can be counted each time it occurs. If vertices A
and B are adjacent, then the A’s list will contain B, and B’s list
will contain A (Wikipedia). The adjacency list the ideal list for maximum
storage capacity in network systems.

Matrix structures of graph theory include four
separate matrices, which includes incident and adjacency as well. The other two
are the distance matrix and the Laplacian Matrix, which is also known as the
Kirchhoff matrix, or Admittance matrix. An incidence matrix is a graph that
is made up of the number of vertices and the number of edges. Incidence
matrices are (0,1) matrices where there are to be no zero rows columns
(Cameron, Prellberg, Stark). A (0,1) matrix is where the elements are either
zero or one.  In an incidence
matrix, the point where the edge and vertex meets will contain information
about where the end of the matrix will be. The example below shows an incidence
list and matrix.

http://mathworld.wolfram.com/images/eps-gif/IncidenceMatrix_999.gif

In the first example above, the vertex 4, which is the last
row, has an edge to each of the other vertices. An adjacency matrix is an nxn
matrix A. In this matrix, n is the number of vertices in the graph. If
vertex x and vertex y and connected by an edge, then that is labeled as axy
is 1 (one), it is not connected by an edge then it is a zero (Wikipedia). The
Laplacian Matrix, take A (adjacency matrix) and subtracts the degree matrix.
The definition for the Laplacian matrix is D-A. This type of matrix includes
the information not only for the degree, but also for the adjacency as well.
And finally, the distance matrix is a degree matrix shown by an n by n
matrix, which is shows as dxy.
In network systems and computing, the adjacency matrix would be the
matrix to use if you were looking for any subgraphs, and the distance matrix is
what you would want to use to get the shortest path between an edge and vertex.
Here are examples of what each of these matrices looks like when applied–

Incidence Matrix – http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/LEC/LECTUR14/IMG887.GIF

Adjacency Matrix –

http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/LEC/LECTUR14/IMG887.GIF

Laplacian Matrix –

http://en.wikipedia.org/wiki/Laplacian_matrix

a

b

c

d

e

f

a

0

184

222

177

216

231

b

184

0

45

123

128

200

c

222

45

0

129

121

203

d

177

123

129

0

46

83

e

216

128

121

46

0

83

f

231

200

203

83

83

0

Distance Matrix –

If you’ve
ever wondered how web search engines work, the answer lies in linear algebra,
which is an element of algebraic graph theory. How exactly does it work? Well,
let’s take a look at Google’s PageRank algorithm. A webpage is
given a ranking based on how many high ranked websites link to the website. The
more links directing you to a certain website, the better your rank will be. A
simple graph for a set of 8 web pages would look like this –

http://www.ams.org/samplings/feature-column/fcarc-pagerank

In
the picture above, the webpage represented by vertex 8, would have the highest
page ranking because it has the most links directing to it. Though, this is a very
simple illustration, web search engines use this model as a way to rank the
millions of websites out there in cyberspace.

Graphing
Theory is also a part of geometry with Geometric Graph Theory. While
researching geometric graph theory, I found that there is a graphing theory for
a collection of sets. This is called an intersection graph. An intersection
graph is defined as an undirected graph formed from a family of sets
(Wikipedia). For example, of we had V(A) and E(A), we would know that we are illustrating
the vertices and edge of set A. If set A {1,2,3,4,5}, and set B{5,6,7,8,9},
then we would create a vertex for both of the sets – Va, Vb.
If  I= the intersection graph, then
the formula for an intersection graph would be –

E(I) = {{ Va,
Vb} | A|B}

As discussed in the engineering journal IIE Transactions, an
intersection graph for rectangles on a plane can be used to solve design
problems of the Flexible Manufacturing Systems (FMS) punch
press in the production of flat sheet metal. Because the advantages of FMS include
time-savings, it is important to make sure that a solution is found for those
in this field. This is something that you and I may not find important, but
engineers or machinists who work with sheet metal frequently, would be extremely
interested in the results of this study.
Here is an example of what an intersection graph can be illustrated as
–

http://en.wikipedia.org/wiki/Intersection_graph

Notice how, although the vertices are in a single set, the
edge must pass through one or more other sets to get to the next vertex.

This
semester, we also discussed probabilities, which also happens to be an element
in graph theory as the Probabilistic graph theory. Graphs that fall under
probabilistic graph theory are graphs that are obtained by adding random edges
in between vertices at random. Paul Erdos and Alfred Renyi first introduced
random graphs to the world in the paper “On Random Graphs”
(Wikipedia). Erdos frequently challenged his followers to solve a problem he created
with a monetary prize offered, coming out of his own pocket.  The problem was this – Prove that
among any six people at a gathering, there will always be three mutual
acquaintances and three mutual non-acquaintances (Erdos). In order to solve a
probabilistic problem like this, first you would have to figure out which
graphs do not solve this problem, because Erdos stated that if it can be shown
that this number of graphs that do not work is definitely less than the total
number of graphs with a given number n of points, then there must exist
a graph with the property in question (Erdos). Ramsey, an English philosopher
and mathematician, created a theorem from which the probabilistic methods were
discovered. Ramsey claimed that every infinite graph also contained a complete
infinite subgroup, or independent set of points (Erdos).

Graph
Theory plays a role in biology. Because our bodies are made up of so many
different part working together, biologists have had to use graph theory
applications to learn about the network systems of our bodies, much like as
seen in analyzing computer science. In May of 2009, the International Journal
of Health Geographics published a report titled, “A graph-theory method for pattern identification in
geographical epidemiology - a preliminary application to deprivation and
mortality” where it discussed using graph theory as an alternative way to
research the clusters of disease. Usually, geographic information systems are
used to detect clusters of disease and used to identify a pattern, but the more
complex the disease is, the more complex it is to track the pattern of the
cluster. The approach graph theory uses in computer science, may be a great
method to use in researching the patterns of the more complex disease clusters.  In this experiment, the vertices
represented census enumeration districts (CEDs) and the edges were determined
by whether or not CEDs where neighbors (Maheswaran, Craigs, Read, Bath, and Willett) If the CEDs where neighbors, then they
were adjacent, meaning that they were part of the same cluster. Researchers
were able to determine whether or not the clusters were associated with each
other or not. This is just one example of how the graph theory has applied to
biological research. Just imagine with all of the different components of a
human body and all the potential connections, how different graphs of different
parts of our bodies would look.

Graph theory is not only present in biology, but also
in sociology, specifically in social network analysis. Social network analysis
studies the importance of relationships in comparison with other relationships.
Think of how Facebook is able to give you friend suggestions. They take the
friends that you have, and compare friends of your friends to decide whether
you may know that person or not. This explanation is very simple, and just a
tiny tip of the iceberg. This idea has been around for many years, but may have
been popularized with the Six Degrees of Separation theory. The idea is that
everyone on the planet is linked to another person, but six degrees at the
most. There is even a map to illustrate this idea –

http://en.wikipedia.org/wiki/File:Six_degrees_of_separation.svg

Each
vertex in the middle (V1 - V6) has an edge connecting to
other people (vertices), all of these vertices at some point intersect with
another but no more than 6 degrees, making a connection.

As
you can see, the ideas of graph theory are applied to many different areas
other than directly mathematics. I have come to notice that my day-to-day functions
have some sort of link to graph theory. Although the actual formulas are a
little bit scary to look at, if you now what it is used for, it is a lot easier
to understand. While researching this topic, I was able to link graph theory to
games I’ve played. Graph theory is a great resource for medical
researches, so you can say that graph theory can even save lives.

Works Cited

Timmons, Todd. "The Birth of Graph
Theory: Leonhard Euler and the Königsberg Bridge Problem." Science and Its Times:
Understanding the Social Significance of Scientific
Discovery. Eds. Josh Lauer and Neil
Schlager. Vol. 4. Detroit: Gale, 2000. 227-229. 8 vols. Gale
Virtual Reference Library. Gale. Mission College Library. 8 May. 2010

<http://0-find.galegroup.com.library.wvmccd.cc.ca.us/gvrl/infomark.do?&contentSet=EBKS&type=retrieve&tabID=T001&prodId=GVRL&docId=CX3408501899&source=gale&userGroupName=mission_main&version=1.0>.

Wikipedia contributors.
"Graph theory." Wikipedia, The Free Encyclopedia. Wikipedia,
The Free Encyclopedia, 8 May. 2010. Web. 13 May. 2010.

"05C: Graph theory." The Mathematical
Atlas. N.p., 14/01/2001. Web. 3 May 2010.
<http://www.math.niu.edu/~rusin/known-math/index/05CXX.html>.

Timmons, Todd. "Science and Its Times." The
Birth of Graph Theory: Leonhard Euler. 1. 4. Gale, 2001. Print

Deshpande, Amol, and Sunita Sarawagi.
"Probabilistic Graphical Models and their Role in Databases." citeseerx.
N.p., n.d. Web. 1 May 2010.
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.98.4577>.

Erdos, Paul. N.p., n.d. Web. 12 May 2010.
<http://www.renyi.hu/~p_erdos/1967-02.pdf>.

Maheswaran, Ravi, Cheryl Craigs,
Simon Read, Peter, A Bath, and Peter Willett. "A graph-theory method for
pattern identification in geographical epidemiology – a preliminary
application to deprivation and mortality." International Journal of
Health Geographics 8.28 (2009): n. pag. Web. 3 May 2010.
<http://www.ij-healthgeographics.com/content/8/1/28>.