Class Notes (1,100,000)
CA (650,000)
UW (20,000)
CS (1,000)
CS341 (20)
Lecture

# CS341 Lecture Notes - Induced Subgraph, Adjacency Matrix, Tree Traversal

Department
Computer Science
Course Code
CS341
Professor
Forbes Burkowski

This preview shows pages 1-3. to view the full 20 pages of the document. 1
Graph Algorithms
Graphs and their representation:
A graph G= (V, E)
Vis a set of vertices V= {vi|i = 1, 2, …, n}
Eis a set of edges E= {ej|j = 1, 2, …, m}that
connect the vertices.
Edge emay be represented by the pair (u,v)
where uand vare the vertices being connected
by e.
Depending on the problem, the pair may be
ordered or unordered.
Graph Algorithms
Many problems can be represented as
graphs:
Traveling Salesperson Problem
Airline flights
Friends who know each other
Moves in a game (each node = the state of the
board or game, each edge = a valid move
between different positions).

Only pages 1-3 are available for preview. Some parts have been intentionally blurred. 2
Directed and Undirected Graphs
An undirected graph, G= <V,E>is the pair:
V= set of distinct vertices
E= set of edges;
For example:
V= {t, u, v, w, x, y, z}
E= {{u, v}, {u, w}, {v, w}, {v, y}, {x, z}}
Directed and Undirected Graphs
Similar to an undirected graph except Eis a set
of ordered pairs.
For example:
E= {<a, b>, <a, c>, <c, b>, <b, e>, <e, b>}

Only pages 1-3 are available for preview. Some parts have been intentionally blurred. 3
More Definitions
Weighted graphs:
A weighted graph has a value assigned to each of
its edges.
More formally, there is a weight function w: E R.
R= real numbers.
We denote this as either w(e)with ein Eor w(u, v)with
uand vrepresenting the vertices of the edge.
More Definitions
Degree:
The degree of vertex v, denoted by deg(v), is the
number of edges that meet at v.
Let vbe a vertex in a directed graph G.
The number of vertices of Gadjacent from vis called
the outdegree of v.
i.e. the number of edges originating in v.
The number of vertices of Gadjacent to vis called the
indegree of v.
i.e. the number of edges ending at v.