Trees Flashcards
Defintion
Connected, undirected graph with no cycles.
What is a cycle
a closed path in which all the edges are different and all the intermediate vertices are different.
A closed path/circuit definition
Succession of edges that star and end at the same vertex.
Vertex definition
The objects that a graph is composed of aka nodes.
Edge defintion
The link between the vertices aka arc.
Degree definition
The number of edges connection to a node.
Neighbour definition
Vertex x is a neighbour of vertex y if an edge directly links them.
Path definition
A sequence of edges leading from one vertex to another.
Design of a tree
All the nodes are connected.
Edges are undirected.
There are no cycles.
Define a rooted tree (RT)
Has a root node from which all other nodes stem.
Parent node definition (RT)
A node from which all other nodes stem from.
Do root nodes have parents? (RT)
No
Child node definition (RT)
Nodes with a parent.
Leaf nodes definition (RT)
Child nodes with no children.
Binary tree definition (BT)
A rooted tree in which every parent node has no more than two child nodes.
What can rooted trees (including binary trees) be used to represent?
Family trees, or file systems on a computers hard drive.
