false

Class Notes
(836,147)

Canada
(509,656)

University of Toronto Scarborough
(31,491)

Computer Science
(312)

CSCA67H3
(56)

Richard Pancer
(3)

Lecture 3

Unlock Document

Computer Science

CSCA67H3

Richard Pancer

Fall

Description

Graph Theory
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
point?”
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.
D
n r
r c
Q. How are dcrected and undirected graphs related?d
d G
G p
p h
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.
o N
n o
c c
e n
d c
e
d
S N
o o
g s
y o
o g
n y
c o
e n
d t 3
d Applications of Graphs
▯ WWW-google!
▯ Scheduling
▯ Chip Design
▯ Network Analysis, such as transportation ﬂow, cellular cov-
erage, electrical current etc.
▯ Flow Charts
▯ Explanatory schematics
▯ Bioinformatics - data clustering
▯ etc.
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.
Mathematical Description.
▯ 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.
s
The grey regions cannot be “seen” by s.
Q. Where should one add s 2 S so that the entire polygon is
guarded?
A.
5 An example.
Here is the actual ﬂoor plan for the Barbara Krakow Art Gallery
in Boston.
6 Here is a simpliﬁed version of the ﬂoor plan which is a simple
polygon.

More
Less
Related notes for CSCA67H3

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.