31251 Lecture Notes - Lecture 5: Adjacency Matrix, Beaufort Scale, Compact Space
30 Jun 2018
School
Department
Course
Professor
Graph and tree traversals
Graphs as Mathematical Objects
Graphs are an incredibly useful modelling tool.
Simple graphs consist of:
A set of elements called vertices.
A set of unordered pairs of distinct vertices called edges.
There is only one edge between a pair of vertices.
Other types of graph come from altering these conditions:
Ordered pairs gives directed graphs.
More than one edge per pair gives multi-graphs.
More than two vertices per edge gives hypergraphs.
Edges (and vertices) can be weighted, labelled, &c.
The vertices model interesting things:
Computers
Processes
Proteins
Production facilities
Websites
The edges model relationships between interesting things:
Network links
Shared resources
Protein interactions
Transport links
Hyperlinks
Used somehow in virtually every part of computer science.
Some Notation and Definitions
If two vertices have an edge between them, they are adjacent.
If a vertex is one of the pair that forms an edge, it is incident to that edge.
The number of edges incident to a vertex is the degree of that vertex.
Graphs will be denoted with uppercase letters like G, H, &c.
1 | P a g e
find more resources at oneclass.com
find more resources at oneclass.com
Vertices will be denoted by lowercase letters like u, v, &c., or natural numbers 1, 2, 3, 4, . . . ,
n.
Edges will be denoted by lowercase letters like e, d, &c. or by their incident vertices:
In undirected graphs uv.
In directed graphs (u, v) – u is the tail, v is the head.
Directed edges are also called arcs.
Graphs as Data Structures
As an abstract data structure, a graph needs to support a lot of basic operations:
addVertex(Vertex v)
removeVertex(Vertex v)
addEdge(Vertex u, Vertex v)
removeEdge(Vertex u, Vertex v)
adjacent(Vertex u, Vertex v)
degree(Vertex u)
return the vertices in the graph
return the edges incident to a vertex
return the vertices adjacent to a vertex
As well as the normal things needed for a usable implementation in a given language
(constructors, &c.)
Some operations may depend on the exact implementation.
Graphs as Data Structures – Adjacency Matrix
Simplest form:
Edges are stored as a two-dimensional matrix (e.g. vector<vector > edges or bool
edges[][]).
edge[i][j] == true means vertex i is adjacent to j.
Some enhancements:
Can use a numeric (int, double, . . . ) matrix to give weighted edges.
Can use a matrix of Edges if edges are more complex – a null-type value means no
edge.
Easily supports directed graphs and undirected graphs.
If vertices have associated data, we can store them separately (another array would
make matching indices easy).
2 | P a g e
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Graphs are an incredibly useful modelling tool. A set of unordered pairs of distinct vertices called edges. There is only one edge between a pair of vertices. Other types of graph come from altering these conditions: More than one edge per pair gives multi-graphs. More than two vertices per edge gives hypergraphs. Edges (and vertices) can be weighted, labelled, &c. Used somehow in virtually every part of computer science. If two vertices have an edge between them, they are adjacent. If a vertex is one of the pair that forms an edge, it is incident to that edge. The number of edges incident to a vertex is the degree of that vertex. Graphs will be denoted with uppercase letters like g, h, &c. Vertices will be denoted by lowercase letters like u, v, &c. , or natural numbers 1, 2, 3, 4, . Edges will be denoted by lowercase letters like e, d, &c. or by their incident vertices:
