Class Notes (836,147)
CSCA67H3 (56)
Lecture 3

# Week 3 Lecture

14 Pages
327 Views

Department
Computer Science
Course
CSCA67H3
Professor
Richard Pancer
Semester
Fall

Description
Graph Theory Originated in approx. 1736 when Leonhard Euler asked the Seven Bridges of Knigsberg question about the river Pregel in the city of Knigsberg 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
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.