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.


History of Graph Theory

No description

Jazel Nithz Cortes

on 23 March 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of History of Graph Theory

Thank you!
The origin of graph theory can be traced back to Euler's work on the Konigsberg bridges problem (1735), which subsequently led to the concept of an Eulerian graph. The study of cycles on polyhedra by the Thomas P. Kirkman (1806 - 95) and William R. Hamilton (1805-65) led to the concept of a Hamiltonian graph.

The concept of a tree, a connected graph without cycles, appeared implicitly in the work of Gustav Kirchhoff (1824-87), who employed graph-theoretical ideas in the calculation of currents in electrical networks or circuits. Later, Arthur Cayley (1821-95), James J. Sylvester(1806-97), George Polya(1887-1985), and others use 'tree' to enumerate chemical molecules.

The study of planar graphs originated in two recreational problems involving the complete graph K5 and the complete bipartite graph K3,3. These graphs proved to be planarity, as was subsequently demonstrated by Kuratowski.
History of Graph Theory

The ‘Königsberg bridge’ problem originated in the city of Königsberg, formerly in
Germany but, now known as Kaliningrad and part of Russia, located on the river Preger.
The city had seven bridges, which connected two islands with the main-land via seven
bridges. People staying there always wondered whether was there any way to walk over
all the bridges once and only once. The below picture is the map of Königsberg during
Euler's time showing the actual layout of the seven bridges, highlighting the river Preger
and the bridges.

In, 1736 Euler came out with the solution in terms of graph theory. He proved that it was
not possible to walk through the seven bridges exactly one time. In coming to this
conclusion, Euler formulated the problem in terms of graph theory. He abstracted the
case of Königsberg by eliminating all unnecessary features. He drew a picture consisting
of “dots” that represented the landmasses and the line-segments representing the bridges
that connected those land masses. The resulting picture might have looked somewhat
similar to the figure shown below
This simplifies the problem to great extent. Now, the problem can be merely seen as the
way of tracing the graph with a pencil without actually lifting it. One can try it in all
possible ways, but you will soon figure out, it is not possible. But Euler not only proved
that its not possible, but also explained why it is not and what should be the characteristic
of the graphs, so that its edge could be traversed exactly once. He came out with the then
new concept of degree of nodes. The Degree of Node can be defined as the number of
edges touching a given node. Euler proposed that any given graph can be traversed with
each edge traversed exactly once if and only if it had, zero or exactly two nodes with odd
degrees. The graph following this condition is called, Eulerian circuit or path. We can
easily infer this theorem. Exactly two nodes are, (and must be) starting and end of your
trip. If it has even nodes than we can easily come and leave the node without repeating
the edge twice or more.
In actual case of seven bridges of Königsberg, once the situation was presented in terms
of graph, the case was simplified as the graph had just 4 nodes, with each node having
odd degree. So, Euler concluded that these bridges cannot be traversed exactly once.
Using this theorem, we can create and solve number of problems. Suppose now, we want
to make the graph created from bridges of Königsberg, a Euler’s circuit. Now, as per
Euler’s theorem we need to introduce a path to make the degree of two nodes even. And
other two nodes can be of odd degree out of which one has to be starting and other
another the endpoint. Suppose we want to start our journey from blue node and end at the
yellow node. So, the two nodes can have odd edges.
What is a graph theory ?
the mathematical theory of the properties and applications of graphs.
Leonhard Paul Euler (1707- 1783) was a pioneering Swiss mathematician, who spent
most of his life in Russia and Germany. Euler (pronounced as OILER) solved the first
problem using graph theory and thereby led the foundation of very vast and important
field of graph theory. He created first graph to simulate a real time place and situation to
solve a problem which was then considered one of the toughest problems.

In mathematics and computer science, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

A "graph" in this context is made up of "vertices" or "nodes" and lines called edges that connect them. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another
Undirected graph
Examples :
An undirected graph is a graph in which the nodes are connected by undirected arcs . An undirected arc is an edge that has no arrow. Both ends of an undirected arc are equivalent--there is no head or tail. Therefore, we represent an edge in an undirected graph as a set rather than an ordered pair.

An undirected graph is an ordered pair with the following properties:

1.The first component, , is a finite, non-empty set. The elements of are called the vertices of G.

2. The second component, , is a finite set of sets. Each element of is a set that is comprised of exactly two (distinct) vertices. The elements of are called the edges of G.
Directed Graph
A directed graph or digraph is a pair G = (V,A) (sometimes G = (V,E)) of:[1]

a set V, whose elements are called vertices or nodes,
a set A of ordered pairs of vertices, called arcs, directed edges, or arrows (and sometimes simply edges with the corresponding set named E instead of A).

It differs from an ordinary or undirected graph, in that the latter is defined in terms of unordered pairs of vertices, which are usually called edges.

Sometimes a digraph is called a simple digraph to distinguish it from a directed multigraph, in which the arcs constitute a multiset, rather than a set, of ordered pairs of vertices. Also, in a simple digraph loops are disallowed. (A loop is an arc that pairs a vertex to itself.) On the other hand, some texts allow loops, multiple arcs, or both in a digraph
Mixed Graph
A mixed graph (G) is a graph in which some edges may be directed and some may be undirected. It is written as an ordered triple G = (V, E, A) with V, E, and A. Directed and undirected graphs are special cases.
Multi Graph
A loop is an edge (directed or undirected) which starts and ends on the same vertex; these may be permitted or not permitted according to the application. In this context, an edge with two different ends is called a link.
As opposed to a multigraph, a simple graph is an undirected graph that has no loops and no more than one edge between any two different vertices. In a simple graph the edges of the graph form a set (rather than a multiset) and each edge is a pair of distinct vertices. In a simple graph with n vertices every vertex has a degree that is less than n (the converse, however, is not true - there exist non-simple graphs with n vertices in which every vertex has a degree smaller than n).
Simple Graph
Submitted by :
Jazel nithz cortes

Source : Andy Jones
Full transcript