Scribd Logo
Upload

Welcome to Scribd!

  • 45 views

    Konigsberg Bridge Problem

    Uploaded by

    katba dhar
    The Konigsberg Bridge Problem asked if it was possible to take a walk through the city of Konigsberg, crossing each of its seven bridges exactly once. Euler converted the problem into a graph with four vertices connected by seven edges. He determined that a graph can have an Eulerian trail connecting all edges only if each vertex has an even degree, but the Konigsberg graph had four vertices of odd degree. Therefore, it was impossible to complete the walk through Konigsberg as described.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Konigsberg Bridge Problem

    Uploaded by

    katba dhar
    45 views10 pages
    The Konigsberg Bridge Problem asked if it was possible to take a walk through the city of Konigsberg, crossing each of its seven bridges exactly once. Euler converted the problem into a graph with four vertices connected by seven edges. He determined that a graph can have an Eulerian trail connecting all edges only if each vertex has an even degree, but the Konigsberg graph had four vertices of odd degree. Therefore, it was impossible to complete the walk through Konigsberg as described.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The Konigsberg Bridge Problem asked if it was possible to take a walk through the city of Konigsberg, crossing each of its seven bridges exactly once. Euler converted the problem into a graph with four vertices connected by seven edges. He determined that a graph can have an Eulerian trail connecting all edges only if each vertex has an even degree, but the Konigsberg graph had four vertices of odd degree. Therefore, it was impossible to complete the walk through Konigsberg as described.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    45 views10 pages

    Konigsberg Bridge Problem

    Uploaded by

    katba dhar
    The Konigsberg Bridge Problem asked if it was possible to take a walk through the city of Konigsberg, crossing each of its seven bridges exactly once. Euler converted the problem into a graph with four vertices connected by seven edges. He determined that a graph can have an Eulerian trail connecting all edges only if each vertex has an even degree, but the Konigsberg graph had four vertices of odd degree. Therefore, it was impossible to complete the walk through Konigsberg as described.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 10

    Konigsberg Bridge Problem

    Name: Pynshngain Dhar


    Roll NO:22PhDMA01
    Supervisor: Dr. John Paul Jala Kharbhih
    Course : SPS-C-500
    Department of Mathematics
    North Eastern Hill University
    Shillong-793022,India
    OUTLINES:

    • Introduction
    • Preliminaries
    • Konigsberg Bridge Problem
    • References
    INTRODUCTION:
    • Konigsberg was founded in1255 and was the capital of German East
    Prussia.

    • The Prussian Royal Castle was located in Konigsberg but it was destroyed
    during World War II , as was much of the city.

    • Because of the outcome of the war , it was decided at the Post


    Conference in 1945 that the region located between Poland and
    Lithuania , containing the city of Konigsberg should be part of Russia.

    • In 1946 , Konigsberg was renamed to Kaliningrad after Mikhail Kalinin ,


    the formal leader of the soviet Union during 1919-1946.
    • The River Pregel flowed through Konigsberg ,
    separating it to four land areas .
    • Seven bridges were built over the river that
    allowed the citizens of Konigsberg to travel
    between these land areas.
    • A map of Konigsberg , showing four land areas
    ( labelled A,B,C,D ), the location of the river ,
    and the seven bridges at that time are given
    below : The city of Konigsberg
    The story goes that the citizens enjoyed going
    for walks near the river .Some citizens
    wondered whether it was possible to go for a
    walk in Konigsberg and pass over each bridges
    exactly once. This became known as the
    Konigsberg Bridge Problem.
    Evidently , this problem remain unsolved for sometime and became well known
    throughout the region. This problem eventually came to the attention of Euler .
    While trying to solve this problem he discovered new branch of mathematics
    that had to do with some type of geometry that did not quiet exist yet what he
    called The Geometry of Position which is now known as Graph Theory.
    He converted this map of Konigsberg bridge problem to Graph as follows:

    Each Land A,B,C,D are called vertex


    And the bridge between land areas are
    called edge.
    Preliminary:
    Definition:
    A graph is a pair G=(V,E) , where V is the set whose elements are called vertices
    and E is the set of paired vertices , whose element are called edges.
    • The number of elements in set V is called order of graph G denoted by o(G)
    • The number of element in set E is called size of graph G denoted by S(G).

    In this graph, o(G)=4 and S(G)=7


    We see that there is an edge ( bridge ) from A
    to B, we say AB is an edge and vertex A and B
    are adjacent .
    We also say that edge AB is incident on A (or
    B).
    • Degree of Vertex:
    The number of edges incident with the vertex A (says) is called degree of vertex A.
    In the given graph,
    Degree of A=5
    Degree of B=3 ( same for vertex C, D)
    • Walk:
    A walk can be defined as sequence of edges and
    vertices of a graph .

    • Trail:
    A walk in which no edge is traversed more than one is
    called a trail.

    • Eulerian Trail:
    A Trail that contain every edge of G is called an
    Eulerian Trail.
    Konigsberg Bridge Problem:
    Is it possible to go for a walk in Konigsberg and pass over each bridge exactly once?
    After converting this problem to graph ,
    The problem is equivalent or same as asking “Does there exist an Eulerian Trail in
    Konigsberg graph? “

    The answer is NO.


    Suppose we assume , that the graph has an Eulerian Trail
    Let us consider any vertex says v which is neither the
    initial and the terminal vertex . Then each time v is
    entered it is also exit.
    So degree of this vertex v is always even .
    But we have seen that each vertex of this Konigsberg
    graph has odd degree.
    Hence we conclude that this graph has no Eulerian Trail .
    Thus, it is not possible to go for a walk and pass over
    each bridge exactly once.
    References:
     Introduction to Graph Theory , D.B West.
     Graph Theory , R. Diestel.
     Introduction to Graph Theory , R.J. Wilson .
     A First Course in Graph Theory ,Gary Chartrand and Ping Zhang.
    THANK YOU

    You might also like