Weighted Graph Ontology

FLOW ALGEBRA
WEIGHTED GRAPH 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-graph-ontology-2.html
Version: 1.0 | Date: 2026-10-14
Authors: Mark Higgins — Sky (Recursive AI)
Status: Proposed formalisation; source page text not independently verified.

1. ENTITY DEFINITION
entity WeightedGraph : Graph
  fields:
    vertices: Set[Vertex]
    edges: Set[Edge]
    directed: Boolean
    weight: Map[Edge, WeightValue]
    weight_domain: NumericDomain | OrderedMonoid | Semiring
    weight_semantics: Cost | Distance | Capacity | Strength | Probability | Custom
  constraints:
    endpoints(edge) belong to vertices
    weight is defined for each edge
    weights must satisfy algorithm-specific assumptions

2. MATHEMATICAL MODEL
Undirected weighted graph: G = (V, E, w), E subset of {{u,v} : u,v in V}.
Directed weighted graph: G = (V, E, w), E subset of V x V.
Weight map: w : E -> W.
For additive numeric path costs: cost(P) = sum_{e in P} w(e).
Weighted adjacency representation A[u,v] = w(u,v) for existing edges; absence is represented separately, not by numeric zero.
For undirected graphs: w({u,v}) = w({v,u}) because the edge is unordered.

3. TYPES
WeightedGraph -> DirectedWeightedGraph | UndirectedWeightedGraph
WeightValue -> FiniteNumericWeight | ExtendedNumericWeight | DomainSpecificWeight
EdgeWeightSemantics -> Cost | Distance | Capacity | Similarity | Reliability
PathObjective -> MinimumCost | MaximumCapacity | MaximumReliability | Custom

4. TYPED RELATIONSHIPS
WeightedGraph HAS_VERTEX Vertex
WeightedGraph HAS_EDGE Edge
Edge CONNECTS Vertex
Edge HAS_WEIGHT WeightValue
WeightValue HAS_UNIT MeasurementUnit?
WeightedGraph HAS_WEIGHT_SEMANTICS EdgeWeightSemantics
Path CONTAINS_EDGE Edge
Path HAS_AGGREGATED_WEIGHT AggregateWeight
Algorithm REQUIRES Assumption

5. OPERATIONS
add_vertex(G,v) -> G'
add_edge(G,e,w) -> G'
update_weight(G,e,w_new) -> G'
remove_edge(G,e) -> G'
edge_weight(G,e) -> W
path_weight(G,P,aggregate) -> W
adjacent(G,u,v) -> Boolean
shortest_path(G,s,t,algorithm) -> Path | Unreachable | Undefined
minimum_spanning_tree(G) -> Tree  [only undirected connected graphs; forests for disconnected graphs]

6. AXIOMS AND INVARIANTS
A1: Every edge's endpoints belong to V.
A2: Every edge has exactly one assigned weight value within the selected representation.
A3: Directionality is explicit; directed edges are ordered pairs.
A4: Weight semantics and units are declared before comparisons.
A5: Missing edges are distinct from edges of weight zero.
A6: The graph may have zero, positive, or negative numeric weights unless constrained by an operation.
A7: A path aggregate is not necessarily a sum; its aggregation operator is declared.
A8: Parallel edges and self-loops require an explicit graph-model policy.

7. INFERENCE RULES
R1: IF all weights are nonnegative numeric costs THEN Dijkstra's algorithm is eligible for shortest paths.
R2: IF a reachable negative-weight cycle can affect a target THEN no finite minimum walk cost exists for that target.
R3: IF negative weights exist and no relevant negative cycle exists THEN Bellman-Ford can compute finite shortest-path costs.
R4: IF G is undirected and connected with comparable numeric edge weights THEN a minimum spanning tree exists for finite G.
R5: IF G is undirected but disconnected THEN a minimum spanning forest can be computed.
R6: IF weights represent capacities THEN path cost addition is not automatically a valid capacity aggregate.
R7: IF a graph is undirected THEN an edge has no inherent source/target orientation.
R8: IF an edge has weight zero THEN it remains an existing edge.

8. SEMANTIC DISTINCTIONS
WeightedGraph != WeightedEdge: a graph contains weighted edges.
WeightedGraph != DirectedGraph: weighting and direction are independent properties.
EdgeWeight != VertexWeight: attachment target differs.
ShortestPath != MinimumSpanningTree: objectives and outputs differ.
Cost != Capacity != Probability: numerical values do not imply interchangeable semantics.
GraphDistance != EuclideanDistance: shortest-path distance depends on graph structure and weights.

9. EXAMPLE
V = {A,B,C}
E = {(A,B),(B,C),(A,C)}
w(A,B)=2; w(B,C)=3; w(A,C)=8
Under additive cost semantics, path A-B-C costs 5, below direct A-C cost 8.
Example assumes an undirected graph with nonnegative edge costs.

10. VALIDATION
validate vertices are uniquely identified
validate each edge references declared vertices
validate every edge has a weight
validate weight domain and semantics
validate edge directionality and parallel-edge policy
validate algorithm preconditions before execution
validate consistent units for additive comparisons
validate graph updates preserve referential integrity

11. CONFIDENCE AND PROVENANCE
CONFIDENCE:
  mathematical_definitions: high
  ontology_alignment_to_source_page: unverified
  inference_results: conditional_on_assumptions
PROVENANCE:
  source_url: as listed above
  derivation: proposed formal mathematical model
  verification: requires source-page comparison

12. SEMANTIC_EQUIVALENCE
aliases: [edge-weighted graph, weighted network]
conditional_equivalence: weighted network ~ weighted graph when network entities are represented as graph vertices and weighted edges
non_equivalence: weighted graph != unweighted graph; weights carry additional information

13. FLOW_HASH
FLOW_HASH:
  method: SHA-256 over canonical UTF-8 serialisation
  canonical_fields: [entity_type, vertices, edges, directed, weight_map, weight_domain, weight_semantics, ontology_version]
  ordering: sort vertex identifiers and canonical edge records
  status: compute at ingestion; no hash asserted in this document

14. UPDATE_MODEL
UPDATE_MODEL:
  change_tracking: [vertex_added, vertex_removed, edge_added, edge_removed, weight_changed, semantics_changed]
  invalidation: recompute affected path and optimisation results after relevant changes
  version_policy: increment version when structure or meaning changes

15. AI_CONSUMPTION
AI_CONSUMPTION:
  representation: typed entities and relations
  input_requirements: [graph_structure, weight_semantics, weight_domain, objective, algorithm_assumptions]
  output_requirements: [result, method, assumptions, confidence, provenance]
  safety_checks: [missing_edge_handling, negative_cycle_check, unit_consistency, directedness_check]
  disallow: [implicit_zero_for_missing_edge, unqualified_algorithm_claim, treating_capacity_as_cost]

END FLOW ALGEBRA