I am currently writing up some notes on the max-plus algebra $mathbb{R}_{max}$ (for those that have never seen the term "max-plus algebra", it is just $mathbb{R}$ with addition replaced by $max$ and multiplication replaced by addition. For some reason, authors whose main interest is control-theoretic applications never seem to use the term "tropical", and I have been reading from such authors). There is a nice result which says the following:
$textbf{Theorem.}$ Let $G$ be a directed graph on $n$ vertices such that each arc $(i,j)$ in $G$ has a real weight $w(i,j)$. Define the $n times n$ matrix $A$ by $(A)_{ij} = w(i,j)$ if $(i,j)$ is an arc, and $(A)_{ij} = -infty$ otherwise. Then for each $k > 0$, the maximum weight of a path of length $k$ from vertex $i$ to vertex $j$ is given by $(A^{otimes k})_{ij}$ (here, $A^{otimes k}$ is just the $k$th power of $A$, computed using the $mathbb{R}_{max}$ operations).
This result is certainly analagous to the standard result that the $ij$-entry of the $k$th power of the adjacency matrix gives the number of walks of length $k$ from vertex $i$ to vertex $j$. When writing up my notes I found myself claiming that the above theorem provides some evidence that $mathbb{R}_{max}$ is in fact a natural setting in which to study weighted digraphs, since there is no natural definition of an ``adjacency matrix'' of a weighted digraph (in the usual setting of $mathbb{R}^{n times n}$) that gives useful information about the weights. This seemed like too strong of a claim, especially since I am no expert in networks or combinatorial optimization. This leads to the question:
$textbf{Question.}$ Is there a standard matrix (in $mathbb{R}^{n times n}$) associated with a weighted digraph that is analogous to the adjacency matrix and captures in a useful way the weights of the arcs?
$textbf{Clarification:}$ By "analogous to the adjacency matrix" I mean a matrix that is defined simply in terms of the graph (vertices, arcs, and weights). I imagine there are all sorts of matrices associated to weighted digraphs so that computers can be used to analyze networks. But I am not interested in, say, a matrix that requires a complicated algorithm to compute its entries.
No comments:
Post a Comment