Class Notes (809,452)
CMPT 225 (60)
John Edgar (28)
Lecture

# CMPT 225 Week 11 Lecture 1

3 Pages
80 Views

School
Simon Fraser University
Department
Computing Science
Course
CMPT 225
Professor
John Edgar
Semester
Summer

Description
Graphs Graph theory considered to be born with Euler, solved Konigsberg bridge problem Town has 7 bridges in center. Was it possible to walk across each bridge just once and return to where they started Euler proved it was impossible, proof involved representing problem as a graph, thoroughly ruining everyone's fun Multigraph - two vertices can have more than one edge between them Graphs very useful, can be used to represent many many different problems Graph consists of two sets: V: set of vertices / nodes E: set of edges that connect the vertices |V| = size of V, |E| size of E Two vertices may be connected by a path. Sequence of edges that starts at one vertex, ends at another. Simple does not pass through same vertex more than once Cycle is path that ends at same vertex. Add complexity, may not be allowed in some systems. If graph has V vertices, how many edges? If every vertex connected to every other vertex, count each direction as 2 edges: v^2 - v If tree: v - 1 (tree is specialized graph) Min number of edges: 0 Connected graph: every pair of vertices has a path between them (tree) Complete: every pair of vertices has an edge between them (not path, all directly connected) Graph cannot have multiple edges between same vertices Graph cannot have self edges, edge from and to the same vertex Disconnected graphs can exist too Directed graph (digraph): each edge has direction, called a directed edge, directed edge can only be traveled in one direction. Can have vertices with two edges between them, if going different directions. Weighted graph: each edge assigned weight, edges' weights are displayed, represent cost to travel that edge. Could be distance. Cost depends on underlying problem. Used for wayfinding! Can combo: directed weighted graph. Graph operations: Create empty Test if empty Determine number vertices Number edges Does edge exist between x and y ? Insert vertex Delete a vertex, associated edges Delete an edge Return vertex with given key Not really anything interesting, but you need to have these. Two common implementations: Both need list of all vertices V (other ways if you don't really have vertices) - example: vertices are just 0 through n, just care about edges - hash tables? Implementation differs in recording of edges Adjacency matrices - fast lookup of individual edges - wasted space if sparse (few edges, trees as example) Adjacency Lists - more space efficient (only maintain the space that is needed) - can efficiently find all neighbours of vertex - not as good for individual edges AM: Edges are recorded in a |V| * |V| matrix 1 when
More Less

Related notes for CMPT 225

OR

Don't have an account?

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.