[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

• Graphs consist of vertices (nodes) and edges (arcs)

• can be weighted / unweighted

• and directed / undirected / directed-acyclic 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.

Undirected Graphs

• edges are unordered 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

• v2 is adjacent to v1 iff <v1, v2> is an edge in E.   e.g. A directed graph:

• read on . . .
[fill in missing bits]
1 2 3 4 5 6
1 ......
2 ......
3 ......
4 ......
5 ......
6 ......
[fill in the missing bits]
123456
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:

• Unweighted graph

• m[i,j] = true   iff   vj is adjacent to vi

• Weighted 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]
1: ----> [__, -]-----> nil

2: ----> [__, -]-----> nil

3: ----> [__, -]-----> nil

4: ----> [__, -]-----> [__, -]-----> [__, -]-----> nil

5: ----> [__, -]-----> [__, -]-----> [__, -]-----> nil

6: ----> [__, -] ----> nil

## Graph Summary

• can represent
• road, & other transport networks
• electronic circuits,   telecommunications networks
• relationships

• directed / undirected
• weighted / unweighted
• 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