Lax Lean Archive

Draft — mutable and not usable as a dependency; its citation marks the draft state.

Lax489179.DistanceProperties

Uniqueness and diagonal entries of shortest-path distances

concepts/Lax489179/DistanceProperties.lean · lax-489179

proven

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Concept map

    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Evidence

    This concept declares 3 statements. Each proof establishes one of them relative to its assumptions.

    1st statement diagonal_zero proven

    2nd statement distance_unique proven

    3rd statement matrix_length proven

    Lemma

    The distance specification has at most one answer for each ordered pair. In a graph with no negative cycle every diagonal answer is zero. An encoded nn by nn distance matrix contains exactly n2n^2 words.

    Lean source view on GitHub

    1import Lax489179.WeightedAPSP
    2
    3/-!
    4---
    5title: Uniqueness and diagonal entries of shortest-path distances
    6type: lemma
    7---
    8The distance specification has at most one answer for each ordered
    9pair. In a graph with no negative cycle every diagonal answer is zero.
    10An encoded nn by nn distance matrix contains exactly n2n^2 words.
    11-/
    12
    13namespace Lax489179.DistanceProperties
    14
    15open WeightedAPSP
    16
    17axiom distance_unique (G : Graph) (u v : Fin G.vertices) (a b : Option ℤ)
    18 (ha : Distance G u v a) (hb : Distance G u v b) : a = b
    19
    20axiom diagonal_zero (G : Graph) (h : NoNegativeCycle G) (v : Fin G.vertices) :
    21 Distance G v v (some 0)
    22
    23axiom matrix_length (n : ℕ) (matrix : Fin n → Fin n → Option ℤ) :
    24 (encodeMatrix n matrix).length = n * n
    25
    26end Lax489179.DistanceProperties
    27
    Show ProofShow ProofShow Proof

    Builds on

    Used by

    none

    From Mathlib

    none

    Community review

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.

    0 comments

    Loading discussion…