----- NEEDS JAVASCRIPT ON. -----
[Subject home ],
[FAQ ],
[progress ],
Bib' ,
Alg's ,
C ,
Java
- L.A. ,
Friday, 03-May-2024 08:16:10 AEST
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 <v1 , v2 >,
and v1 & v2 are in V.
Un directed Graphs
edges are un ordered pairs, often written
(v1 , v2 ), and
(v1 , v2 ) =
(v2 , v1 ),
(Edge-) Weighted Graphs
each edge is a triple
<v1 , v2 , 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:
v2 is adjacent to v1 iff
<v1 , v2 > 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 vj is adjacent to
vi
W eighted graph
m[i,j] = weight(<vi , vj >)
if vj adjacent to vi
m[i,j] = some "special" value
if vj not adjacent to vi
(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 ,
Friday, 03-May-2024 08:16:10 AEST
users.monash.edu/~lloyd/tilde/CSC2/CSE2304/Notes/14graphs.shtml
Computer Science,
Software Engineering,
Science (Computer Science).