Tree Ontology

FLOW ALGEBRA
TITLE: Tree Ontology
DOMAIN: Discrete Mathematics / Graph Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/graph-theory/tree-ontology-2.html
VERSION: 1.0
DATE: 2026-10-11
AUTHORS: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
STATUS: Mathematical reference model; source-page text not independently verified.

1. ONTOLOGY DEFINITION
ontology TreeOntology extends GraphTheoryOntology:
  entity Tree: ConnectedAcyclicUndirectedGraph
  entity Forest: AcyclicUndirectedGraph
  entity Vertex: GraphVertex
  entity Edge: UnorderedPair[Vertex]
  entity RootedTree: TreeWithDistinguishedRoot
  entity Root: Vertex
  entity Parent: Vertex
  entity Child: Vertex
  entity Leaf: Vertex
  entity InternalVertex: Vertex
  entity Path: VertexSequence
  entity Subtree: RootedTree
  entity SpanningTree: Tree
  entity Depth: NonNegativeInteger
  entity Height: NonNegativeInteger

2. TYPE CONSTRAINTS
  Tree(V,E) requires finite(V) and E subset {{u,v} | u,v in V and u != v}
  connected(Tree) = true
  acyclic(Tree) = true
  Forest(V,E) requires acyclic(Forest)
  rooted(T,r) requires T:Tree and r in vertices(T)
  parent_T(v) defined only for rooted tree and v != root(T)
  children_T(v) = {u | parent_T(u) = v}

3. CORE FLOW OPERATIONS
flow IsTree(G:UndirectedGraph) -> Boolean:
  return connected(G) AND acyclic(G)

flow IsForest(G:UndirectedGraph) -> Boolean:
  return acyclic(G)

flow UniquePath(T:Tree, u:Vertex, v:Vertex) -> Path:
  require u,v in vertices(T)
  return the unique simple u-v path in T

flow RootTree(T:Tree, r:Vertex) -> RootedTree:
  require r in vertices(T)
  orient conceptual parent-child relationships away from r
  return rooted(T,r)

flow Depth(T:RootedTree, v:Vertex) -> NonNegativeInteger:
  return number_of_edges(UniquePath(T,root(T),v))

flow Height(T:RootedTree, v:Vertex) -> NonNegativeInteger:
  return max({distance(v,leaf) | leaf descendant of v})

flow SpanningTree(G:ConnectedUndirectedGraph) -> Tree:
  return (V(G), Eprime) where Eprime subset E(G), connected(V(G),Eprime), acyclic(V(G),Eprime)

4. AXIOMS AND INVARIANTS
  A1: finite nonempty undirected G is a tree iff G is connected and acyclic.
  A2: if T is a finite tree, |E(T)| = |V(T)| - 1.
  A3: any two distinct vertices of a tree have exactly one simple path.
  A4: removing any edge of a tree disconnects it.
  A5: adding an edge between two previously nonadjacent vertices of a simple tree creates exactly one cycle.
  A6: every finite tree with at least two vertices has at least two leaves (degree-one vertices).
  A7: every connected undirected graph contains a spanning tree.
  A8: a forest with n vertices and c connected components has n-c edges (including isolated vertices).
  A9: in a rooted tree every non-root vertex has exactly one parent.
  A10: a one-vertex tree has zero edges; its vertex is a leaf in the rooted-child sense, but has degree zero.

5. RELATIONSHIPS
  Tree is_a Graph
  Tree has_property Connected
  Tree has_property Acyclic
  Forest consists_of TreeComponents
  RootedTree has_root Root
  Parent has_child Child
  Subtree part_of RootedTree
  SpanningTree spans_vertices_of Graph
  Leaf is_a Vertex
  Edge connects Vertex

6. INFERENCE RULES
  R1: connected(G) AND acyclic(G) => IsTree(G).
  R2: IsTree(T) AND finite(T) => |E(T)| = |V(T)|-1.
  R3: IsTree(T) AND edge(e,T) => not connected(T-e).
  R4: IsTree(T) AND nonedge({u,v},T) => exactly_one_cycle(T+{u,v}).
  R5: IsForest(F) AND components(F)=c => |E(F)|=|V(F)|-c.
  R6: rooted(T,r) AND v != r => exists_unique(parent_T(v)).
  R7: IsTree(T) AND |V(T)|>=2 => at_least_two_degree_one_vertices(T).

7. VALIDATION
  validate finite_simple_undirected_graph_input
  validate every_edge_endpoint_belongs_to_vertex_set
  validate no_self_loops_for_simple_tree
  validate connectivity_and_acyclicity_independently
  validate edge_count_as_necessary_not_sufficient_test
  validate root_membership_before_parent_or_depth_queries
  validate distinguish rooted_leaves_from_degree_one_vertices
  validate empty_graph_convention_explicitly (this model requires nonempty trees)

8. SEMANTIC_EQUIVALENCE
  Tree <=> finite nonempty connected acyclic undirected graph
  Tree <=> finite nonempty connected undirected graph with |E|=|V|-1
  Tree <=> finite nonempty acyclic undirected graph with |E|=|V|-1
  Tree <=> finite nonempty undirected graph with unique simple path between each distinct vertex pair
  Forest <=> acyclic undirected graph
  Note: equivalences assume finite simple undirected graphs and stated nonempty convention.

9. CONFIDENCE
  formal_mathematical_definitions: 1.00
  stated_finite_graph_theorems: 1.00
  semantic_aliases_context_sensitive: 0.95
  source_page_alignment: unverified
  rule: confidence values indicate model assessment, not empirical calibration.

10. FLOW_HASH
  algorithm: SHA-256
  canonicalisation: UTF-8; LF line endings; normalise trailing whitespace
  hash_scope: sections 1-9 and 11-12 (exclude this field)
  value: COMPUTE_ON_PUBLICATION
  rule: do not represent placeholder as computed digest.

11. UPDATE_MODEL
  version: 1.0
  update_triggers: definition_revision, theorem_correction, ontology_alignment_change, source_page_change
  validation_required: true
  preserve_provenance: true
  regenerate_flow_hash_after_update: true

12. AI_CONSUMPTION
  primary_entity: Tree
  ontology_class: GraphTheory.Tree
  accepted_inputs: finite simple undirected graph; optional distinguished root
  output_types: Boolean, Tree, Forest, Path, Integer, InferenceResult
  reasoning_modes: deductive, structural, constraint_validation
  related_topics: Graph, Vertex, Edge, DirectedGraph, UndirectedGraph, SpanningTree, Path, Cycle, Forest
  caution: a directed arborescence is not identical to an undirected tree; use an explicit conversion or separate ontology.

END FLOW ALGEBRA