Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Modular arithmetic does not come with an ordering, so what does "shortest" mean to you in that setting? –  Henning Makholm Mar 3 '12 at 21:35
    
@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\}$). –  user2468 Mar 3 '12 at 21:37
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. –  Henning Makholm Mar 3 '12 at 21:44
    
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. –  Henning Makholm Mar 3 '12 at 21:47
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. –  Henning Makholm Mar 3 '12 at 22:17
show 1 more comment

2 Answers 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.

share|improve this answer
add comment
up vote 0 down vote accepted

Henning's comments answered my question.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.