The Konigsberg Bridge Problem Engineering Essay

The earliest paper on graph theory seems to be by Leonard Euler,Solutio problematic ad situs pertinentis,Commentarii Academetarii Scientiarum Imperialist Petropolitanae 8 (1736),128-140.Euler discusses whether or not it is possible to scroll around Konigsberg(later called the Pregolya exactly once. Euler gave the conditions which are necessary to permit such a stroll. Thomas Pennyngton Kirkman (1856) and Wiliam Roman Hamilton (1856) studied trips which certain sites exactly once.

History of Euler paths and cycles

An ‘Eulerian path’ is a path in a graph which visits each edge exactly once in the theory graph .so, in the same way, an ‘Eulerian circuit’ is an Eulerian path which starts and ends on the same vertex. They were first discussing by Leohard Eular while solving the famous Seven Bridges of Konigsberg problem in 1736. Mathematically the problem can be stated like this:

Given the graph on the right, is it possible to construct a path (or a cycle for example, a path starting and ending on the same vertex) which visits each edge exactly once

Graphs which allow the manufacture of so called ‘Eulerian cycles’ are called ‘Eulerian graphs’. Euler observed that a necessary condition for the existence of Eulerian cycles is that all vertices in the graph have an even degree, and that for an Eulerian path either all, or all but two (i.e., the two endpoint) vertices have an even degree; this means the Konigsberg graph is ”not” Eulerian. Carl Heierholzer published the first complete characterization of Eulerian graphs in 1873, by proving that in fact the Eulerian graphs are exactly the graphs which are connected and where every vertex has an even degree.

Example using euler in our daily life is using in the teaching for set theory that widely use in the schools. Another example is to visualizing file system organization.it will allows files to appear in more than one directory in a computers file system.

The history of the Konigsberg

Leonhard Euler (1707-1783) is considered to have been the father of graph theory. His paper in 1736 on the seven bridges of Konigsberg is considered to have been the foundational paper in the subject.

Konigsberg is a town, founded in 1256, that was originally in Prussia. After a stormy history, the town became part of Soviet Union and was renames Kaliningrad in 1946. In any event, during Euler’s time the town had seven bridges (named Kramer, Schmiede, Holz, Hohe, Honig, Kottel, and Grunespanning) spanning the Pregel River. Figure 8.1 gives a simplified picture of how the bridges were originally configured (two of the bridges were later destroyed during World War II, and two other demolished by the Russians.

Figure 8.1: the seven bridge of Konigsberg

History of Hamiltonian:

Hamiltonian is introduced by Sir William Rowan Hamilton at 1857. He made a game called “around the world” and the originally in form of solid called dodecahedron. It has 20corners/for each corner, it called as town. The problem started when the travel started from one city to another city along the edge to arrive at city by only once arrived at one city. This is how the Hamiltonian is appearing. There is example of using Hamiltonian in life such as no-complete, n-cube and traveling salesman problem.

Two types of Hamiltonian are Hamiltonian path and Hamiltonian cycle

Introduction

Path

Path is the sequences of alternating vertices and edges. Which begin from a vertex and ended with a vertex. Each vertex is preceded and followed by its endpoints.

Simple path

Simple path is a path such that all its vertices and edges are distinct.

Below is a graph that gives differences between path and simple path.

Path 1: v,b,x,h,z(simple path)

Path 2 : u,c, w,f,y,g,x,e,d,v(path)

Example of path is the way of bus direction from one destination to another destination. In other hand, simple path is a path that no complicated for example the direction from faculty of FTSM to faculty of FUU.

Cycle

Circle is a circular sequence of alternating vertices and edges. Each edges is preceded and followed by its endpoints.

Simple cycle

Simple cycle is a cycle such that all its vertices and edges are distinct.

Cycle: u,c,w,e,x,g,f,w,d,v,a,u

Simple cycle:v,b,x,g,y,f,w,c,u,a,v,

Example of using cycle in life is when we travel to another place then come back to our home with using the different ways. Another example in ukm is the bus ways for example bus zone 2 will make a circle to take student and will come back to the initial location where the busy will take a rest.

For simple cycle, we always see in sport, such as the court for athletes running especially in event of 400 * 100 meters. Then, we also can see in power plant program that is simple cycle power plant (pp) program. It gives much benefit such as optimized design, reduced engineering costs, short lead times, increase availability and fast startups also high operational flexibility.

Connected Graph

Connected graph is a graph that there exists a path between all pairs of vertices.

If a graph is a directed graph, there exist a path between vertexes to each other that in the graph, is called as strongly connected graph.

Figure 1: connected graph

Unconnected graph.

Disconnected graph: There are at least two vertices not connected by a path.

The examples of disconnected graphs:

Figure 2: connected digraph

Example of using connected graph is use in building. For example Menara Berkembar Petronas, there is a bridge to connect the two buildings. Another example is the bridge of Pulau Pinang. First use to connect the island and peninsular Malaysia.

Example of disconnected graph is other hand than connected graph. For example the building of one employee is not connected by bridge with another employee. Next, the Island of Sipadan is not connected by a bridge with Borneo land.

An Euler path in a graph is a path which traverses each edge of the graph exactly once. An Euler cycle is an Euler path which is contains cycle. If there are no loop graphs, without isolated vertices, the continuation of an Euler path implies the connected of the graph, since traversing every edge of such a graph requires visiting each vertex at least once.

But, when the connected graph has an Euler path, one can be constructed by applying Fleury’s algorithm. A connected graph has an Euler path if it has exactly zero or two vertices of odd degree. If every vertex has even degree, the graph has an Euler cycle.

The definition and properties of Euler paths, cycles and graphs are valid for multigraph as well.

The graph above has an Euler cycle. It is because all of its vertices are of even degree.

The graph above has a Eular path which is not a cycle. It has two vertices of odd degree.

The seven bridge of Konigsberg

In Konigsberg, Germany, a river ran through the city such that in its centre was an island, and after passing the island, the river broke into two parts. Seven bridges were built, so that the people of the city could get from one part to another part. A crude map of the centre of Konigsberg might look like this:

The people wondered whether or not, one could walk around the city in a way that would involve crossing each bridge exactly once.

Degree of vertex

Term of degree of vertex in graph theory is the number of edges which connected to a vertex. Degree of vertex also known as local degree. The list of all degree of vertex is called as degree sequences. One way to find the number of vertex is count the number of degree for each vertex that endpoint. An easy way is draw a circle around the vertex and count the number of edges that cross the circle. The degree of vertex can be add or even. if the degree of vertex is even, it is known as degree vertex and the other hand, if the degree of vertex is odd, the vertex is called an odd vertex. To find out the degree of graph is by choose the largest degree of vertex. Example graph with have odd and even vertex:

Example degree of vertex is application of roundabout because there are many roads that connected. Either the value is odd or even. The road can be representing as edges and the roundabout as the vertex. Another example is the number of use degree of vertex in electrical pole such as the number of wire connected to the one pole.

Hamiltonian path:

Hamiltonian path is also called as traceable path. Hamiltonian path is a path that visits each vertex exactly one and not repeated for each vertex in a graph. Hamiltonian graph us use to solve a problem when find a path that only visited each vertex only one in a graph.

Figure:Hamiltonian path graph

Hamiltonian cycle:

Hamiltonian cycle is a cycle that goes through the entire city (vertex) only once for a graph. It cannot be repeated to reach a city for a one cycle except the starting and the ended city.

Example of Hamiltonian cycle:

A Hamiltonian Cycle on the Dodecaheron

Results of research and real world examples

Graphs can be used to represent oil flow in pipes, traffic flow on motorways, transport of pollution by rivers, groundwater movement of contamination, biochemical pathways, and the underground network.

The example of Euler path:

There are many useful applications to Euler circuits and paths. Networks can be used to solve many difficult problems, like the Konigsberg Bridge problem. The can also used by mail carrier who wants to have a route where they do not retrace any of their previous steps. Other than that, Euler circuits and paths are also useful to painters, garbage collector, airplanes pilots and world navigators. Below are the examples of how Euler circuit and paths are useful in the real world.

The maps that pilots use are called route maps. The route maps show the paths of the airplanes from one destination to another. Here is an example of actual route map. The centre for all travel with this airline is in Denver, Colorado. From there, we can travel to some of the major cities in the surrounding states.

 

The Navigation below is a trip to see all different regions of the world.

The above regions of the world have all been given different colors. Each region also has been given marked with a node or vertex and some (but not all) of the regions are connected with arcs.

Conclusions and recommendations

As the conclusion towards this particular project, the study of graphs and their properties is a classical subject in most computer science department around the world. Graph Theory can be further exploited by object-oriented software engineering, taking advantage of recent research in various fields. Other than that, Graph theory is one of the top reasons to learn linear Algebra. So, all graphs (included directed, weighted, and multi-graphs) can be represented intuitive by adjency matrices, and matrix operations often end up being meaningful in terms of graph they represent. Seeing the connection between a graph and its matrix helps to understand both of them, and being able to switch back and forth between mental models is often useful.

For example, a person in many fields of modeling, are mostly easily thought of the weight graphs, and are most easily manipulated as matrices. By learning the entire graph, the student can get many benefits by it especially the computer science student. So, our recommendation towards this topic in order to make the student easy to learn and improve themselves are for example, ask the student to make a lot of exercise. Other than that, ask them to make an assignment about this topic. So that the student can search many information based on this topic and become more familiar and understand about graph theory