Originated in approx. 1736 when Leonhard Euler asked the Seven
Bridges of Knigsberg question about the river Pregel in the city
of Knigsberg where he lived in Prussia. The town had seven
bridges crossing the river. He asked:
“Is it possible to walk a route that crosses all seven
bridges exactly once and ends up at the same starting
He solved the problem by representing each section of land by a
node and drawing lines or edges between them for each bridge.
He then proved that in general, a walk that traverses each edge
exactly once and returns to the starting point can only exist if
each node has a particular property.
Q. What is this property?
A. each node has an even number of edges.
1 Graph Theory Deﬁnitions
▯ A graph G = (V;E) consists of a set of vertices (or nodes)
V and a set of edges E.
▯ We deﬁne n = jV j, the number of nodes, and m = jEj,
the number of edges.
▯ A graph can be directed or undirected.
Q. How are dcrected and undirected graphs related?d
A. An undirehted graph can be converted to a directed graph by
replacing each edge with a pair of edges in opposing directions.
▯ In a weighted graph each edge e 2 E is assigned a real
number w(e) called its weight.
▯ An undirected graph is said to be connected if there is a
path between every two vertices.
2 ▯ A directed graph is said to be strongly connected if, for any
two vertices u;v, there is a directed path from u to v.
d t 3
d Applications of Graphs
▯ Chip Design
▯ Network Analysis, such as transportation ﬂow, cellular cov-
erage, electrical current etc.
▯ Flow Charts
▯ Explanatory schematics
▯ Bioinformatics - data clustering
4 The Art Gallery Problem
This problem belongs to the ﬁeld of computational geometry and
is a visibility problem however it originates from the real world
problem of determining how many guards are needed to watch
over an entire gallery.
▯ Let the ﬂoor map of a gallery be represented by a simple
polygon (no crossing edges, no holes).
▯ Let each guard be represented by a point in the polygon.
▯ A set of points S is said to guard the polygon if every point
p in the polygon can be “seen” by some s 2 S.
▯ A point s 2 S can see another point p iff the line segment
sp does not leave the polygon.
The grey regions cannot be “seen” by s.
Q. Where should one add s 2 S so that the entire polygon is
5 An example.
Here is the actual ﬂoor plan for the Barbara Krakow Art Gallery
6 Here is a simpliﬁed version of the ﬂoor plan which is a simple