Talk:Adjacency matrix

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Mid Importance
 Field: Algebra
WikiProject Computer science (Rated Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 


I removed

The modified adjacency matrix is generated by replacing all entries greater than 1 in the adjacency matrix by 1.

from the article. The edges in graphs are defined as a set, so it is not possible that an edge (vi,vj) is contained more than once. I think the adjacency matrix should be a (0,1)-matrix and perhaps in a subsection someone could extend this definition to count the number of edges two vertices share.MathMartin 18:56, 25 Sep 2004 (UTC)

This is correct, although multigraphs have a multiset of edges. Derrick Coetzee 00:25, 2 Oct 2004 (UTC)

Maybe the example graph can contain a self loop, to show how it can be represented into the adjacency matrix.

That's a great idea. Deco 01:39, 21 Mar 2005 (UTC)

Most software packages show a binary adjacency matrix, even on the diagonal. But loops are always counted twice, and some books show an adjacency matrix like this one, with 2 on the diagonal...

I don't think the information about the relationship between the invertibility of I-A and the presence of directed cycles in the graph is correct. For example, if the adjacency matrix of a directed graph is like the one below, the graph both contains a cycle and has invertible I-A.

\begin{pmatrix}
0 & 1 & 0 & 1\\
0 & 0 & 1 & 1\\
1 & 0 & 0 & 0\\
1 & 1 & 0 & 0\\
\end{pmatrix}.

The statement about det(I-A) is definitely wrong. For an infinite set of counter-examples, consider the adjacency matrices of complete graphs of 3 or more vertices. They all have determinant I-A not equal to 0, so are invertible, but they also all contain cycles, whether treated as directed or undirected graphs. Cdsmith (talk) 15:31, 1 May 2008 (UTC)

Properties section[edit]

What does one cannot 'hear' the shape of a graph mean? --Bkkbrad 19:53, 16 November 2006 (UTC)

See the following articles -
Hope that helps. It's all a little out of my league. Perhaps it needs citation, though, because it is not obvious to laymen. Also, there is at least one article on arXiv claiming you can hear the shape of certain graphs. [1] --W0lfie (talk) 16:57, 18 December 2007 (UTC)

Relative to the Adjacency Matrix example, for those less familiar with this area a small edit would clarify that the matrix listing refers to nodes 1 to 6 in the picture, with node 1 at the top and node 6 at the bottom of the matrix --TopoRubin 16:06, 3 March 2007 (UTC)

Is the Adjacency Matrix correct? It appears to indicate that node 1 is adjecent to itself. - I am not a mathematician, but unless there is a requirement in a closed sytem for this to be so I suggest the first entry should be a '0', thus maintaining the diagonal of non-self-adjacency. —Preceding unsigned comment added by 82.69.206.96 (talk) 23:57, 5 July 2008 (UTC) In general there is no restriction on self-adjacency. An example would be a no-op in a state machine. 129.11.146.164 (talk) 14:44, 18 November 2008 (UTC)

History section[edit]

Could someone with the necessary references start a history section? First known use of adjacency matrices, etc. I've searched around online and can't find anything on it's first known/documented use, or which specific cultures used it. Mojodaddy (talk) 14:23, 17 May 2009 (UTC)

one-hop connectivity matrix?[edit]

I don't know if it's right, but I added the name 'one-hop connectivity matrix' for adjacency matrix. I'm not sure, but this might be only used in network communication (ie, IEEE) circles. Rhetth (talk) 00:11, 8 December 2009 (UTC)