Frank Harary
Abstract
The consistency of precedence matrices is studied in the very natural geometric setting of the theory of directed graphs. An elegant recent procedure (Marimont [7]) for checking consistency is further justified by means of a graphical lemma. In addition, the “direction of future work” mentioned in [7] (to which the present communication may be regarded as a sequel) is developed here using graph theoretic methods. This is based on the relationship between the occurrence of directed cycles and the recognition of “strongly connected components” in a directed graph. An algorithm is included for finding these components in any directed graph. This is necessarily more complicated than determining whether there do not exist any directed cycles, i.e., whether or not a given precedence matrix is consistent.
- 1 E. W. BARANKIN, Precedence matrices. University of California Management Sciences Research Project, Research Report No. 26, December, 1953.Google Scholar
- 2 F. HA~nY, A graph theoretic method for the complete reduction of a matrix with a view toward finding its eigenvalues. J. Math. Phys. 88 (1959), 104--111.Google Scholar
- 3 F. HAP~Rr, Graph theoretic methods in the management sciences. Management Science 5 (1959), 387-403.Google Scholar
- 4 F. HARARY, The number of functional digraphs. Math. Ann. 188 (1959), 203-211.Google Scholar
- 5 F. HARAnV AND Z. NORMAN, Graph theory as a mathematical model in social science. Ann Arbor, Institute for Social Research, 1953.Google Scholar
- 6 D. FK~NIO, Theorie der endlichen und uncndl~chen Graphen. Leipzig, 1936; reprinted New York, 1950.Google Scholar
- 7 R. B. M~RIMONT, A new method of checking the consistency of precedence matrices. J. Assoc. Comp. Mach. 6 (1959), 164--171. Google Scholar
- 8 I. C. Ross ANY F. HARARY, A description of strengthening and weakening members of a group. Sociometry 22 (1959), 139-147.Google Scholar
Index Terms
- On the Consistency of Precedence Matrices
Recommendations
A New Method of Checking the Consistency of Precedence Matrices
A new method of checking the consistency of precedence matrices is demonstrated. The method is based on the theorem that a precedence matrix is consistent if and only if every principal submatrix has at least one zero row or zero column. Because this ...
Biclique graphs and biclique matrices
A biclique of a graph G is a maximal induced complete bipartite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1,-1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, -1 entries in ...
Comments