Class Notes (836,147)
Canada (509,656)
CSCA67H3 (56)
Lecture 3

Week 3 Lecture

14 Pages
Unlock Document

Computer Science
Richard Pancer

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 Definitions ▯ A graph G = (V;E) consists of a set of vertices (or nodes) V and a set of edges E. ▯ We define 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 flow, cellular cov- erage, electrical current etc. ▯ Flow Charts ▯ Explanatory schematics ▯ Bioinformatics - data clustering ▯ etc. 4 The Art Gallery Problem This problem belongs to the field 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 floor 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 floor plan for the Barbara Krakow Art Gallery in Boston. 6 Here is a simplified version of the floor plan which is a simple polygon.
More Less

Related notes for CSCA67H3

Log In


Join OneClass

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

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
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.

Add your courses

Get notes from the top students in your class.