não disponível

Our objective in this work is to study the problem of converting a given matrix to an incidence matrix of a graph using elementary row operations and column-scaling, if such a conversion is possible. This problem is a particular case of the more abstract matroid graph realization (mgr) problem, which is: given a matroid m, decide whether m is isomorphic to a matroid of a graph and, if such is the case, construct such a graph. Tutte [1960] gave a polinomial algorithm to solve the mgr problem when m is binary, that is, given by a matrix over gf (2). Bixby and wagner [1988] designed a faster algorithm based on a particular graph decomposition. Bixby and cunningham [1980] showed how the mgr problem can be solved in polinomial-time when m is representable over a field, by reducing this problem to the binary case. Finally, seymour [1981] solved the mgr problem in the general case. These algorithms are related to the polinomial-time algorithm for testing whether a given matrix is totally unimodular, which is a consequence of seymour's famous decomposition theorem of regular matroids, in the sense that both rely on a reduction to the binary case. This work describes all the algorithms mentioned above, some in terms of matroids and others in terms of matrices and graphs