Konigsberg Bridge Problem_Graph Theory.pptx

Konigsberg Bridge Problem_Graph Theory.pptx

1. ESSENTIALS OF PROBLEM SOLVING Konigsberg Bridge Problem The Konigsberg is the name of the German city, but this city is now in Russia. In the image, we can see the inner city of Konigsberg with the river Pregel . There are a total of four land areas in which this river Pregel is divided, i.e., A, B, C and D. There are total 7 bridges to travel from one part of the city to another part of the city.

2. ESSENTIALS OF PROBLEM SOLVING Konigsberg Bridge Problem: The Konigsberg Bridge contains the following problem which says: Is it possible for anyone to cross each of the seven bridges only a single time and come back to the beginning point without swimming across the river if we begin this process from any of the four land areas that are A, B, C, and D?.

3. ESSENTIALS OF PROBLEM SOLVING A walk is a sequence of vertices so that there is an edge between consecutive vertices. A walk can repeat vertices and edges. A trail is a walk with no repeated edges. A trail can repeat vertices but not edges A path is a trail with no repeated vertex (or edges). A path on n vertices is denoted Pn . A closed walk is a walk that starts and ends at the same vertex. A circuit is a closed trail; that is, a trail that starts and ends at the same vertex with no repeated edges though vertices may be repeated. A cycle is a closed path; that is, a path that starts and ends at the same vertex. Thus cycles cannot repeat edges or vertices. Note: we do not consider the starting and ending vertex as being repeated since each vertex is entered and exited exactly once. A cycle on n vertices is denoted Cn.

4. ESSENTIALS OF PROBLEM SOLVING Example: Given the graph below, find a trail (that is not a path) from a to c, a path from a to c, a circuit (that is not a cycle) starting at b, and a cycle starting at b. Trail from a to c A trail is a walk with no repeated edges. A trail can repeat vertices but not edges

5. ESSENTIALS OF PROBLEM SOLVING Example: Given the graph below, find a trail (that is not a path) from a to c, a path from a to c, a circuit (that is not a cycle) starting at b, and a cycle starting at b. Path from a to c A path is a trail with no repeated vertex (or edges).

6. ESSENTIALS OF PROBLEM SOLVING Example: Given the graph below, find a trail (that is not a path) from a to c, a path from a to c, a circuit (that is not a cycle) starting at b, and a cycle starting at b. Circuit starting at b A circuit is a closed trail; that is, a trail that starts and ends at the same vertex with no repeated edges though vertices may be repeated.

7. ESSENTIALS OF PROBLEM SOLVING Example: Given the graph below, find a trail (that is not a path) from a to c, a path from a to c, a circuit (that is not a cycle) starting at b, and a cycle starting at b. Cycle starting at b A cycle is a closed path; that is, a path that starts and ends at the same vertex. Thus cycles cannot repeat edges or vertices.

8. ESSENTIALS OF PROBLEM SOLVING Note that the trail from a to c is not a path since the vertex f is repeated The circuit starting at b is not a cycle since the vertex d is repeated. Moreover, the examples given above are not the only solutions but rather an option among many possible solutions.