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.
