赋矩阵权图的邻接矩阵的逆矩阵（英文）

崔登兰

摘 要 考虑边赋权图，其权是阶数相同的方阵.加权图的邻接矩阵和定向加权图的斜邻接矩阵以自然的方式定义.给出了具有唯一完美匹配的二部图的赋权图的邻接矩阵和斜邻接矩阵的逆矩阵的表达式，并说明这些公式在分块矩阵求逆中的应用.

关键词 加权图；邻接矩阵；斜邻接矩阵；逆矩阵

1 Introduction

We only consider graphs which have no loops or multiple edges. Let G=（V，E） be a connected graph with vertex set V={1，2，…，n} and edge set E. A weighted graph is a graph in which each edge is assigned a weight， which is usually positive number. An unweighted graph， or simply a graph， is thus a weighted graph with each of the edges bearing weight 1.

A weighted graph is a graph， each edge of which has been assigned a square matrix， called the weight of the edge. All the weight matrices will be assumed to be of the same order and nonnull. In this note， by “weighted graph” we will mean a “weighted graph with each of its edges bearing a nonnull matrix as weight”， unless otherwise stated. The spectra of these weighted graph were investigated by Das in [1～4] recently. We now introduce some more notation. Let G be a weighted graph on n vertices. Denote by wi，j the nonnull weight matrix of order p of the edge ij， and assume that wi，j=wj，i. We write ij∈E if vertices i and j are adjacent.

The adjacency matrix of a weighted graph is a block matrix， denoted and defined as A（G）=（ai，j）， where

ai，j=wi，j，if ij∈E，

0，otherwise.

Note that in the definition above， the zero denotes the p×p zero matrix. Thus A（G） is a square matrix of order np. Note also that the adjacency matrix A=（ai，j） of a weighted digraph satises ai，j=aj，i but is not nesessary symmetric in general. A （weighted or unweighted） graph G is said to be nonsingular if its adjacency matrix A（G） is nonsingular.

Let G be a （weighted） graph and G be an orientation of a （weighted） graph G， which assigns to each edge of G a direction so that G becomes a （weighted） directed graph， we call these （weighted） oriented graphs. In this paper we only consider digraphs which are oriented graphs.

The skewadjacency matrix of a weighted graph G （related to an orientation G is a block matrix， denoted and defined as S（G）=（si，j）， where

si，j=wi，j，if ij∈E and i→j，

-wi，j，if ij∈E and i←j，

0，otherwise.

Note that in the definition above， the zero denotes the p×p zero matrix. Thus S（G） is a square matrix of order np. Note that the skewadjacency matrix S（G）=（si，j） of a weighted graph satisfies sj，i=-si，j but S（G） is not necessary skew symmetric in general. A （weighted） digraph G is said to be skewnonsingular if its skewadjacency matrix S（G） is nonsingular. The spectra of skewadjacency matrix of a oriented graph and its applications were investigated in [5～9]. A graph G is said to have a perfect matching if there exists a spanning forest whose components are solely paths on two vertices. A graph in general can have more than one perfect matchings. It is wellknown that if a tree has a perfect matching， then it has a unique perfect matching and such trees are precisely the trees which nonsingular. In general， any graph which has a unique perfect matching is nonsingular[10]， and its any orientation is also skew nonsingular， this follows from that det S=（pfS）2 for any skewsymmetric matrix， where pfS is the Pfaffian of the skewsymmetric matrix S[11].Let G be a graph with a perfect matching M. A path P（i，j）=[i=i1，i2，…，I2k=j] from a vertex i to vertex j in G is said to be an alternating path if the edges i1i2，i3i4，…，i2k-1i2k are edges in the perfect matching M. In other words， a path is called an alternating path if its edges are alternately in M and not in M， and the first edge and the last edge are in M.

A combinatorial description of the inverse of the adjacency matrix of nonsingular tree has been given in[12] and in[13]. A combinatorial description of the inverse of the adjacency matrix of a bipartite graph without a cycle of length 4m is given in Cvetkovic[10]. A combinatorial description of the inverse of the adjacency matrix of a bipartite graph with a unique matching is given in[14]. In this note we supply a simple combinatorial description of the inverse of the adjacency matrix and skewadjacency matrix of a weighted bipartite graph with a unique perfect matching， which contains the formula due to [14] as a special case.

2 The Main Results

Let G be a bipartite graph with a unique perfect matching M and P（i，j） denotes the collection of all alternating paths between vertices i and j in G. Note that if P（i，j） is an alternating path between vertices i and j， then the number of edges in P（i，j） which are not in M is P（i，j）-12， where P（i，j） is the number of edges in the path P（i，j）.

