Class Notes
(809,452)

Canada
(493,718)

Simon Fraser University
(12,071)

Computing Science
(220)

CMPT 225
(60)

John Edgar
(28)

Lecture

# CMPT 225 Week 11 Lecture 1

Unlock Document

Simon Fraser University

Computing Science

CMPT 225

John Edgar

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