Matrices Used in Graph Theory
The following matrices find their main application in graph and network theory.
- Adjacency matrix — a square matrix representing a graph, with aij non-zero if vertex i and vertex j are adjacent.
- Biadjacency matrix — a special class of adjacency matrix that describes adjacency in bipartite graphs.
- Degree matrix — a diagonal matrix defining the degree of each vertex in a graph.
- Edmonds matrix — a square matrix of a bipartite graph.
- Incidence matrix — a matrix representing a relationship between two classes of objects (usually vertices and edges in the context of graph theory).
- Laplacian matrix — a matrix equal to the degree matrix minus the adjacency matrix for a graph, used to find the number of spanning trees in the graph.
- Seidel adjacency matrix — a matrix similar to the usual adjacency matrix but with −1 for adjacency; +1 for nonadjacency; 0 on the diagonal.
- Tutte matrix — a generalisation of the Edmonds matrix for a balanced bipartite graph.
Read more about this topic: List Of Matrices
Famous quotes containing the words graph and/or theory:
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)
“There is in him, hidden deep-down, a great instinctive artist, and hence the makings of an aristocrat. In his muddled way, held back by the manacles of his race and time, and his steps made uncertain by a guiding theory which too often eludes his own comprehension, he yet manages to produce works of unquestionable beauty and authority, and to interpret life in a manner that is poignant and illuminating.”
—H.L. (Henry Lewis)