资源描述：
《矩阵在图论中的应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、矩阵在图论中的应用一、无向图的邻接矩阵定义1：设图G顶点集合为VG(){,,,}=vv"v，边集为E(){,,,}Ge=ee"，则图12p12qG的邻接矩阵AG()()=a定义为ijpp×⎧⎪1(vv∈EG)ija=⎨ij⎪0(vv∉EG)⎩ij例1．如下图Gv1e1v2e2e3e4v3e5v4G的邻接矩阵为⎛⎞0110⎜⎟1011AG()=⎜⎟⎜⎟1101⎜⎟⎝⎠0110nn()定理1：设图G的顶点集为VG(){,,,}=vv"v，邻接矩阵为A，且Aa=()，则12pijpp×()na为G中长为n的不同vv−途径的条数。ijij证
2、明：对n进行归纳。当n=1时，由邻接矩阵定义，a=1当且仅当存在一条vv−途径，ijijnn−−1(1)(1n−)故结论成立。设Aa=()，且a为G中长为n-1的不同vv−途径的条数，由ijpp×ijijpnn−1()nn(1)−(1n−)A=AA得，aaij=∑ikakj，而aaikkj为由长为n-1的vvik−途径加上vvkj边k=1()n组成的长为n的vv−途径的条数，由归纳假设，a为长为n的不同vv−途径的条数。ijijij例2．如例1中⎛⎞01100110⎛⎞⎛⎞2112⎜⎟⎜⎟⎜⎟101110111321A2==⎜⎟⎜⎟
3、⎜⎟⎜⎟11011101⎜⎟⎜⎟1231⎜⎟⎜⎟⎜⎟⎝⎠01100110⎝⎠⎝⎠2112(2)a=2表示长为2的vv−途径有2条，即vevev和vevev。14141124412354⎛⎞21120110⎛⎞⎛⎞2552⎜⎟⎜⎟⎜⎟132110115455AA32==A⎜⎟⎜⎟=⎜⎟⎜⎟12311101⎜⎟⎜⎟5545⎜⎟⎜⎟⎜⎟⎝⎠21120110⎝⎠⎝⎠2552(3)a=5表示长为3的vv−途径有5条，即：1212vevevev,vevevev,vevevev,vevevev,vevevev.112111212321121123
4、33211244421235442ki推论：设G的邻接矩阵为A，Mm==()ijpp×∑A，则mij为长度不超过k的vvi−j途i=1径的条数。二、有向图的关联矩阵定义2：设有向图D的顶点集为VG(){,,,}=vv"v，弧集为H(){,,,}Dh=hh"，12p12q则图D的关联矩阵BD()()=b定义为，ijpq×⎧1∃=vvaikj⎪bv=−∃⎨1v=aijkij⎪⎩0otherwise例3．如下图Dv1e2e3e1e4v2e5v3ev46D的关联矩阵为⎛⎞111000⎜⎟−100110BD()=⎜⎟⎜⎟010101−−⎜⎟⎝
5、⎠001011−−−定理2：P阶连通有向图D的关联矩阵B的秩为p-1。（不证）定义3：设B为p阶连通有向图D的关联矩阵，从B中去掉与顶点v对应的一行得一k(1pq−×)矩阵B，称B为D的对应于顶点v的基本关联矩阵。kkk定理3：设B为有向图D的基本关联矩阵，且Ceee={,,,}"是D中一回路，则回路Ck12l的各边所对应的矩阵B的各列必线性相关。k证明：设M为B中ee,,,"e对应的列构成的子阵，若C中含有v，则由定理2，秩k12lk()M≤−l1；若C中不含v，则M中非零行的个数至多为l−1，则秩()M≤−l1。所k以B中ee,
6、,,"e对应的列线性相关。k12l推论：B任一p−1阶子式M不为零的充要条件是M的各列对应的边构成的子图为D的生k成树。引理（Binet-Canchy）：设有矩阵Aa=()和Bb=()，且mn≤，则ijmn×ijnm×
7、
8、
9、
10、ABA=∑ii
11、
12、B，i其中
13、
14、A是矩阵A中m阶子式，
15、
16、B则是B中相应的m阶子式。iiT定理4：设B为有向图D的任一基本关联矩阵，则图D的生成树的数目为
17、
18、BB。kkk证明：TT2∵
19、BBkk
20、
21、
22、==∑∑BBi
23、
24、
25、
26、iBiii又当B中列对应的边构成树时，B=±1，否则，B=0。iiiT∴
27、
28、BB为D中生成
29、树的数目。kk例4．从例3中图D的关联矩阵B中取v的基本关联矩阵4⎛⎞111000⎜⎟TB=−100110，计算
30、
31、BB=16.4⎜⎟44⎜⎟⎝⎠010101−−说明图D有16个不同的生成树，如下图v1v1v1v1e2e3e2e3e1e1e4v2v2e5e4v2e5v3v4vv3e6v4v3e6v43v4v1v1v1v1e2e2e3e2e3e3e1e1v2e4v2v2e5v2e5v3e6v4v3v4v3v4v3e6v4v1v1v1v1e3e2e3e1e4v2v2e5e4v2v2e5v3e6v4v3e6v4v3e6v4v3e6v4v1
32、v1v1v1e3e3e2e2e1e1e1e4e4v2e5e4v2e5v2e5v3v4v3v4v3v4v3v4
