第七章 离散数学 图论-3rd.pdfVIP

离散数学 大连理工大学软件学院 陈志奎 教授 办公室：综合楼411 ，Tel 实验室：教学楼A318/A323 ，Tel 24 Mobile: Email: zkchen@ zkchen00@ 第七章 图论 7.4图的矩阵表示 一、邻接矩阵 定义：设G =〈V , E,ψ〉是一个简单有向图，其中的 V {v , v ,=⋅⋅⋅v } 结点集合 1 2 n ，并且假定各结点已经有了 从结点v 到v 的次序。试定义一个n ×n 的矩阵A ，使 1 n 得其中的元素 1 当〈v ,v 〉∈E ai j { i j (1) 0 当 v v E 〈 , 〉∉ i j 则称这样的矩阵A 是图G的邻接矩阵。 3 邻接矩阵 定义：元素或为0或为1的任何矩阵，都称为比特矩 阵或布尔矩阵。 邻接矩阵也是布尔矩阵，第i行上值为1的元素的个 数，等于结点vi 的出度；第j 列上值为1的元素的个数， 等于结点v 的入度。 j 4 邻接矩阵 图的邻接矩阵不具有唯一性。 对于给定简单有向图G =〈V , E,ψ〉来说，其邻接矩阵 依赖于集合V中的各元素间的次序关系。 给定两个有向图和相对应的邻接矩阵，如果首 先在一个图的邻接矩阵中交换一些行，而后交 换相对应的各列，从而有一个图的邻接矩阵， 能够求得另外一个图的邻接矩阵，则事实上这 样的两个有向图，必定是互为同构的。 5 邻接矩阵 例：写出下图的邻接矩阵，并计算各个节点的出度 和入度。 解：首先给各结点安排好一个 v 次序，譬如说是v ,v ,v ,v 。得 1 v2 1 2 3 4 出邻接矩阵如下： v v v v v v 1 2 3 4 3 4 v1 0 1 0 0