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)

---