notes:discrete:discrete2010
<html> <script language=“JavaScript”> This will add the word javascript to the document title document.title = “Graph Theory” ; </script> </html> ~~DISCUSSION|Graphy Theory Project~~
~~TOC~~
Discrete Structures
Graph Theory
A project to document and explain graph theory…
For those unfamiliar, here is a page on wiki editing syntax that can be used here.
===== Graph Theory Overview =====
==== What is Graph Theory? ====
To understand graph theory, we must define what it is.
According to Websters, graph theory is a branch of mathematics concerned with the study of graphs.
1)
Ok, fine, but lets break it down further.
==A Graph Is==
A graph is used to represent a complex ideas with a clear visualization.
Graph can be defined as followings:
<code>
1 - The collection of all points whose coordinates satisfy a given relation (as a function)
2 - A diagram (as a series of one or more points, lines, line segments, curves, or areas) that represents
the variation of a variable in comparison with that of one or more other variables
3 - A collection of vertices and edges that join pairs of vertices.
</code>
2)
==A Theory Is==
<code>
1 - The analysis of a set of facts in their relation to one another
2 - Abstract thought : speculation
3 - The general or abstract principles of a body of fact, a science, or an art <music theory>
4 - Belief, policy, or procedure proposed or followed as the basis of action
<her method is based on the theory that all children want to learn> b : an ideal or hypothetical
set of facts, principles, or circumstances —often used in the phrase in theory
5 - A plausible or scientifically acceptable general principle or body of principles offered
to explain phenomena <the wave theory of light>
6 - A hypothesis assumed for the sake of argument or investigation b : an unproved assumption :
conjecture c : a body of theorems presenting a concise systematic view of a subject <theory of equations>
</code>
3)
==Now what does that mean===
Graph theory provide a mathematically rigorous approach to examine the development and organization of complex systems. Which is applied to the mental lexicon4) to examine the organization of words in the lexicon and to explore how that structure might influence the acquisition5) and retrieval of phonological6) word-forms.
7)
graphs in practice.
* Routing
* Logistics
* Electrical circuits
* Chemistry
* Evolutionary Biology
* Parsers (e.g. compilers, file loaders)
* Analysis of the stability of multithreading application
* Every program can be modelled as a Turing Machine
* Flowcharts
* Artificial intelligence: Neural networks
* Databases
* Probability theory
* Google Page-Rank
* Social Networks
* Dating-Sites
* Computer Networks, such as the Internet
* Mind-mapping
* class hierarchies
8)
===== Origins and History =====
==== Mike: Pre(Early) - History ====
The origins of graph theory are steeped in mystery. The term “graph” first appeared in English in 1878 by JJ Sylvester, who used it to describe diagrams of chemical bonds of molecules.9)
<html>
<img src='http://ualr.edu/lasmoller/mathresources/sylvester.jpeg'></img>
<img src='http://www.biologie.uni-hamburg.de/b-online/ge18/04.gif'></img>
</html>
According to Dr Sarma 10) In 1906, Charles Sanders Peirce and Clifford further defined a graph as a diagram composed principally of spots and lines connecting certain spots. Pierce called his own logical diagrams graphs because they were also composed of spots and lines. Pierce used a more general definition as a curve showing the relationship between coordinates.
<html>
<img src='http://www.pragmatism.org/images/peirce.jpg'></img>
Pierce
</html>
==== Quinton Clark: Pre(Early) - History ====
The first person to apply graph theory was Leonhard Euler.<html>
<img src='http://www.ams.org/images/md-200704-euler.jpg'></img>
</html>
Euler wanted to see if it was possible to cross all seven bridges on the Pregel River in Konigsburg, Russia once and return to the same point from which he started. In 1735, Euler presented the solution to the problem before the Russian Academy. He explained why crossing all seven bridges without crossing a bridge twice was impossible. While solving this problem, he developed a new mathematics field called graph theory, which later served as the basis for another mathematical field called topology.
<html>
<img src='http://math.youngzones.org/Konigsberg_bridge.jpg'></img>
</html>
Euler simplified the bridge problem by representing each land mass as a point and each bridge as a line. He reasoned that anyone standing on land would have to have a way to get on and off. Thus each land mass would need an even number of bridges. But in Konigsberg, each land mass had an odd number of bridges. This was why all seven bridges could not be crossed without crossing one more than once. If a bridge had been added of removed then the problem would have been solved. Euler found no path from where he could start at one point and return to that same point. The Seven Bridges of Konigsberg problem was unable to be a Eulerian circuit, otherwise known as a closed circuit.11)
Another graph discovered is called the Knight's Tour. This graph was discovered by the 9th century Indian poet Rudrata. In this graph, the knight chess piece hits every single spot on the a chess board, following the legal movements a knight can make, and does in fact return to it's starting point. Nevertheless he still discovered a graph that related to graph theory.12)13)
<html>
<img src='http://upload.wikimedia.org/wikipedia/commons/thumb/0/02/Turk-knights-tour.svg/340px-Turk-knights-tour.svg.png'></img>
</html>
Another man who helped in the advancement of Graph Theory was Arthur Cayley.<html><img src='http://www.nutquote.com/thumb/3112-Arthur_Cayley.jpg'></img></html>
In 1863 he was appointed Sadleirian professor of Pure Mathematics at Cambridge. This involved a very large decrease in income for Cayley who now had to manage on a salary only a fraction of that which he had earned as a skilled lawyer. However Cayley was very happy to have the chance to devote himself entirely to mathematics. He published over 900 papers and notes covering nearly every aspect of modern mathematics. The most important of his work is in developing the algebra of matrices, work in non-Euclidean geometry and n-dimensional geometry. Arthur Cayley developed the theory of algebraic invariance14) and his development of n-dimensional geometry has been applied in physics to the study of the space-time continuum. His work on matrices served as a foundation for quantum mechanics, which was developed by Werner Heisenberg in 1925. Cayley also suggested that euclidean and non-euclidean geometry are special types of geometry. He also united projective geometry15) and metrical geometry which is dependent on sizes of angles and lengths of lines.16)
Another great man who helped in the advancement of graph theory is James Joseph Sylvester, whom the next section will be talking about.
==== Nate Webb: James Joseph Sylvester ====
<html>
<img src='http://www-history.mcs.st-and.ac.uk/BigPictures/Sylvester_4.jpeg'></img>
</html>
Born: Sept 3, 1814 Died: March 15, 1897
“The mathematician lives long and lives young; the wings of his soul do not early drop off, nor do
his pores become clogged with the earthy particles blown from the dusty highways of vulgar life.” – James Joseph Sylvester
==History:==
James Joseph Sylvester was born in London, England to his father Abraham Joseph a common merchant. During Sylvester’s time in London he attended two separate schools, The first being a boarding school in Highgate which he attended up until 1827. After Highgate, he then attended a separate school at Islington which he attended for a year or so. At only the striking age of 14 Sylvester enrolled in the University College London and began studies the very first year that the University held students. However shortly into his studies he was released from the University due to Sylvester threatening a fellow student with a knife. Sylvester’s family had him continue his education at the Royal Institution in Liverpool.
1831 Sylvester enrolled into yet another school, this time St John’s College in Cambridge where he attended until 1837. However during 1833 to 1835 he was forced to take a leave of absence due to a severe illness. Once he regained his health Sylvester took the Mathematical Tripos Examination in 1837. Although Sylvester scored second out of the encompassing testers, he didn’t graduate do to his Jewish heritage conflicting with the Christian requirements of the University.
Immediately after Sylvester returned to the University of London and held the Chair of Natural Philosophy for three years. Although he was very active in research and made large contributions his desire to teach mathematics and not physics caused him to resign from the position in 1841. However he finally gained his degrees from Trinity College in Dublin, acquiring both a B.A and M.A.
At only the age of 27, Sylvester was appointed to the chair of mathematics in the University of Virginia in Charlottesville, USA, however yet again resigned from the position, after striking a student who had insulted him. Sylvester believing he actually killed the student fled to New York. Sylvester looked for work but was turned down from both Columbia and Harvard. As a result he boarded a ship and headed back to London in 1843.
Once back in England Sylvester took work as a secretary at the Equity Law and Life Assurance Company. As a result, Sylvester had a strong interest in studying law as well. This is where he met the other iconic figure of Graph Theory, Arthur Cayley and became lifelong friends. In 1854 Sylvester was reappointed into a mathematics chair position, this time at the Royal Military Academy in Woolwich. This is where Sylvester began or continued the bulk of his works. Initially focusing on matrix theory, he expanded his horizons.Back in 1851 he discovered the discriminant of a cubic equation and actually was the first user of the word discriminant. Sylvester received many honors and awards and retired at 55 from the Academy. After his retirement Sylvester took a lengthy break in the world of mathematics not doing any specific research or publications.
In 1878 however he returned to his roots and founded the American Journal of Mathematics which was the first mathematics journal in US history. A year prior Sylvester accepted a chair at John Hopkins University in which he had a revival in his mathematical interest and contributions. At the age of 68 Sylvester was appointed to a chair in Oxford. However in 1892, at 78 years of age his mind had become to slip and factors such as memory loss forced him to retire and he returned to London where he spent his remaining days.
==Notable Contributions to Graph Theory:==
Throughout his life, Sylvester contributed more to graph theory than anyone could ever have imagined, even himself. He truly was one of the founding fathers and backbones to this expansive topic. Sylvester submitted and published over 40 papers during his time.
Collected Papers of J J Sylvester Vol I:
http://books.google.com/books?id=THt5RLJzo94C&pg=PA200&lpg=PA200&dq=jj+sylvester+invariants+covariants&source=bl&ots=48EHuTtA56&sig=L64TNPRyEQ3Un_hTUNrgeCRaXBY&hl=en&ei=hz8GTazlA8L7lwfxhIHMBw&sa=X&oi=book_result&ct=result&resnum=3&ved=0CCIQ6AEwAg#v=onepage&q&f=false
Collected Papers of J J Sylvester Vol III:
http://books.google.com/books?id=aC7STr6FT9IC&pg=PA524&lpg=PA524&dq=james+jospeh+sylvester+syzygy&source=bl&ots=X9Zv-5fIxq&sig=DZr2_E0LW5xxV5-W7pNroh1RSQI&hl=en&ei=XE4GTdaHB8WBlAe0i8H6CA&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBoQ6AEwAA#v=onepage&q&f=false
Covariants:
<html>
<img src='http://upload.wikimedia.org/wikipedia/en/1/18/Basis.gif'></img>
</html>
The contravariant components of a vector are obtained by projecting onto the coordinate axes. The covariant components are obtained by projecting onto the normal lines to the coordinate hyperplanes.
Graph:
First Usage of the term Graph
http://www.archive.org/stream/nature15unkngoog#page/n312/mode/1up
====Justin Walrath: Sir William Rowan Hamilton====
<html>
<img src='http://www.maths.tcd.ie/pub/HistMath/People/Hamilton/Hamilton.gif'></img>
</html>
Sir William Rowan Hamilton: math genius,founding father of graph theory
This brilliant Irishman was born in Dublin in 1805. Became orphaned at a really young age (young enough that I doubt he knew his parents. His uncle was his teacher and focused on language. Hamilton was a prodigy. He could read at a young age of 3, and by 13 he could speak as many languages as his years on this planet. His math though really only started at the age of 15, and for the next 45 years this is where he focused the majority of his efforts.
He began learning math after an inspiration by having met Zerah Colburn (a yank). He then went off and read some of Sir Issac Newton's Universalls arithmetica. He taught himself the majority of the math that there was out there by reading any great theoretical math book that he could get a hand on. He even found odd errors and corrected them. This guy makes Einstein seem insignificant.
Well after having done all this, he decided at the age of 19, to go to college. 4 years later he became the Royal Astronomer of Ireland, as an undergrad. He also ended up as a Professor of Astronomy at Dublin University too.
In 1833 he began his innovative career in math by publishing a paper on how, “algebra of complex numbers appears as an algebra of ordered pairs of real numbers.” He was knighted shortly after this.
His work on Quaternions though is what really ties in to graph theory. He broke the barriers of conventional algebra and formulated (i^2=j^2=k^2=ijk=-1) a way to take the quotient of two points in space. This developed into vector analysis which continues to evolve today. Now quaternions are used primarily in 3d rotation, for computer's and robotics.
He formed something similar to Euler's circuit, but works with the vertices of the figure.
<html>
<img src='http://www.ccs3.lanl.gov/mega-math/workbk/graph/grhampath.gif'></img>
</html>
Tidbit of sources:
http://www.engr.iupui.edu/~orr/webpages/cpt120/mathbios/hamil.htm
http://www.maths.soton.ac.uk/EMIS/classics/Hamilton/ - a collection of math papers
http://mathworld.wolfram.com/Quaternion.html
http://mathworld.wolfram.com/HamiltonianPath.html
===== Theory 1 =====
The graph theory is similar to probability theory. Both original work was motivated by games of chance. The graph theory have been studied and recreated for both games and mathematics. The graph was created to representing between data and information, where at times that the pictorial representation is needed to demonstrate problems and complex issues. Graph can also be mathematical model, solve the appropriate graph theoretic problem, and then interpret the solution in terms of the original problem. Some of the application used in graph theory could be chemical molecule, singal-flow graph, maze, konigsberg bridges, four cordinate graph and so on.
Basically graph theory can be expressed in many ways but before we get into the theory, let's talk about the problems.
Assume there are four different type of problems “Eulerian Type Problem”, “Planarity type problems”, “Enumeration Problems” and “Optimization Problems” in order to under stand the theory we must understand what need to be asked first. For example, in Eulerian Type Problem, many algorithm was used in the Eulerian like Tarry's algorithm and Kruskal's and Prim's algorithms those type of problems typically come with the logical concept of algorithic thinking those things include maze and spanning tree. Planarity are include the cordinates. Enumeration include labeled tree, digraph and graphs. Finally, Optimization shows the max or the min of it's verticies.17)
Now we understand some types of the problem let's give it a shot to see what we can come up with the theory.
By starting given problem “Eulerian Type” it's theorm says:
“Theorem 1. A graph G is Eulerian if and only if it has at most one nontrivial
component and its vertices all have even degree.” 18)
“Proof. Let P be a maximal path in G. Maximal means that the path P
cannot be extended to form a larger path. Why does such a path exist? Now let
u be an endpoint of P. Since P is maximal (cannot be extended), every vertex
adjacent to u must already be in P. Since u has degree at least two, there is an
edge e extending from u to some other vertex v in P, where e is not in P. The
edge e together with the section of P from u to v completes a cycle in G.”
19)
===== Computer Science Applications of Graph Theory =====
Graph theory can also be thought of in it's applications to the computer science field.
The algorithms that are made to solve the graph theory problems are used in similar
computer science problems. Some of the graphical algorithms include finding the shortest path in
a network, finding a minimum spanning tree, finding cycles in a graph, searching for an element
in a data structure, finding graph planarity, etc.
Some computer languages that are really useful for figuring out graph theory problems include SPANTREE,
GTPL, GASP, HINT, GRASPE, IGTS, GEA, AMBIT, GIRL, FGRAAL. (http://www.ijest.info/docs/IJEST10-02-09-124.pdf) Java
is also used to solve graph theory problems like Prim's algorithm, Dijkstra's algorithm, Kruskal's algorithm, and
Tarry's algorithm.
Without graph theory, computer chips, computer networks, or large computer programs. Graph theory helps
computer researchers solve complex computer science problems by putting the problem into a graph that can be easily
studied. Graph theory and computer science complement each other. Computer science needs graph theory to say - make
a microprocessor. That same microprocessor is used to solve graph theory problems.
(http://www.cs.ucf.edu/newsletter/vol1/issue_two/graph-theory.html)
Graph theory also can be applied to websites. Web sites can be thought of as nodes and hyperlinks as edges between nodes. You can study how viruses could be spread across web pages and how to crawling and searching algorithms go through all the different web pages. A websites structure can also be modeled in a graph with the nodes representing titles, subjects, and text in a webpage and the edges showing how the nodes are connected. They can be connected as a link, a text, a title, or other ways webpages are connected to each other. An algorithm called the vertex cover algorithm is used in graphs to simulate worms on big computer networks. The graph the algorithm is tested on has vertices that are routing servers and the edges connect the servers. This test helps people find ways to stop a real virus or worm.
Graphs are also used to show a fault tolerant system. A fault tolerant system is used to make the best and most efficient computer system. The graph that is used to show a fault tolerant system is called a facility graph. This graph has nodes that are the software and hardware parts of a computer and edges that connect the software and hardware parts to show the relationships between them. Some software parts would be compilers, application programs, library routines, operation systems, and other software parts. Hardware parts would include control units, arithmetic processors, storage units, input/output equipments, and other hardware parts.
===== The Future of Graphy Theory =====
===== Open Problems =====
An open problem is simply a problem that has been presented but has not been solved. In this case the problems relate to graph theory.
=== Crossing Number of K(9, 9) ===
PROBLEM: The unsolved problem at hand is what is the crossing number of the k(9, 9) bipartite graph?
To understand this, the arrangement of the graph must be understood. This is a bipartite graph which means it has two parts and in this case the two parts are the nodes being put into two groups. Each group has 9 nodes so there are two groups of 9, hence the name K(9, 9). The two groups will now be referred to as two rows as that is how they are positioned for this graph. Each individual node in the top row must connect to each individual node on the bottom with an edge. As a note remember that these edges can be curves. Also one crossing point is simply where one of the edges intersects another edge.
Now the conjecture part is what is the minimum amount of crossing points. It is conjectured that the minimum number of crossing points is 256 but no one really knows. One crossing point is simply where one of the edges intersects another edge.
20)
<html>
<img src='http://dimacs.rutgers.edu/~hochberg/undopen/graphtheory/k44a.gif'></img>
This is a K(4, 4)graph. Note the two 'rows' and the use of straight edges and curved edges.
</html>
Zarankiewicz’ Conjecture proposed a formula for the crossing number of a bipartite graph.
<html>
<img src='http://upload.wikimedia.org/math/a/c/d/acd55dc7b7bc94a2069397e206d2254b.png'></img>
This is the formula he conjectured. This formula works but not in the way needed for this problem. It can solve for the min(m, n) but only up to, less than or equal to 8. For obvious reasons this submits a problem.
</html>
There may be question as to why any one would care about the crossing number and why some one might spend their precious time trying to figure it out when they could be doing things like scuba diving or hosting bingo at a local church. Now pretend you're working on a circuit board and you have to create the most electrical connections possible with the least amount of crossing. The reason you would want to not have them cross is because the more times you cross the more interference there will be between the connections. So in other words this crossing problem could help make computers (or anything using a circuit board) run more more efficiently.
To sum this up, nobody has yet found a definite answer for this problem. Many people believe it is 256 but no one is 100%. 21)
=== Erdős–Faber–Lovász conjecture ===
This problem is a little more of a noodle scratcher but can be presented in a more understandable way.
Conjecture 1: The union of n pairwise edge-disjoint complete graphs with n vertices is n-colorable.
Conjecture 2: Every n-vertex linear hypergraph without edges of size 1 is properly n-edge-colorable.
Note: Being colorable means that whatever color a node is the adjacent nodes must be different colors.
There is a much easier way to word this problem:
in a university department, there are k committees, each consisting of k faculty members, and that all committees meet in the same room, which has k chairs. Suppose also that at most one person belongs to the intersection of any two committees. Is it possible to assign the committee members to chairs in such a way that each member sits in the same chair for all the different committees to which he or she belongs? 22)
<html>
<img src='http://upload.wikimedia.org/wikipedia/commons/thumb/f/fa/Erd%C5%91s%E2%80%93Faber%E2%80%93Lov%C3%A1sz_conjecture.svg/240px-Erd%C5%91s%E2%80%93Faber%E2%80%93Lov%C3%A1sz_conjecture.svg.png'></img>
</html>
This is a pictorial representation of this situation. The blue cliques are committees. The nodes are the members.
If some one relaxes the problem, allowing cliques to intersect in any amount of vertices, the chromatic numbers (the minimum number of colors needed to make the graph colorable) of the resulting graphs are at most and some graphs of this type require this many colors.
Originally there was a 50$ reward at hand for an answer, now there is a 500$ reward, so have at it.
===== Conclusions =====
===== References =====
== N. Webb:==
http://www-history.mcs.st-and.ac.uk/Biographies/Sylvester.html
http://fabpedigree.com/james/mathmen.htm#Sylvester
http://www.robertnowlan.com/pdfs/Sylvester,%20James%20Joseph.pdf
===== Appendicies =====
=== Definitions ===
<HTML>
<style>
p.def {
color:#000000;
font-face:sans-serif;
font-weight:normal;
font-size:10pt;
margin:0em;
padding:0em;
padding-left:2em;
text-indent:-2em;
}
p.def:first-line {
font-face:serif;
font-weight:bold;
font-size:12pt;
text-transform:capitalize;
line-height:12pt;
}
</style>
<p class=“def”><a name=“Graph”>Graph</a>:<br />
— The collection of all points whose coordinates satisfy a given relation (as a function)<br />
— A diagram (as a series of one or more points, lines, line segments, curves, or areas) that represents the variation of a variable in comparison with that of one or more other variables<br />
— A collection of vertices and edges that join pairs of vertices<br />
Source: <a href=“http://www.merriam-webster.com/dictionary/graph”>Merriam Webster</a>
</p>
<p class=“def”><a name=“Theory”>Theory</a>:<br />
— The analysis of a set of facts in their relation to one another<br />
— Abstract thought : speculation<br />
— The general or abstract principles of a body of fact, a science, or an art ‹music theory›<br />
— Belief, policy, or procedure proposed or followed as the basis of action ‹her method is based on the theory that all children want to learn›<br />
— An ideal or hypothetical set of facts, principles, or circumstances — often used in the phrase in theory ‹in theory, we have always advocated freedom for all›<br />
— A plausible or scientifically acceptable general principle or body of principles offered to explain phenomena ‹the wave theory of light›<br />
— A hypothesis assumed for the sake of argument or investigation <br />
— An unproved assumption
— A body of theorems presenting a concise systematic view of a subject ‹theory of equations›
<br />
Source: <a href=“http://www.merriam-webster.com/dictionary/theory”>Merriam Webster</a>
</p></HTML>
4)
inventory or record: unparalleled in the lexicon of human relations.
5)
The act of acquiring
6)
The study of speech sounds in language or a language with reference to their distribution and patterning and to tacit rules governing pronunciation
8)
Source: http://www.open-graphtheory.org/
9)
James Joseph Sylvester(1878), “On an Application of the New Atomic Theory to the Graphical Representation of the Invariants and Covariants of Binary Quantics with Three Appendices”; American Journal of Mathematics, Vol. 1, pp.64-128
10)
The Icfai University Journal of Computer Sciences, Vol III, No. 2, 2009
12)
source: “A History of Chess” by H.J.R. Murray
13)
site of interactive knight's tour, although it is not complete: http://www.borderschess.org/KnightTour.htm
14)
Algebraic invariance refers to combinations of coefficients from certain functions that remain constant when the coordinate system in which they are expressed is translated, or rotated. An example of this kind of invariance is seen in the behavior of the conic sections.(http://science.jrank.org/pages/3665/Invariant-Algebraic-invariance.html
18)
-Introduction to Graph Theory
Allen Dickson, Oct 2006, pg5
19)
-Introduction to Graph Theory, Allen Dickson, Oct 2006, pg5
21)
Source: http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBMQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.70.1784%26rep%3Drep1%26type%3Dpdf&rct=j&q=K(9%2C%209)%20crossing%20pdf&ei=W2EETbSrC4aKlwfe8tH4Cg&usg=AFQjCNG45Lpioix9Qi1QCd4yIH9d8YZHfg&sig2=UBYE1W9LtfTxM8z1OPlKBg&cad=rja
notes/discrete/discrete2010.txt · Last modified: 2012/08/27 20:11 by wedge