图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 将此问题通过图的模型描述: 下图中,点—各城市,带箭头连线—从箭尾城市到箭头城市已 订购有机票,带箭头连线旁的数字机票数量。 郑州办事处已订有的到 北京的机票数量。 6
6 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 将此问题通过图的模型描述： 下图中，点——各城市，带箭头连线——从箭尾城市到箭头城市已 订购有机票，带箭头连线旁的数字——机票数量。 成 重 武 昆 上 广 西 郑 沈 京 8 郑州办事处已订有的到 北京的机票数量
图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图及其分类和术语 图论中所研究的图并非几何学中的图,也不是绘画中的图。在 这里我们所关心的仅仅是图中有多少个点,点与点之间有无线来连 接,也就是说我们研究的是某个系统中的元素—点,以及这些元 素之间的某种关系—连线。 定义:图 个图G是一个有序二元组(V,E),记为G =(V,E)其中(1)V是一个有限非空的集合,其元素称为G的 点或顶点,而称V为G的点集V=v1,V2,…,vn};(2)E是Ⅴ 中元素的无序对(vp,v所构成的一个集合,其元素称为G的边, 般表示为e=(v,v),而称E是G的边集
7 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图及其分类和术语 图论中所研究的图并非几何学中的图，也不是绘画中的图。在 这里我们所关心的仅仅是图中有多少个点，点与点之间有无线来连 接，也就是说我们研究的是某个系统中的元素——点，以及这些元 素之间的某种关系——连线。 定义：图——一个图G 是一个有序二元组（V，E），记为 G =（V，E）其中（1） V 是一个有限非空的集合，其元素称为G 的 点或顶点，而称V为G 的点集 V ={v1，v2，···，vn}；（2）E 是V 中元素的无序对(vi，vj ) 所构成的一个集合，其元素称为G 的边， 一般表示为 e =(vi，vj )，而称E 是G 的边集
图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图及其分类和术语 边(无向边)没有方向的连线 弧(有向边)—带有方向的连线 无向图 有向图 简单图 多重图 完全图 二部图(偶图,双图) 子图 真子图 生成子图 点生成子图 边生成子图点的次 奇次点 偶次点 链 圈 路 回路 赋权图
8 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图及其分类和术语 边（无向边）—— 没有方向的连线 弧（有向边）—— 带有方向的连线 无向图 有向图 简单图 多重图 完全图 二部图（偶图，双图） 子图 真子图 生成子图 点生成子图 边生成子图 点的次 奇次点 偶次点 链 圈 路 回路 赋权图
图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图及其分类和术语 连通图 在众多各类图中有一类在实际应用中占有重要地位的图 连通图—在图中,任意两点间至少存在着一条链。 连通图 不连通图
9 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图及其分类和术语 连通图 在众多各类图中有一类在实际应用中占有重要地位的图 连通图——在图中，任意两点间至少存在着一条链。 连通图 不连通图
图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图与矩阵 在图与网络分析的应用中,将面临一个问题—如何分析、 计算一个较大型的网络,这当然需借助快速的计算工具—计算机。 那么,如何将一个图表示在计算机中,或者,如何在计算机中存储 个图呢?现在已有很多存储的方法,但最基本的方法就是采用矩 阵来表示一个图,图的矩阵表示也根据所关心的问题不同而有 邻接矩阵、关联矩阵、权矩阵等。 10
10 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图与矩阵 在图与网络分析的应用中，将面临一个问题——如何分析、 计算一个较大型的网络，这当然需借助快速的计算工具——计算机。 那么，如何将一个图表示在计算机中，或者，如何在计算机中存储 一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩 阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有—— 邻接矩阵、关联矩阵、权矩阵等