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

•Adirected graph, G= <V,E>:

•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.

###### You're Reading a Preview

Unlock to view full version