图的拉普拉斯矩阵

内容来自

wikipedia

链接为

/wiki/Laplacian_matrix

图的拉普拉斯矩阵

1.

In

the

mathematical

field

of

graph

theory

,

the

Laplacian

matrix

,

sometimes

called

admittance

matrix

,

Kirchhoff

matrix

or

discrete

Laplacian

,

is

a

matrix

representation of a

graph

. Together with

Kirchhoff's theorem

, it can be

used to calculate the number of

spanning trees

for a given graph. The Laplacian

matrix

can

be

used

to

find

many

other

properties

of

the

graph.

Cheeger's

inequality

from

Riemannian

geometry

has

a

discrete

analogue

involving

the

Laplacian

matrix;

this

is

perhaps

the

most

important

theorem

in

spectral

graph

theory

and one of the most useful facts in algorithmic applications. It approximates

the sparsest cut of a graph through the second eigenvalue of its Laplacian.

2.

定义

Given a

simple graph

G

with

n

vertices, its Laplacian ma trix

L

n

?

n

is defined as:

L

?

D

?

A

，

where

D

is the

degree matrix

and

A

is the

adjacency matrix

of the graph. In the case

of

directed graphs

, either the

indegree or outdegree

might be used, depending on the

application.

The elements of

L

are given by

where deg(

v

i

) is degree of the vertex

i

.

The

symmetric normalized Laplacian matrix

is defined as:

The elements of

are given by

The

random-walk normalized Laplacian matrix

is defined as:

The elements of

are given by

3.

例子

Here is a simple example of a labeled graph and its Laplacian matrix.

Labeled graph

Degree matrix

Adjacency matrix

Laplacian matrix

4.

性质

For an (undirected) graph

G

and its Laplacian

matrix

L

with

eigenvalues

?

L

is symmetric.

L

is

positive-semidefinite

(that

is

for

all

i

).

This

is

verified

in

?

the

incidence matrix

section (below). This can also be seen from the fact that the

Laplacian is symmetric and

diagonally dominant

.

?

L

is an

M-matrix

(its off- diagonal entries are nonpositive, yet the real parts of

its eigenvalues are nonnegative).

?

Every row sum and column sum of

L

is zero. Indeed, in the sum, the degree of

the vertex is summed with a

?

Inconsequenc

T

, because the vector

satisfies

?

he number of times 0 appears as an eigenvalue in the Laplacian is the number

of

connected components

in the graph.

?

The smallest non-zero eigenvalue of

L

is called the

spectral gap

.

The

second

smallest

eigenvalue

of

L

is

the

algebraic

connectivity

(or

Fiedler

value

) of

G

.

?

?

When

G

is

k-regular,

the

normalized

Laplacian

is:

where A is the adjacency matrix and I is an identity matrix.

,

5.

L

关 联矩阵

Define

an