资源简介

《计算机数学》课程教案
教案编写人：
课程名称 计算机数学 本次内容 图的矩阵表示
授课班级 时 间 第 周 第 次 教学课时 /单元课时 /项目课时
学习目标 知识目标： 1.无向图的邻接矩阵和关联矩阵 2.有向图的邻接矩阵和关联矩阵 能力目标： 1.能够根据矩阵画出对应的图 2.能够根据图写出相对应的矩阵 3.能够熟记邻接矩阵和关联矩阵的特点 素质目标： 动手动脑能力的培养 观察理解力的培养
教学 重难点 1.无向图的邻接矩阵和关联矩阵 2.有向图的邻接矩阵和关联矩阵 3.邻接矩阵和关联矩阵的特点
课后总结 建议学时2学时
一、图的邻接矩阵
定义6.2.1 在无向图中，，如果用表示顶点与之间的边数，则称矩阵为无向图的邻接矩阵，记为
.
例6.2.1 请写出右图所表示的无向图的邻接矩阵.
解 根据邻接矩阵的定义，无向图 ，
，则
例6.2.2 已知无向图的邻接矩阵，请画出对应的无向图.
解 详见书上例题
通过上面两个例题，我们不难发现无向图的邻接矩阵的特征：
无向图的邻接矩阵是一个对称矩阵；
无向图的邻接矩阵的所有元素之和等于该无向图所有顶点的总度数之和，也就是等于边数的两倍.
定义6.2.2 在有向图中，，如果用表示以顶点为起点，以为终点的有向边的条数，则称矩阵为有向图的邻接矩阵，记为.
例6.2.3 请写出右图所表示的有向图的邻接矩阵.
解 根据邻接矩阵的定义，有向图 ，
，则
例6.2.4 已知有向图的邻接矩阵，请画出对应的有向图.
解 详见书上例题
通过上面两个例题，我们不难发现有向图的邻接矩阵的特征：
有向图的邻接矩阵每一行的元素之和等于该行所对应顶点的所有出度之和；
有向图的邻接矩阵每一列的元素之和等于该列所对应顶点的所有入度之和；
有向图的邻接矩阵的所有元素之和等于该有向图的边数.
二、图的关联矩阵
定义6.2.3 设无向图是一个图，即，，如果用表示顶点与作为边端点的次数，则称矩阵为无向图的关联矩阵，记为.
例6.2.5 请写出右图所表示的无向图的关联矩阵.
解 根据关联矩阵的定义，无向图
，，
，则
例6.2.6 已知无向图的关联矩阵，请画出对应的无向图.
解：详见书上例题
通过上面两个例题，我们不难发现：无向图的关联矩阵有如下特征：
无向图的关联矩阵任意一行的元素之和等于该行所对应顶点的度数之和；
无向图的关联矩阵任意一列的元素之和等于2，这是因为与每条边相关联的顶点有2个（环的顶点视为2个）；
无向图的关联矩阵的所有元素之和等于该无向图的边数之和的两倍.
定义6.2.4 设有向图是一个没有环的图，即，，如果 表示与边相关联的顶点的情况，即
则称矩阵为有向图的关联矩阵，记为.
例6.2.7 请写出右图所表示的有向图的关联矩阵.
解 根据有向图关联矩阵的定义，有向图
，，
，则
例6.2.7 已知有向图的关联矩阵，请画出对应的有向图.
解 图略，见书
通过上面两个例题，我们不难发现有向图的关联矩阵具有如下特征：
有向图的关联矩阵中任意一行的元素1的个数等于该顶点的出度，元素“-1”的个数等于该顶点的入度；
有向图的关联矩阵的任意一列的所有元素之和都等于0，因为每天有向边都有一个起点一个终点；
有向图的关联矩阵的所有元素之和等于0，即所有的元素1的个数等于所有的元素-1的个数，且都等于该有向图有向边的条数.

展开更多......

收起↑