《图的矩阵表》PPT课件.ppt

第八章图论 8 1图的基本概念8 2路径和回路8 3图的矩阵表示8 4二部图8 5平面图8 6树8 7有向树 8 3图的矩阵表示 1 邻接矩阵2 可达性矩阵3 可达性矩阵的应用4 关联矩阵 1 邻接矩阵 定义1设G 有向 无向 线图 有n个标定了次序的结点v1 v2 vn V 则n阶方阵A aij 称为G的邻接矩阵 这里 例1左下图的邻接矩阵 注 图的邻接矩阵与n个结点的标定次序有关 对于V中各元素不同的标定次序 可得出不同的邻接矩阵 不过这些矩阵可以通过交换行和列而相互得出 具有这样性质的矩阵称它们置换等价 例如 左下图的两个置换等价邻接矩阵 有向简单图在标定次序后得到唯一邻接矩阵 零图的邻接矩阵的元素全为0 称为零矩阵 完全图Kn的邻接矩阵是恰有n个0并全在对角线上的n阶 0 1 方阵 当有向线图代表关系 关系矩阵就是邻接矩阵 有向线图G V E 的邻接矩阵是A 则G的逆图G V E 的邻接矩阵是A的转置矩阵 记为AT 无向简单图的邻接矩阵是对称矩阵 A AT 有n个结点的赋权图G V E W 的邻接矩阵是n阶方阵A aij 其中当 vi vj E aij W vi vj 否则 aij 0 有n个结点的多重图的邻接矩阵是n阶方阵A aij 其中aij代表从vi到vj的边的重数 几个特殊图的邻接矩阵 邻接矩阵的图论意义 设A为无向简单图G的邻接矩阵 其第i行 列 元素为1的个数等于结点的度 邻接矩阵的图论意义 设A为无向简单图G的邻接矩阵 其第i行 列 元素为1的个数等于结点的度 设A为有向简单图G的邻接矩阵 A的第i行 列 和等于第i个结点的出 入 度 i 1 n v3的出度 1 1 0 1 3 v3的入度 0 1 0 0 1 邻接矩阵的图论意义 设A为无向简单图G的邻接矩阵 其第i行 列 元素为1的个数等于结点的度 设A为有向简单图G的邻接矩阵 A的第i行 列 和等于第i个结点的出 入 度 i 1 n B AAT bij 的元素bij ai1aj1 ainajn k表示有k个点 都是从i j引出的有向边的公共交点 特别地 bii是第i结点的出度 对偶地可讨论ATA的元素的图论意义 i j 练习 求AAT ATA 并由此求每个结点的出度与入度 练习 求AAT ATA 并由此求每个结点的出度与入度 定理1设简单有向图G 的邻接矩阵为A 则矩阵A k 中的第i行第j列元素等于G中从vi到vj长度为k的不同路径的数目 例A 2 中的第2行第1列元素等于2 说明从v2到v1长度为2的路的有两条 v2v4v1 v2v3v1 分析 a21 2 a21a11 a22a21 a23a31 a24a41 0 0 0 0 1 1 1 1 2注意从v2到v1长度为2的路中间必经由一个结点vk 即v2 vk v1 1 k 4 一般地 A m 中从i到j长为m的路径总数是aij m 条 过i的长为m的回路共有aii m 条 Br A A 2 A 3 A r 的元素bij表示从vi到vj长度小于等于r的不同路径总数 在n个结点的简单有向图中 基本路径长度不超过n 1 基本回路长度不超过n 故可用Bn 1 A A 2 A 3 A n 1 i j时 Bn A A 2 A 3 A n i j时 研究vi到vj的可达性和经vi是否存在回路的问题 bij 0 i j 表示从vi到vj可达 否则从vi到vj不可达 分属不同强分图 bij 0 i j 表示经vi存在回路 否则表示不存在经vi的回路 例2根据有向图和矩阵B5 验证 a b52 0 所以v2和v5分属两个强分图 b b11 0 所以没有经过v1的回路 c b53 3 所以从v5到v3长度不超过5的路径有3条 v1 v1 v1 2 可达性矩阵 定义2设G 为简单有向图 V v1 v2 vn 定义矩阵P pij 其中 有向图G中从vi到vj是否有路可达可通过矩阵运算而得到 P称为图G的可达性矩阵 方法 利用矩阵Bn Bn 1 确定P 当bij 0时 pij 0 否则 pij 1 方法 直接由邻接矩阵确定可达矩阵 P A A2 An 其中Ak为A的布尔方幂 方法1 先由邻接矩阵A求B4 B4 A A 2 A 3 A 4 然后写出可达矩阵P 计算可达矩阵举例 方法2 将A A 2 A 3 A 4 转换为布尔矩阵A A2 A3 A4则P A A2 A3 A4 例3求例2的图的可达性矩阵 v1 3 可达矩阵的应用 利用一个图的可达性矩阵 求出这个图的所有强分图 方法 图G的强分图可从矩阵P PT求得可求得G的强连通分支对应结点集为 1 2 3 4 5 4关联矩阵 定义3设G 是无向图 V v1 v2 vn E e1 e2 en 一个n m矩阵M mij 称为G的关联矩阵 其中mij是结点vi和ej的关联次数 定义4设G 是有向简单图 V v1 v2 vn E e1 e2 en 一个n m矩阵M mij 称为G的关联矩阵 其中 5 课堂练习 练习求如下有向图的邻接矩阵A 指出从v1到v4且长度为2和4的路 解 从v1到v4长度为2的路有1条 v1v2v4从v1到v4长度为4的路有3条 v1v2v4v2v4 v1v2v3v2v4 v1v4v2v3v4 作业 P2841P2853 关联矩阵