Weighted Edge Ontology

FLOW ALGEBRA
WEIGHTED EDGE ONTOLOGY
Kireth Semantic Library | Mathematical Entities | Graph and Network Entities
Source: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/graph-and-network-entities/weighted-edge-ontology.html
Version: 1.0 | Date: 2026-10-14 | Locale: en-GB
Authors: Mark Higgins — Sky (Recursive AI)
Status: Proposed formalisation; source-page wording not independently verified.

1. ONTOLOGY IDENTITY
ontology WeightedEdgeOntology {
  entity WeightedEdge <: Edge
  domain GraphTheory
  purpose "Represent an edge associated with an explicitly typed weight and its interpretation."
}

2. TYPED ENTITIES
Graph := (V: Set<Vertex>, E: Set<Edge>)
WeightedGraph := (V, E, w: E -> W)
WeightedEdge := (edge_id: Identifier, endpoints: Pair<Vertex>, weight: W,
                 weight_semantics: WeightSemantics, directed: Boolean)
W := NumericDomain | OrderedDomain | ApplicationSpecificDomain
WeightSemantics := Cost | Distance | Duration | Capacity | Strength | Probability | Similarity | Other
Vertex := (vertex_id: Identifier)
Path := Sequence<Edge>

3. STRUCTURAL RELATIONSHIPS
WeightedEdge IS_A Edge
WeightedEdge BELONGS_TO WeightedGraph
WeightedEdge CONNECTS Vertex
WeightedEdge HAS_WEIGHT Weight
Weight HAS_SEMANTICS WeightSemantics
WeightedGraph DEFINES_WEIGHT_FUNCTION w
Path CONTAINS Edge

4. FORMAL DEFINITIONS AND INVARIANTS
G = (V,E,w) with w: E -> W.
For every e in E, w(e) is defined and belongs to W.
Undirected edge {u,v} has unordered endpoints; directed edge (u,v) has ordered endpoints.
Parallel edges may carry different weights when the graph permits them.
A weight need not be positive unless required by the application or algorithm.
Missing weight is not automatically equivalent to zero weight.
Edge weight and edge identity are distinct entities.
For a simple graph, no parallel edges are permitted; multigraphs may permit them.

5. OPERATORS
WEIGHT(e) -> w(e)
ASSIGN_WEIGHT(e, value: W) -> WeightedEdge
UPDATE_WEIGHT(e, value: W) -> WeightedEdge
INCIDENT(e, v) -> Boolean
ADJACENT(u, v) -> Boolean
PATH_WEIGHT(p) -> W when aggregation is defined

For additive numeric costs:
  path_weight(p) = SUM_{e in p} w(e).
For multiplicative path reliability (under stated independence assumptions):
  path_reliability(p) = PRODUCT_{e in p} w(e).
For bottleneck capacity:
  path_capacity(p) = MIN_{e in p} w(e).
The aggregation operator must match weight semantics; no universal path-weight formula exists.

6. INFERENCE RULES
R1: e IN E AND w: E -> W => w(e) IN W.
R2: e=(u,v) IN directed E => SOURCE(e)=u AND TARGET(e)=v.
R3: e={u,v} IN undirected E => INCIDENT(e,u) AND INCIDENT(e,v).
R4: p=(e1,...,ek) AND semantics=additive_cost => PATH_WEIGHT(p)=SUM_i w(ei).
R5: w(e)<0 => reject Dijkstra non-negative-weight precondition for that graph.
R6: capacity_semantics(e) => do not infer that edge capacity is additive along a path.
R7: weight(e1)=weight(e2) DOES_NOT_IMPLY e1=e2.

7. SEMANTIC DISTINCTIONS
Weighted edge != unweighted edge (unless an explicit default-weight mapping is declared).
Weight != probability: probability weights require bounds [0,1] and a suitable interpretation.
Distance != similarity: larger distance generally means farther; larger similarity often means closer.
Edge cost != edge capacity: path composition and optimisation differ.
Directed weighted edge != undirected weighted edge.
Zero weight != missing weight.

8. ALGORITHMIC PRECONDITIONS
Dijkstra: additive path costs and non-negative numeric edge weights.
Bellman-Ford: additive numeric weights; shortest paths are undefined where reachable negative cycles permit unbounded reduction.
Minimum spanning tree: undirected weighted graph with comparable weights; spanning tree requires connectivity.
Maximum flow: directed network with non-negative capacities and defined source/sink.
Do not infer algorithm validity solely from the presence of weights.

9. VALIDATION
CHECK graph vertices and edges have stable identifiers.
CHECK each edge's endpoints exist in V.
CHECK each edge has exactly one effective weight for the selected weight function.
CHECK weight values satisfy declared type, units and constraints.
CHECK directedness and parallel-edge policy.
CHECK aggregation is compatible with weight semantics.
CHECK missing and zero values are distinguishable.
CHECK algorithm-specific preconditions before execution.

10. CONFIDENCE AND PROVENANCE
CONFIDENCE:
  mathematical_axioms: high (standard graph-theoretic definitions)
  page_alignment: unverified
  inferred_application_semantics: conditional
PROVENANCE:
  source_url: above
  derivation: mathematical formalisation by authors
  source_text_verified: false

11. SEMANTIC_EQUIVALENCE
WeightedGraph ~= EdgeWeightedGraph WHEN vertices, edges, weight map and semantics agree.
WeightedEdge ~= CostedEdge ONLY WHEN weight_semantics=Cost.
WeightedEdge ~= CapacitatedEdge ONLY WHEN weight_semantics=Capacity.
No equivalence inferred from matching labels alone.

12. FLOW_HASH AND UPDATE_MODEL
FLOW_HASH:
  canonicalise ontology identifier, version, typed entities, axioms, relations and rules
  encode as UTF-8 with deterministic ordering
  hash using SHA-256
  note: actual digest must be computed on the final canonical serialisation
UPDATE_MODEL:
  versioned_change_log: required
  invalidate_dependents_on: weight_type_change | semantic_change | rule_change
  preserve_provenance: true

13. AI_CONSUMPTION
AI_CONSUMPTION:
  parse typed vertices, edges and weight semantics
  enforce domain constraints before reasoning
  choose path aggregation from explicit semantics
  check algorithm preconditions before optimisation
  report uncertainty where units or semantics are unspecified
  retain provenance and version references
  avoid conflating weight, capacity, probability and similarity

END FLOW ALGEBRA