离散数学第7章课件.ppt

第四篇 图论;例：用定理解决哥尼斯堡桥的问题　 ;第四篇 图论;WWW;复杂网络的事例——社会网络;复杂网络的事例——交通运输网络;复杂网络的事例——生物网络;Santa Fe 研究所的科学家合作网;经济物理学科学家合作网;复杂网络的事例——中药方剂网示意图;§1 图的基本概念;§1 图的基本概念;§1 图的基本概念;§1图的基本概念;§1图的基本概念;§1图的基本概念;§1图的基本概念;§1图的基本概念;§1图的基本概念;§1图的基本概念;§1图的基本概念;§1图的基本概念; 定义：在图G=V，E，v?V，与结点v关联的边数称为该点的度数，记为deg(v)。 孤立结点的度数为0。 图G最大度记为?(G)=max{deg(v)|v?V(G)}， 最小度数记为 ?(G)=min{deg(v)|v?V(G)};§1图的基本概念;如：G1是无向图，deg(v1)=3，deg(v2)=1 G2是有向图，deg+(v1)= 2 ，deg-(v1)=3，deg(v1)=5，;定理：每个图中，结点度数总和等???边数的两倍。即 ?deg(v)=2|E| v?V ;定理：在任何图中, 度数为奇数的结点必定是偶数个。;定理：在任何有向图中，所有结点的入度之和等于所有结点的出度之和。;定义：含有平行边的图称为多重图。;;;;;;;;两图同构的一些必要条件： 1.结点数目相同； 2.边数相等； 3.度数相同的结点数目相等。;§2 路与回路;例如 路：v1e2v3e3v2e3v3e4v2e6v5e7v3 v5e8v4e5v2e6v5e7v3e4v2 v4e8v5e6v2e1v1e2v3 v2e1v1e2v3e7v5e6v2;§2 路与回路;§2路与回路;§2路与回路;§2路与回路;§2路与回路;§2路与回路;§2路与回路;§2路与回路; 定义：设无向图G =V,E是连通图,若有结点集V1?V,使图G中删除了V1的所有结点后,所得到的子图是不连通图,而删除了V1的任何真子集后,所得到的子图仍是连通图,则称V1是G的一个点割集(cut-set of nodes) 。若某一个点构成一个点割集，则称该点为割点。;s;§2 路与回路;§2 路与回路;§2 路与回路;§2 路与回路;§2路与回路;§2路与回路;§2路与回路;§2路与回路;§2路与回路;§2 路与回路;§2路与回路;§2路与回路;§2路与回路;§2路与回路;§2路与回路;§2 路与回路;§2路与回路;§2路与回路;§2 路与回路;§2 路与回路;§2 路与回路;§2 路与回路;§2 路与回路;§2 路与回路;§2 路与回路;§2 路与回路;§2 路与回路;§3图的矩阵表示;§3图的矩阵表示;§3图的矩阵表示;;§3图的矩阵表示;§3图的矩阵表示;§3图的矩阵表示;§3图的矩阵表示;§3图的矩阵表示;§3图的矩阵表示;可达矩阵表明了图中任意两结点间是否至少存在一条路以及在结点处是否有回路。 从图G的邻接矩阵A可以得到可达矩阵P，即令Bn=A+A2+A3+…+An，再从Bn中非零元素改为1而零元素不变，这种变换后的矩阵即是可达矩阵P。;§3图的矩阵表示; 3) 每一条边关联两个结点,故每一列中只有两个1。 4) 每一行中元素之和等于该行对应的结点的度数。 5) 两个平行边其对应的两列相同。 6) 同一个图当结点或边的编号不同时，其对应的矩阵只有行序列序的差别。 ;有向图的关联矩阵 ; 有向图的关联矩阵的特点： (1)每一列中有一个1和一个-1，对应一边一个始点、一个终点，元素和为零。 (2)每一行元素的绝对值之和为对应点的度数。-1的个数等于入度，1的个数等于出度。; ; ; 有向图G的两行相加定义为：第i行第j列的对应元素算术相加；相当于删除结点vi与结点vj之间的关联边，合并结点vi和vj 。合并后得到的新结点记为vi,j 。 无向图G的两行相加定义为：第i行第j列的对应元素模2相加；相当于删除结点vi与结点vj之间的关联边，合并结点vi和vj 。合并后得到的新结点记为vi,j 。 ;3、关联矩阵的秩 ; ;例：写出如图7-3.11所示的图G的完全关联矩阵，并验证其秩如定理7-3.2所述。;§4 欧拉图和汉密尔顿图; 由于有了欧拉路和欧拉回路的判别准则，因此哥尼斯堡七桥问题立即有了确切的否定答案，因为从图中可以看到deg(A)＝5，deg(B)＝deg(C)＝deg(D)=