Flashcards

Trees

Carl Patchett Computing Science and Mathematics English 6 cards

Cards in this deck (6)

1What is a Tree?A tree is an Undirected Graph
which has no cycles and is
connected.
2What is a Forest?A forest is a graph which has
no cycles but which is
disconnected. Each
connected component of a
forest is therefore a tree.
3What is a Rooted Tree?A rooted tree is a tree for
which one of the vertices is
identified as being the root.
4What is a Rooted Binary Tree?A rooted binary tree is a
tree for which for which each
vertex has 0, 1 or 2 children.
In this case, each child is
either designated as a left
child or a right child.
5What is a Spanning Tree?Let G be any connected
graph. Then T is called a
spanning tree for G if T is a
tree with the same vertices as
G, for which the edges are all
edges of G
6Which Algorithms have been developed for finding the minimal spanning tree for a weighted graph?Kruskal’s algorithm, Dijkstra’s Shortest Path
Algorithm