Graph algorithms in the language of linear algebra

摘要

The thesis presents usefulness of duality between graph and his adjacency matrix. The teoretical part provides the basis of graph theory and matrix algebra mainly focusing on sparse matrices and options of their presentation witch takes into account the number of nonzero elements in the matrix. The thesis includes presentation of possible operations on sparse matrices and algorithms that basically work on graphs, but with help of duality between graph and his adjacency matrix can be presented with sequence of operations on matrices.udPractical part presents implementation of some algorithms that can work both with graphs or their adjacency matrices in programming language Java and testing algorithms that work with matrices.udIt focuses on comparison in efficiency of algorithm working with matrix written in standard mode and with matrix written in format for sparse matrices. It also studies witch presentation of matrices works beter for witch algorithm.ud