Lemma 1[14] Let G be a bipartite graph with a unique perfect matching M and the edge ii′ in M. If a vertex v≠i′ is adjacent to i such that there exists an alternating path P（v，j）=[v=x1，x2，…，xn=j between vertices v and j， then P′=[i′，i，P（v， j）]=[i′，i，v，x2，…，x2k=j] is an alternating path from i′ to j.

Note that the converse of Lemma 1 holds clearly. That is， if there is an alternating path P（i′，j） from i′ to j， it must have the form [i′，i，x1，x2，…，xm=j]. Thus there must exist a vertex v=x1≠i′ adjacent to i such that an alternating path from v to j exists.

Lemma 2[15] Let G be a graph， then G is bipartite and has a unique perfect matching if and only if the adjacency matrix of G can be expressed as

A（G）=0LLt0，

where L is a lowertriangular， square （0，1）matrix with every diagonal entry equal is 1.

It follows that the determinants of the adjacency and skewadjacency matrix of a weighted bipartite graph with a unique perfect matching are ±∏i，j∈M（det wi，j）2. Thus， the adjacency and skewadjacency matrix of a weighted bipartite graph with a unique perfect matching is nonsingular if and only if all weight matrices wi，j， where ij∈M， are nonsingular.

The following result gives a combinatorial description of the inverse of the adjacency matrix of a weighted bipartite graph with a unique perfect matching.

Theorem 1 Let G be a weighted bipartite graph with a unique perfect matching M and let A（G）=（aij） be its adjacency matrix. If all weight matrices wi，j where ij∈M， are nonsingular， then A（G） is nonsingular and its inverse is the block matrix B=（bi，j）， where

A combinatorial description of the inverse of the adjacency matrix of nonsingular tree has been given in[12] and in[13]. A combinatorial description of the inverse of the adjacency matrix of a bipartite graph without a cycle of length 4m is given in Cvetkovic[10]. A combinatorial description of the inverse of the adjacency matrix of a bipartite graph with a unique matching is given in[14]. In this note we supply a simple combinatorial description of the inverse of the adjacency matrix and skewadjacency matrix of a weighted bipartite graph with a unique perfect matching， which contains the formula due to [14] as a special case.

2 The Main Results

Let G be a bipartite graph with a unique perfect matching M and P（i，j） denotes the collection of all alternating paths between vertices i and j in G. Note that if P（i，j） is an alternating path between vertices i and j， then the number of edges in P（i，j） which are not in M is P（i，j）-12， where P（i，j） is the number of edges in the path P（i，j）.

Lemma 1[14] Let G be a bipartite graph with a unique perfect matching M and the edge ii′ in M. If a vertex v≠i′ is adjacent to i such that there exists an alternating path P（v，j）=[v=x1，x2，…，xn=j between vertices v and j， then P′=[i′，i，P（v， j）]=[i′，i，v，x2，…，x2k=j] is an alternating path from i′ to j.

Note that the converse of Lemma 1 holds clearly. That is， if there is an alternating path P（i′，j） from i′ to j， it must have the form [i′，i，x1，x2，…，xm=j]. Thus there must exist a vertex v=x1≠i′ adjacent to i such that an alternating path from v to j exists.

Lemma 2[15] Let G be a graph， then G is bipartite and has a unique perfect matching if and only if the adjacency matrix of G can be expressed as

A（G）=0LLt0，

where L is a lowertriangular， square （0，1）matrix with every diagonal entry equal is 1.

It follows that the determinants of the adjacency and skewadjacency matrix of a weighted bipartite graph with a unique perfect matching are ±∏i，j∈M（det wi，j）2. Thus， the adjacency and skewadjacency matrix of a weighted bipartite graph with a unique perfect matching is nonsingular if and only if all weight matrices wi，j， where ij∈M， are nonsingular.

The following result gives a combinatorial description of the inverse of the adjacency matrix of a weighted bipartite graph with a unique perfect matching.

Theorem 1 Let G be a weighted bipartite graph with a unique perfect matching M and let A（G）=（aij） be its adjacency matrix. If all weight matrices wi，j where ij∈M， are nonsingular， then A（G） is nonsingular and its inverse is the block matrix B=（bi，j）， where

A combinatorial description of the inverse of the adjacency matrix of nonsingular tree has been given in[12] and in[13]. A combinatorial description of the inverse of the adjacency matrix of a bipartite graph without a cycle of length 4m is given in Cvetkovic[10]. A combinatorial description of the inverse of the adjacency matrix of a bipartite graph with a unique matching is given in[14]. In this note we supply a simple combinatorial description of the inverse of the adjacency matrix and skewadjacency matrix of a weighted bipartite graph with a unique perfect matching， which contains the formula due to [14] as a special case.

2 The Main Results

Let G be a bipartite graph with a unique perfect matching M and P（i，j） denotes the collection of all alternating paths between vertices i and j in G. Note that if P（i，j） is an alternating path between vertices i and j， then the number of edges in P（i，j） which are not in M is P（i，j）-12， where P（i，j） is the number of edges in the path P（i，j）.

Lemma 1[14] Let G be a bipartite graph with a unique perfect matching M and the edge ii′ in M. If a vertex v≠i′ is adjacent to i such that there exists an alternating path P（v，j）=[v=x1，x2，…，xn=j between vertices v and j， then P′=[i′，i，P（v， j）]=[i′，i，v，x2，…，x2k=j] is an alternating path from i′ to j.

Note that the converse of Lemma 1 holds clearly. That is， if there is an alternating path P（i′，j） from i′ to j， it must have the form [i′，i，x1，x2，…，xm=j]. Thus there must exist a vertex v=x1≠i′ adjacent to i such that an alternating path from v to j exists.

Lemma 2[15] Let G be a graph， then G is bipartite and has a unique perfect matching if and only if the adjacency matrix of G can be expressed as

A（G）=0LLt0，

where L is a lowertriangular， square （0，1）matrix with every diagonal entry equal is 1.

It follows that the determinants of the adjacency and skewadjacency matrix of a weighted bipartite graph with a unique perfect matching are ±∏i，j∈M（det wi，j）2. Thus， the adjacency and skewadjacency matrix of a weighted bipartite graph with a unique perfect matching is nonsingular if and only if all weight matrices wi，j， where ij∈M， are nonsingular.

The following result gives a combinatorial description of the inverse of the adjacency matrix of a weighted bipartite graph with a unique perfect matching.

Theorem 1 Let G be a weighted bipartite graph with a unique perfect matching M and let A（G）=（aij） be its adjacency matrix. If all weight matrices wi，j where ij∈M， are nonsingular， then A（G） is nonsingular and its inverse is the block matrix B=（bi，j）， where