3
$\begingroup$

Let $G=(V,E,W)$ be an undirected weighted graph, where $V$ (resp. $E$) is the set of vertices (resp. edges) of $G$, and $W : E \to \mathbb{Z}_p$ is the edge weight assignment function. Note that weights in my definition are modular numbers. My impression (might be wrong)that works in graph theory (in particular, shortest paths results) assume that weights are from a characteristic zero field.

Question: are there existing results in graph theory where the edge weights are modular? In particular shortest path algorithms?

  • 3
    Note that it's not really the characteristic that's the problem, but the fact that it's not an _ordered_ field/ring. (Except that rings of positive characteristic can never be be ordered). The standard algorithms would also have trouble with weights in $\mathbb C$ and a request to find solutions whose total weight had minimal absolute value, for example.2012-03-03

2 Answers 2

0

Henning's comments answered my question.

2

Knot diagrams are sorta kinda graphs, and there are ways to prove a given knot diagram is non-trivial that involve assigning elements of ${\bf Z}_n$ for an appropriate $n$ to each strand of the diagram. See, for example, this essay by The Unapologetic Mathematician.

There are also questions about whether you can label the edges of various graphs with integers in such a way that the vertices all have different weights modulo $n$, where the weight of a vertex is the sum between the labels of its edges. Something like this is discussed in the Wikipedia essay on edge-graceful labelling.

But I think Henning's comments put paid to any connection to shortest path problems.