第5章 图与网络模.ppt

第5章 图与网络模型 练习1, 给定无向图G1和有向图G2如图所示(写出邻接矩阵）: 从邻接矩阵看图的性质: 无向图:每行1的个数=每列1的个数=对应结点的度 有向图:每行1的个数=对应结点的出度 每列1的个数=对应结点的入度 练习2.无向图的完全关联矩阵 1). 2.有向图的完全关联矩阵 1). * 定义 有序三元组G=(V,E, )称为一个图. 图的定义 定义 定义 返回 顶点的次数 例 在一次聚会中，认识奇数个人的人数一定是偶数。 子图 返回 关联矩阵 注：假设图为简单图 返回 邻接矩阵 注：假设图为简单图 返回 v1 ? ? v5 v4 ? v2 ? ? v3 G1 v3 ? ? v2 ?v4 ? v5 v1 ? G2 2).从关联矩阵看图的性质: a)每列只有二个1. (因为每条边只关联两个结点) b)每行中1的个数为对应结点的度数. c)如果两列相同,则说明对应的两条边是平行边. e1 e2 e3 e4 e5 e6 e7 v1 -1 1 0 0 0 0 0 v2 1 0-1 0-1 0 0 v3 0-1 1-1 0-10 v4 0 0 0 1 1 0 1 v5 0 0 0 0 0 1-1 M= 2).从关联矩阵看图的性质: a)每列只有一个1和一个-1. (每条边有一个起点一个终点) b)每行中1的个数为对应结点 的出度.-1个数是结点入度 基 本 概 念 返回 *