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
    $\begingroup$ Modular arithmetic does not come with an ordering, so what does "shortest" mean to you in that setting? $\endgroup$ – Henning Makholm Mar 3 '12 at 21:35
  • $\begingroup$ @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\}$). $\endgroup$ – user2468 Mar 3 '12 at 21:37
  • 2
    $\begingroup$ 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. $\endgroup$ – Henning Makholm Mar 3 '12 at 21:44
  • $\begingroup$ The problem with the naive ordering you propose is that you can have $a>0$ yet $a+b<b$, which ruins most attempts to generalize things from a setting with real weights. $\endgroup$ – Henning Makholm Mar 3 '12 at 21:47
  • 3
    $\begingroup$ 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. $\endgroup$ – Henning Makholm Mar 3 '12 at 22:17

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.


Henning's comments answered my question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy