Tree Concepts

From NovaOrdis Knowledge Base
Revision as of 20:37, 9 October 2021 by Ovidiu (talk | contribs) (→‎Free Tree)
Jump to navigation Jump to search

Internal

Overview

A tree is a particular case of a graph.

Free Tree

A free tree is a connected, acyclic, undirected graph.

Graph FreeTree.png

For an undirected graph G = (V, E), the following statements are equivalent:

  1. G is a free tree.
  2. Any two vertices in G are connected by a unique simple path.
  3. G is connected, but if any edge is removed from E, the resulting graph is disconnected.
  4. G is connected and │E│ = │V│ - 1.
  5. G is acyclic and │E│ = │V│ - 1.
  6. G is acyclic, but if any edge is added to E, the resulting graph contains a cycle.

Forest

If the undirected graph is acyclic, but disconnected, it is a forest.

Graph Forest.png

Search Tree

Binary Tree

Binary Search Tree

TODO Binary_Search_Tree_TODELETE