CSC 2200 Lecture Notes - Lecture 14: Routing Protocol, Computer Network, Cluster Analysis
27 Jun 2018
School
Department
Course
Professor
CSC 2200 lecture 14
Spanning tree
oIs a subset of graph G, which has all the vertices covered with minimum possible
number of edges
oA spanning tree does not have cycles and it cannot be disconnected
oBy definition, we can draw a conclusion that every connected and undirected
graph G has at least one spanning tree, as it cannot be spanned to all its vertices
o
Found three spanning tree off one complete graph
oSpanning tree dies not have any cycles (loops)
oRemoving one edge from the spanning tree will make the graph disconnected
The spanning tree is minimally connected
oAdding one edge to the spanning tree will create a circuit or loop
The spanning tree is maximally acyclic
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Found three spanning tree off one complete graph: spanning tree dies not have any cycles (loops, removing one edge from the spanning tree will make the graph disconnected. The spanning tree is minimally connected: adding one edge to the spanning tree will create a circuit or loop. The spanning tree is maximally acyclic: mathematical properties. Spanning tree has n-1 edges, where n is the number of nodes. A complete graph can have maximum n^(n-2) number of spanning trees: spanning tree is basically used to find a minimum path to connect all nodes in a graph, common application of spanning trees are . Has minimum weight than all other spanning trees of the same graph. This weight can be measured as distance, congestion, traffic load, or any arbitrary value denoted to the edges: kruskal"s spanning tree algorithm. To find the minimum cost spanning tree uses the greedy approach.
