Vipul: /* For a finite undirected graph */

2014-05-25T19:26:25Z

For a finite undirected graph

← Older revision		Revision as of 19:26, 25 May 2014
Line 8:		Line 8:
	* 1 if there is an edge between <math>v(i)</math> and <math>v(j)</math>		* 1 if there is an edge between <math>v(i)</math> and <math>v(j)</math>

	Note that this matrix is well defined only ''after'' we fix the bijection <math>v</math>. Changing the bijection has the effect of [[groupprops:conjugation\|conjugating]] the adjacency matrix by a permutation matrix obtained by composing one bijection with the inverse of the other. In other words, we re-label the rows and re-label the columns in the same manner.		Note that this matrix is well defined only ''after'' we fix the bijection <math>v</math>. Changing the bijection has the effect of [[groupprops:conjugation\|conjugating]] the adjacency matrix by a permutation matrix obtained by composing one bijection with the inverse of the other. In other words, we re-label the rows and re-label the columns in the same manner. In particular, the characteristic polynomial as well as the multiset of eigenvalues do not depend on the choice of ordering of vertices.

	===For a finite undirected graph allowing parallel edges, loops, and weights===		===For a finite undirected graph allowing parallel edges, loops, and weights===

Vipul: Created page with "==Definition== ===For a finite undirected graph=== Suppose $G$ is a finite undirected graph. Let $n$ be the size of the vertex set..."

2012-05-28T02:54:31Z

Created page with "==Definition== ===For a finite undirected graph=== Suppose <math>G</math> is a finite undirected graph. Let <math>n</math> be the size of the vertex set..."

New page

==Definition==

===For a finite undirected graph===

Suppose <math>G</math> is a [[finite graph|finite]] [[undirected graph]]. Let <math>n</math> be the size of the vertex set <math>V(G)</math>. Fix a bijective correspondence <math>v:\{ 1,2,\dots,n\} \to V(G)</math>. The '''adjacency matrix''' of <math>G</math> is defined as the <math>n \times n</math> matrix whose <math>(ij)^{th}</math> entry is:

* 0 if there is no edge between <math>v(i)</math> and <math>v(j)</math>
* 1 if there is an edge between <math>v(i)</math> and <math>v(j)</math>

Note that this matrix is well defined only ''after'' we fix the bijection <math>v</math>. Changing the bijection has the effect of [[groupprops:conjugation|conjugating]] the adjacency matrix by a permutation matrix obtained by composing one bijection with the inverse of the other. In other words, we re-label the rows and re-label the columns in the same manner.

===For a finite undirected graph allowing parallel edges, loops, and weights===

* If we allow loops (but no parallel edges or weights), the definition does not change, but it may now be possible to have 1s on the diagonals at the entries corresponding to loops.
* If we allow parallel edges, then the <math>(ij)^{th}</math> entry is taken to be the ''number'' of edges between <math>v(i)</math> and <math>v(j)</math>.
* If we allow weights, we could use the [[weighted adjacency matrix]] instead.

===For a finite directed graph===

Suppose <math>G</math> is a [[finite graph|finite]] [[undirected graph]]. Let <math>n</math> be the size of the vertex set <math>V(G)</math>. Fix a bijective correspondence <math>v:\{ 1,2,\dots,n\} \to V(G)</math>. The '''adjacency matrix''' of <math>G</math> is defined as the <math>n \times n</math> matrix whose <math>(ij)^{th}</math> entry is:

* 0 if there is no edge from <math>v(j)</math> to <math>v(i)</math>
* 1 if there is an edge from <matH>v(j)</math> to <math>v(i)</math>

===For a finite directed graph allowing parallel edges, loops, and weights===

* If we allow loops (but no parallel edges or weights), the definition does not change, but it may now be possible to have 1s on the diagonals at the entries corresponding to loops.
* If we allow parallel edges, then the <math>(ij)^{th}</math> entry is taken to be the ''number'' of edges from <math>v(j)</math> and <math>v(i)</math>.
* If we allow weights, we could use the [[weighted adjacency matrix]] instead.

==Facts==

* The adjacency matrix of a finite undirected graph is a symmetric matrix. This remains true even if we allow loops and parallel edges.
* The adjacency matrix of a finite undirected graph has entries only 0s and 1s. This remains true even if we allow loops but is no longer true if we allow parallel edges.
* The adjacency matrix of a finite undirected graph has 0s throughout the diagonal. This remains true even if we allow parallel edges but is no longer true if we allow loops.

Adjacency matrix - Revision history

Vipul: /* For a finite undirected graph */

Vipul: Created page with "==Definition== ===For a finite undirected graph=== Suppose G is a finite undirected graph. Let n be the size of the vertex set..."

Vipul: Created page with "==Definition== ===For a finite undirected graph=== Suppose $G$ is a finite undirected graph. Let $n$ be the size of the vertex set..."