The path matrix of a graph, its construction and its use in evaluating certain products
type: Item
instance of: scholarly article
title: The path matrix of a graph, its construction and its use in evaluating certain products
zbMATH Open document ID: 0539.05045
DOI: 10.1016/0045-7825(84)90032-X
author: R. E. Roberson
published in: Computer Methods in Applied Mechanics and Engineering
publication date: 1984-01-01T00:00:00Z
review text: Let \(G=(V,E)\) be a finite connected digraph without self-loops or multiple edges. Its incidence matrix S is a \(| V| \times | E|\)-matrix defined by \[ S_{i,a} = \begin{cases} +1\quad&\text{,if \(i\) is start vertex of }a\\ -1\quad&\text{,if \(i\) is end vertex of }a\\ 0\quad&\text{,otherwise}\end{cases} \] for \(0\leq i\leq | V| -1,\quad 1\leq a\leq | E|.\) The reduced incidence matrix \(\hat S\) is obtained from S by eliminating row 0, corresponding to an arbitrary reference vertex. \(\hat S\) still contains all incidence information and is square, iff G is a tree. The generalized left inverse T (called path matrix, here) can be derived by the (weak) ordering implied by any directed spanning tree rooted in vertex 0. It is used in dynamic simulations of multi-body mechanical systems. Storage variants of \(\hat S\) and T are described. A depth-first algorithm for deriving T directly from \(\hat S\) is given, and some pseudo-algol programs for evaluating matrix-vector products involving T.
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 70E99
zbMATH DE Number: 3857156
zbMATH Keywords: incidence matrix
zbMATH Keywords: path matrix
zbMATH Keywords: depth-first-search
zbMATH Keywords: multibody mechanics
reviewed by: Jürgen Ebert
MaRDI profile type: Publication
cites work: Polhode and Herpolhode Cones in a Generalized Hooke' Joint
cites work: Q4138203
cites work: A state-space dynamical representation for multibody mechanical systems. I: Systems with tree configuration
cites work: Q3883524
full work available at URL: 0045-7825(84)90032-x
OpenAlex ID: W1968070497
description: scientific article; zbMATH DE number 3857156