计算机数学基础 -何春江 第13章 图论初步.pptVIP

第13章 图论初步 本章学习目标 我们在前面曾介绍过二元关系的图形表示，即关系图。在关系图中，我们主要关心研究对象之间是否有连线（图论中称为边），这样的图正是图论的主要研究对象。图论中还根据实际需要，将这类图进行了推广，并且把它当作一个抽象的数学系统来进行研究。通过本章学习，读者应该掌握以下内容： 本章学习目标 无向图、有向图的定义，图的基本术语的含义 子图、生成子图的概念 无向连通图及有向连通图的有关概念 通路、回路的概念 图的矩阵表示 赋权图的概念及应用 欧拉通路、欧拉回路、欧拉图和半欧拉图的概念 哈密尔顿通路、哈密尔顿回路、哈密尔顿和半哈密尔顿的概念 树的定义 最小生成树的求法 最优树的求法 主要内容 13.1 图的基本概念 13.2 图的矩阵表示 13.3 路与回路 13.4 树及其应用 13.1 图的基本概念 13.1 图的基本概念 13.1 图的基本概念 13.1 图的基本概念 13.1 图的基本概念 13.1 图的基本概念 13.1 图的基本概念 13.1 图的基本概念 13.1 图的基本概念 13.1 图的基本概念 13.1 图的基本概念 13.1 图的基本概念 13.1 图的基本概念 13.2 图的矩阵表示 13.2 图的矩阵表示 13.2 图的矩阵表示 13.2 图的矩阵表示 13.2 图的矩阵表示 13.2 图的矩阵表示 13.2 图的矩阵表示 有向图的完全关联矩阵也有类似于无向图的一些性质。如： （1）关联矩阵中每列的元素之和为0，说明有向图中每条边关联两个顶点，一个始点，一个终点。 （2）第i行元素的绝对值之和为对应顶点的度数，其中1的个数为出度，-1的个数为入度。 （3）关联矩阵中，1的个数与-1的个数相同，都等于边的数目，这说明有向图中各顶点入度之和等于出度之和，都等于边数，于是各顶点度数之和等于边数的2倍。 （4）若关联矩阵中有两列相同，说明图中这两列对应的边有相同的始点和终点，因而它们是平行边。 13.2.3 图的可达矩阵表示 13.2.3 图的可达矩阵表示 13.3 路与回路 13.3 路与回路 定理13.3.1 在n阶无向图中，如果存在一条从vi到vj的通路，则从vi到vj必有一条长度不大于n-1的基本通路。 证明 设从vi到vj存在的通路为vi…vj，若其中有相同的顶点vk，如vi…vk…vk…vj，则删去vk到vk的这些边，它仍是vi到vj的通路，如此反复进行，直到没有重复顶点为止，此时所得的通路就是vi到vj的基本通路。由于1条基本通路的长度比此通路中顶点数少1，而图中仅有n个顶点，故此基本通路的长度不大于n-1。 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.3 路与回路 13.4 树及其应用 13.4 树及其应用 13.4 树及其应用 13.4 树及其应用 定理13.4.3 设图有n个顶点，可用下面的算法产生最小生成树。 （1）选取最小边e1，设边数k=1； （2）若k=n-1，结束，否则转（3）； （3）设已选择边为e1，e2，…，ek，在G中选择不同于e1，e2，…，ek的边ek+1，使ek+1是满足{e1，e2，…，ek，ek+1}中无回路的权最小的边。 （4）k=k+1，转（2）。 上面给出的求最小生成树的算法，是克鲁斯卡尔在1956年首先提出的。 13.4 树及其应用 13.4 树及其应用 13.4 树及其应用 13.4 树及其应用 13.4 树及其应用 13.4 树及其应用 13.4 树及其应用 13.4 树及其应用 13.4 树及其应用 13.4 树及其应用 13.4 树及其应用 13.4 树及其应用 13.4 树及其应用 13.4 树及其应用 13.4 树及其应用 本章小结 13.4.3 有向树 给定了一组权w1，w2，…，wn，如何求最优树。1952年，霍夫曼给出一种算法：首先找出两个最小的权值w1和w2，然后对n-1个权w1+w2，w3，，…，wn求一棵最优树，并且将这棵最优树中的顶点w1+w2用以w1和w2为儿子的分枝点代替，依次类推，最后可转化为求有两片树叶的最优