Graph Entity Ontology

FLOW ALGEBRA
GRAPH ENTITY ONTOLOGY
Kireth Semantic Library
Source: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/graph-and-network-entities/graph-entity-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Status: Proposed formalisation; source-page wording not independently verified.

flow "GraphEntityOntology" v1.0

ENTITY_TYPES:
  Graph: {vertices: Set[Vertex], edges: Set[Edge], directed: Boolean, multigraph: Boolean}
  Vertex: {id: Identifier, attributes: Map}
  Edge: {id: Identifier, source: Vertex, target: Vertex, attributes: Map}
  Path: {vertices: Sequence[Vertex], edges: Sequence[Edge]}
  Subgraph: {parent: Graph, vertices: Set[Vertex], edges: Set[Edge]}
  GraphProperty: {name: String, value: Any, evidence: Optional[Evidence]}

DEFINITIONS:
  graph(G) := G = (V,E), where V is a set of vertices and E is a set of edges.
  simple_undirected_edge := unordered pair {u,v} with u != v.
  directed_edge := ordered pair (u,v).
  incidence(e,v) := v is an endpoint of e.
  adjacent(u,v) := an edge connects u and v.
  degree(v) := number of incident edge ends (a loop contributes two in undirected multigraphs).
  indegree(v) := number of directed edges ending at v.
  outdegree(v) := number of directed edges beginning at v.
  path := vertex-edge sequence with valid consecutive incidence; simple_path has no repeated vertices.
  connected(G) := every pair of vertices is joined by a path (undirected graphs).
  strongly_connected(G) := every ordered pair of vertices is joined by a directed path.

RELATIONSHIPS:
  Graph HAS_VERTEX Vertex
  Graph HAS_EDGE Edge
  Edge HAS_SOURCE Vertex
  Edge HAS_TARGET Vertex
  Vertex ADJACENT_TO Vertex [graph_context]
  Vertex INCIDENT_TO Edge [graph_context]
  Path TRAVERSES Edge
  Path CONNECTS Vertex
  Subgraph SUBGRAPH_OF Graph
  Graph HAS_PROPERTY GraphProperty

AXIOMS_AND_CONSTRAINTS:
  A1: For each edge e in G, endpoints(e) are members of V(G).
  A2: Vertex identifiers are unique within a graph.
  A3: Edge identifiers are unique within a graph.
  A4: In a simple graph, parallel edges and loops are forbidden.
  A5: In an undirected graph, adjacency is symmetric.
  A6: In a directed graph, adjacency need not be symmetric.
  A7: For a finite undirected graph, sum(degree(v) for v in V) = 2*|E|.
  A8: For a finite directed graph, sum(indegree(v)) = sum(outdegree(v)) = |E|.

INFERENCE_RULES:
  R1: HAS_EDGE(G,e) AND HAS_SOURCE(e,u) AND HAS_TARGET(e,v) -> HAS_VERTEX(G,u) AND HAS_VERTEX(G,v).
  R2: UNDIRECTED(G) AND ADJACENT_TO(u,v,G) -> ADJACENT_TO(v,u,G).
  R3: PATH_FROM_TO(p,u,v,G) -> REACHABLE(u,v,G).
  R4: REACHABLE(u,v,G) AND REACHABLE(v,w,G) -> REACHABLE(u,w,G).
  R5: CONNECTED(G) AND UNDIRECTED(G) -> COMPONENT_COUNT(G)=1 [when V(G) nonempty].
  R6: TREE(G) -> UNDIRECTED(G) AND CONNECTED(G) AND ACYCLIC(G) [finite simple graph convention].
  R7: TREE(G) AND FINITE(G) -> |E(G)| = |V(G)|-1.

SEMANTIC_DISTINCTIONS:
  GraphEntity != GraphDrawing: an abstract vertex or edge is not its visual representation.
  Vertex != Edge: vertices are objects; edges encode incidences or relations.
  DirectedGraph != UndirectedGraph: orientation affects adjacency and reachability.
  SimpleGraph != Multigraph: parallel-edge and loop policies differ.
  Path != Walk: a walk may repeat vertices or edges; a simple path does not repeat vertices.
  GraphTheoryGraph != FunctionGraph: mathematical graph structures differ from plotted function loci.
  GraphEntity != KnowledgeGraphEntity: graph-theoretic entities can represent knowledge entities but are not identical concepts.

VALIDATION:
  check endpoint_membership, unique_ids, edge_policy, directedness, path_incidence.
  check degree_sums for finite graphs.
  check claimed connectivity by reachability.
  check claimed tree status by connectivity and acyclicity.
  reject conclusions if graph type or assumptions are missing.

CONFIDENCE:
  mathematical_axioms: high when premises and graph conventions are explicit.
  inferred_properties: conditional on validated graph data.
  external_facts: require provenance and independent verification.

SEMANTIC_EQUIVALENCE:
  canonical: Graph Entity
  aliases: [Graph-Theoretic Entity, Graph Element]
  related_not_equivalent: [Network Entity, Knowledge Graph Entity, Graph Visualization]

FLOW_HASH:
  method: SHA-256
  input: canonical UTF-8 representation of ontology version, entity types, relationships, axioms and rules
  value: computed by consuming implementation; not precomputed here

UPDATE_MODEL:
  version: 1.0
  change_policy: preserve prior versions; validate modified axioms and inference rules
  provenance: source URL and authorship retained

AI_CONSUMPTION:
  purpose: typed graph reasoning, entity resolution, topology checks and explainable inference
  parse: entity types -> constraints -> relationships -> inference rules -> validation
  output: typed assertions with assumptions, evidence, confidence and provenance
  safety: do not treat a graph relationship as proof of causality; do not infer absent edges from missing data

END FLOW ALGEBRA