The authors investigate the sizes of Jordan blocks of regular matrix pencils by means of a one-to-one correspondence between a matrix pencil (λE + μA) and a weighted digraph G(E, A). Based on the relationship between determinantal divisors of a pencil and spanning-cycle families of the associated digraph G(E, A), the Jordan-block-size structure is determined graph-theoretically. For classes of structurally equivalent matrix pencils defined by a pair of structure matrices [E, A], the generic Jordan block sizes corresponding to the characteristic roots at zero and at infinity can be obtained from the unweighted digraph G([E], [A]). Eigenvalues of matrices are discussed as special cases. A nontrivial mechanical example illustrates the procedure.