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?

  • 1
    Modular arithmetic does not come with an ordering, so what does "shortest" mean to you in that setting?2012-03-03
  • 0
    @HenningMakholm Hm. I did *not* know that. I thought a path of length, say, $2 \bmod 13$ will be shorter than a path of length, say, $9 \bmod 13$ (using the standard representation of $\mathbb{Z}_{13}$ as $\{0,\ldots,12\}$).2012-03-03
  • 2
    Well, if you can find a cycle somewhere whose total weight is coprime to the modulus, then including an appropriate number of loops around that can produce a path of length $0$ modulo $n$ between any two vertices in the same component.2012-03-03
  • 0
    The problem with the naive ordering you propose is that you can have $a>0$ yet $a+b, which ruins most attempts to generalize things from a setting with real weights.2012-03-03
  • 0
    @HenningMakholm I should point out that I am not proposing any schemes. I am curious whether there are counter-part results dealing with the case of characteristic $> 0$ fields.2012-03-03
  • 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.