We discuss the interpretation of some matrix max-plus algebra Rmax operations and concepts in graph theory. We show that every matrix A e Rmax corresponds to a weighted directed graph and conversely. A formula for the maximum mean weight of the elementary circuit in the precedence graph of A is max (A) = (1/k trace(A). if matrix A e R max is irreducible, then A has a unique max-plus algebra eigen value max (A).