Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

2 ADJACENCY MATRICES

1

Basic Graph Theory

Graph theory investigates the structure, properties, and algorithms associated with graphs
...

A graph, denoted G, is defined as an ordered pair composed of two distinct sets:
1
...
A set of edges, denoted E(G)
The order of a graph G refers to |V (G)| and the size of a graph G refers to |E(G)|
...

In order to perform compuptations with these graphs, we utilize matrices as an incredibly valuable, alternative representation
...


2
2
...
For this reason,
adjacency matrices are one of the most common ways of representing graphs
...
2

Distance and Powers of A

The distance between vertices vi and vj , denoted d(i, j), of a graph G is defined by the
path of minimum length between the two vertices
...

There are two paths of length 4 between vertices v6 and v8 as depicted in Figure 2
...

Theorem 2
...
Let G be a graph with adjacency matrix A and k be a positive integer
...

For example, return to the graph shown in Figure 2
...


3

2
...
While this result provides a useful method
of counting the number of paths between vertices in a graph, it can be extended to a similarly
interesting and logical corollary
...
1
...
Then
the sum Sn defined by
Sn = A + A2 +
...

Herein matrices once again provide a computationally useful tool for identifying and
organizing the properties of a graph
...
3

Eigenvalues and Complete Graphs

A complete graph G of order n, denoted Kn , includes an edge between every pair of
vertices
...

A complete bipartite graph G of order n = p + q, denoted Kp,q , consists of two sets
U, V ⊂ E(G) for which every vertex of U is adjacent to every vertex of V , and no two vertices
within the same set are adjacent
...

4

3 INCIDENCE MATRICES

Figure 4: Complete Bipartite Graph K3,4

Figure 3: Complete Graph K5

The eigenvalues of a graph G are the eigenvalues of its adjacency matrix
...

Theorem 2
...
For any positive integer n, the eigenvalues of Kn are n − 1 with multiplicity
1, and −1 with multiplicity n - 1
...

While this result is interesting in its own right, this theorem can be used to interweave a
basic result from graph theory with one in linear algebra
...
Combining this fact with
the above result, this means that every n − k + 1 square submatrix, 1 ≤ k ≤ n, of A(Kn )
possesses the eigenvalue −1 with multiplicity k and the eigenvalue n − k + 1 with multiplicity
1
...


3
3
...
2 Incidence and Rank

3 INCIDENCE MATRICES


Qij =

1, if vertex vi is incident to edge ej
0, otherwise

(4)

Although incidence matrices are not as computationally useful as adjacency matrices, they
retain certain interesting properties using linear algebra
...
2

Incidence and Rank

First, an observation: the column sums of Q(G) are all zero, and hence the rows of Q(G) are
linearly depedent, because the vector consisting of all 1 spans the null space of Q
...
It turns
out, however, that for any graph G, only one of the columns is a linear combination of the
others:
Lemma 3
...
If G is a connected graph on n vertices, then rank Q(G) = n − 1
...
A disconnected graph is a graph in which at least one pair
of vertices does not have a path between them
...


Figure 5: A disconnected graph of order 9
Each connected subsection of a graph G is called a component G
...
Using the previous lemma, we can produce a more general
result for any graph
...
1
...

Thus, incidence matrices capture a different aspect of graphs
...


6

3
...
3

4 LAPLACIAN MATRICES

Path Matrices and Incidence Matrices

Let G be a graph with size m and u, v ∈ V (G) (that is, any two vertices u and v of G)
...

In other words, a path matrix is defined for a certain pair of vertices in a graph G in which
• the rows of P (u, v) correspond to the different paths from vertex u to vertex v (which,
for example, could be counted using the m-th power of the adjacency matrix Am (G),
as described in Section 2
...

Theorem 3
...
Let G be a graph of order n, and at least two vertices u, v ∈ V (G)
...
Then,
Q(G) ∗ P T (u, v) (mod 2) = M,
(6)
where M is the matrix having all ones in two rows u and v, and zeros in the remaining n 2 rows
...
One of the most powerful
matrix representations, however, has yet to come
...
1

Laplacian Matrices
Definition

The degree of a vertex vi , denoted di , is the total number of other vertices to which vertex
i is adjacent
...
This provides us with a basis of knowledge for defining the Laplacian matrix, which
at first glance seems entirely arbitrary, but has a number of incredible properties
...
Otherwise, every other entry consists of all zeros
...
2 The Matrix Tree Theorem

4 LAPLACIAN MATRICES

If we define D0(G) to be a diagonal matrix whose entries are the degrees of each vertex,
then the Laplacian Matrix of a graph G can be equivalently defined as
L(G) = D0(G) − A(G)

(8)

Remarkably, Laplacian Matrices can also be expressed in terms of Incidence Matrices
...
2

The Matrix Tree Theorem

A spanning tree of a graph G is a tree which is a subgraph of G
...
As one can imagine, counting all of the spanning
subtrees of a graph G can rapidly become an arduous task
...

Namely, one of the most useful, elegant theorems in graph theory is that of The Matrix
Tree Theorem
...
1 (Matrix Tree Theorem)
...
Then the cofactor
of any element of L(G) equals the number of spanning trees of G
...
Taking the (2,3)-cofactor of the Laplacian Matrix of the
triangle:



−1
2+3  2
C23 = (−1)
∗
= (−1) ∗ (−2 − 1) = 3
(11)
−1 −1
which corresponds to the 3 spanning trees of the graph, depicted in Figure 7
...


5
5
...
Naturally, this means that
D(G) is a symmetric matrix whose diagonal consists entirely of zeros
...
2

Distance Matrices and Trees

When distance matrices are applied to trees, an interesting generality emerges:
Theorem 5
...
Let T be a tree with order n
...
First, as a direct
connection to linear algebra, because the determinant is nonzero for all trees of order n ≥ 3,
the distance matrix of all trees is nonsingular
...
That is, of the nn−2 trees of order n, every single one of their distance
matrices has the same determinant
...


9

5
...
3

5 DISTANCE MATRICES

Connection Between Distance and Laplacian Matrices

Finally, there exists a connection between the distance and Laplacian matrices of a tree:
Theorem 5
...
Let T be a tree of order n with Laplacian matrix L and distance matrix D
...
It suggests an
underlying similarity of great interest
...
http://compalg
...
elte
...

PDF, 2010
...

[2] R
...
Bapat
...
Hindustan Book Agency, New Delhi, India, 2010
...
A First Course in Graph Theory
...

[4] Douglas E
...
Winston Crawley
...
John Wiley and Sons,
Inc
...

[5] Laszlo Lovasz
...
http://www
...
elte
...
pdf,
2007
...

[6] Damir Vukiccevic and Ivan Gutman
...

http://elib
...
sanu
...
rs/files/journals/kjm/26/d003download
...
[Online; accessed 17-03-2017]

---