Introduction To Graph Theory

The Seven Bridges of Königsberg

The Seven Bridges of Königsberg is a historically notable problem in mathematics. It goes like this.

Source:https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg
  1. Accessing any bridge without crossing to its other end

What does this have anything to do with Graph Theory?

Well, Euler observed that…

1. Choice of land route within each land mass is irrelevant.

This implied that the problem needn’t be viewed photographically or in a map, but can be expressed in an abstract form.

2. If one enters by a bridge, one must leave by a bridge.

Euler observed that except at the endpoints of the walk, when one enters a vertex by a bridge, one must exit the vertex by a bridge. That is the number of times one enters a non-terminal vertex equals the number of times one leaves it. Now, if every bridge can be walked upon just once, then for each vertex ( the non-terminal ones) the number of bridges touching that land mass must be even, that is the degree of each node should be even(half of them towards,half away from the land)

Some defintions:

A Graph is an ordered triplet G=(V(G), E(G), ψ(G)) consisting of non-empty set V(G) of vertices, a set E(G) of edges and an incidence function ψ(G) that associates with each edge of G with an un-ordered pair of vertices.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Enfa Rose George

Enfa Rose George

199 Followers

Sipping my coffee in a warm cafe, a book in hand, waiting for my DL model to finish training