----- NEEDS JAVASCRIPT ON. -----

[Subject home ],
[FAQ ],
[progress ],
Bib' ,
Alg's ,
C ,
Java
- L.A. ,
Sunday, 28-Nov-2021 04:20:00 AEDT
Instructions :
Topics discussed in these lecture notes are examinable
unless otherwise indicated.
You need to follow instructions,
take more notes &
draw diagrams especially as [indicated] or
as done in lectures,
work through examples, and
do extra reading.
Hyper-links not in [square brackets] are mainly for revision,
for further reading, and for lecturers of the subject.
Graphs: Introduction
The bad news?

Graphs consist of vertices (nodes) and edges (arcs)
can be weighted / un weighted
and directed / un directed /
directed-a cyclic graphs (DAG)
(also many other special types of graph)
Undirected Graph

Directed Graph

Weighted Undirected Graph

Weighted Directed Graph

Formally a
Graph ,
G, is:

G = < V, E >, a pair of sets, where
V is a set of Vertices
E is a set of edges, where
each e in E is a pair <v_{1} , v_{2} >,
and v_{1} & v_{2} are in V.
Un directed Graphs

edges are un ordered pairs, often written
(v_{1} , v_{2} ), and
(v_{1} , v_{2} ) =
(v_{2} , v_{1} ),
(Edge-) Weighted Graphs

each edge is a triple
<v_{1} , v_{2} , w>,
where w is a weight (a number/ length/ time/...etc.)
Graphs

[lecturer: derive a graph from some real example;
class: take notes!]
A Graph
G = < V, E >

max number of edges is
|V|^{2} for a directed graph
|V|*(|V|+1)/2 for an undirected graph
graph is
sparse if |E| < < |V|^{2}
dense if |E| ~ |V|^{2}
Graph by
Adjacency Matrix:
v_{2} is adjacent to v_{1} iff
<v_{1} , v_{2} > is an edge in E.
e.g. A directed graph:
read on . . .
[fill in missing bits]
directed, by adjacency matrix:
1
2
3
4
5
6
1
. . . . . .
2
. . . . . .
3
. . . . . .
4
. . . . . .
5
. . . . . .
6
. . . . . .

[fill in the missing bits]
-undirected, by adjacency matrix:
1 2 3 4 5 6
1
.
2
. .
3
. . .
4
. . . .
5
. . . . .
6
. . . . . .

Undirected graph - adjacency matrix is symmetric,
or lower - (or upper-) triangular.
Adjacency Matrices of (Un)weighted graphs,
a tricky point:
Un weighted graph
m[i,j] = true iff v_{j} is adjacent to
v_{i}
W eighted graph
m[i,j] = weight(<v_{i} , v_{j} >)
if v_{j} adjacent to v_{i}
m[i,j] = some "special" value
if v_{j} not adjacent to v_{i}
(must suit problem)
somtimes use zero (provided it cannot be a weight)
sometimes use a big value for "infinity"
[fill in missing bits]
by adjacency lists:
1: ----> [__, -]-----> nil
2: ----> [__, -]-----> nil
3: ----> [__, -]-----> nil
4: ----> [__, -]-----> [__, -]-----> [__, -]-----> nil
5: ----> [__, -]-----> [__, -]-----> [__, -]-----> nil
6: ----> [__, -] ----> nil
can represent
road, & other transport networks
electronic circuits, telecommunications networks
relationships
directed / un directed
weighted / un weighted
sparse / dense
NB. Adjacent (by an edge) and
connected (by a path) are not the same_{ } thing.
Adjacency matrix good for [_____?_____] graphs
Adjacency lists good for [_____?_____] graphs
Read about:
path
problems in Graphs.
© L.Allison ,
Sunday, 28-Nov-2021 04:20:00 AEDT
users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/14graphs.shtml
Computer Science,
Software Engineering,
Science (Computer Science).