Trees Flashcards
What is a forest?
An acyclic graph (no cycles)
What is a tree Tn?
A connected acyclic graph
What are the end points of a tree?
Leaves and vertices with the degrees = one
What is a rooted tree?
Tree with single vertex r distinguished as the root. Each split creates children, where the vertex split from is called the parent
Why can vertices in a rooted tree not have more than one parent?
Implication of a cycle within the graph.
What is a directed tree?
Assymetric graph whose underlying graph is a tree
What is a directed rooted tree>?
A directed tree with vertex r designated as root such that id(r) = 0 and id(v) = 1 for all other vertices v
What is an anti-arborecence?
Directed tree with a single sink vertex, such that all other arcs point towards it
What is a spanning tree?
A spanning subgraph T of G is a tree that is a subset of G, containing all vertices of G, that is connected and acyclic
What is a minimum spanning tree?
A spanning tree of G that has a minimum total weight
Why is it important to use a minimum weight spanning tree and not a different one?
If not spanning, then missing vertices
If not tree, then not acyclic or not connected
Which algorithms are used to find minimum spanning trees?
Kruskal’s algorithm
Prim’s algorithm
What is the theorem of unique minimum spanning trees?
If all edges in weighted connected graph G have distinct weights, then G has unique minimum spanning tree T
