Data Structures and
Algorithms
(Graphs & Sample Algorithm)
UKZN
ENEL2DSH2
2016
,Terminology
• Span
§ Given some vector v, it possible to create a number
(or a set) of vectors that when linearly combined will
give any vector of a type similar to v
§ Similarly, given a graph, it is possible to create sub-
graphs that together they define the original graph
ü Note that a graph is constituted of vertices and
edges
, Point of interest
Vertices
v1
v1 Edges v6
v2
v6
v2
v3 Vertices
v4
v5
v4
v5
• A sub-graph with all the vertices
• If there are no loops then we end up with a t
generally called the spanning tree
• A tree is called a spanning tree of a connected
if the tree has the same nodes as G and all th
of T are contained among the edges of G. It ca
contain a cycle.
Algorithms
(Graphs & Sample Algorithm)
UKZN
ENEL2DSH2
2016
,Terminology
• Span
§ Given some vector v, it possible to create a number
(or a set) of vectors that when linearly combined will
give any vector of a type similar to v
§ Similarly, given a graph, it is possible to create sub-
graphs that together they define the original graph
ü Note that a graph is constituted of vertices and
edges
, Point of interest
Vertices
v1
v1 Edges v6
v2
v6
v2
v3 Vertices
v4
v5
v4
v5
• A sub-graph with all the vertices
• If there are no loops then we end up with a t
generally called the spanning tree
• A tree is called a spanning tree of a connected
if the tree has the same nodes as G and all th
of T are contained among the edges of G. It ca
contain a cycle.
