[Fundamental] The 7 Bridges Problem

Overview

In East Prussia(普鲁士), people try to walk all 7 bridges w/o crossing a bridge twice.

Leonhard Euler (pronounced “oiler”) – Swiss

Euler path

An Euler path, also called an Eulerian trail, is a walk on the graph edges of a graph which uses each graph edge in the original graph exactly once.

Degree

Node degree of a vertex: the number of edges incident with it.

Euler Theorem

A graph contains an euler path iffeither of the following cases hold:

1. All except for two nodes have even degrees – the 2 odd-degree nodes must be start and end points
2. all nodes have even degrees.

Application

networks, distributed systems, coding theory