《离散数学》第6章 图的基本概念.ppt

1、多伦是一个古老的数学领域，它起源于游戏难题的研究。多伦的内容很丰富，应用相当广泛，很多科系(如操作研究、信息论、控制论、网络理论、博弈论、化学、生物学、物理、社会科学、语言学、计算机科学等)都用作解决实际问题和理论问题的工具。随着电脑科学的发展，多伦在上述各学科中的作用越来越大，同时多伦本身也得到了充分的发展。本课程在第6章和第7章介绍了与电脑科学密切相关的导论的基础内容。图论简介，内容：直接图，无向图的基本概念。中点：1，直接图，无方向图的定义，6章图的基本概念，1节无方向图和无方向图，5，图的同构定义。一、一、绘画的概念。1，定义。无序产品，无向度，有向度，2，图的表示。直接图，无向图的顶

2、点显示为小圆圈。图形表示为右：图形表示为右：3，相关概念。孤立点是无限关联的点。具有平行边的多个图形。简单图没有平行的边和环。例如，1(1)处的孤立点、悬挂点、悬挂边、环、平行边、重量2、多重图形。4，全图(如，2，顶点图，握手整理)。1，顶点度(度)。例如，在1的(2)中，2，握手整理。清理1:清理2:推断：在某个图中，奇数度的顶点数是偶数。示例2(1)(2，3，4，5，6，7)，(1，2，2，3，4)是否可以配置无向图的度数序列？为什么？如果可能，请绘画。(2)插图中的11个边、1个4度顶点、4个3度顶点和其他顶点的角度小于2。最少有多少个顶点？三、子图、补充图。1，定义子图形：导出子图形

3、，示例3，在上图中，(1)(6)是(1)的子图形。其中，(2)(6)是实际子图形，(1，2，定义补充图形)。例3中，4，图的同构。定义：示例4，分析：仅以下三幅图：分析：仅以下四幅图：内容：图的走刀、环、连接、点切削集、边切削集。2，图的连接性概念，3，短线，距离的概念。第二通道，循环，图形的连接性，1，路径，循环。1，路径(循环)，2，简单路径，简单循环。简单路径(轨迹)、简单循环(闭合轨迹)、复杂路径(循环)、3、基本路径、基本循环、基本路径(路径)、基本循环(圆)、示例1、(1)、长度3，定理3:推论：定理4:推论：第二，图形的连接性。1，连接，可以到达。2，短线，距离。短距离善意长度，

4、(2)，3，无向图的连接。4，直接图的连接。示例2，强连接，单向连接，单向连接，弱连接，非连接图形，3，点切削集，边切削集。1，设置无向图是连接图。如果存在顶点集，则删除(删除中间顶点和关联边)后，生成的子图形不连接或正常图形。删除实际子集将链接结果子图形。也就是说，如果“点切削集”只有一个顶点，则该点称为剪切点，2，无向图称为连接图，如果有一组边，则删除(从中删除所有边)将导致生成的子图形不连接或为常规图形。删除实际子集将链接结果子图形。也就是说，如果边剪切集中只有一条边，则该边是剪切边或腿、内容：关联矩阵、邻接矩阵、中点：1、直接图形、无方向图形的关联，理解：有向图的可达矩阵。第三个图的矩

5、阵表示1，无向图的关联矩阵。解决方案：2，性格。(1)，(2)，2，直接图的相关矩阵。其中解决方案：2，属性。(1)、(2)、(3)、3，直接图形的邻接矩阵。解决方案：2，性格。，(1)，(2)，(3)，(1)命令，矩阵乘法，其中，(2)设置，4，直接图形的可到达性矩阵。(了解)，可访问性矩阵，第4部分最短路径和关键路径，内容：权重图表，最短路径，Dijkstra算法，PERT图表，关键路径，重点：Dijkstra算法，了解：关键路径问题，第1部分，第1部分否则，转到步骤2，在修改阶段中，每个顶点的标签：1、基本概念。第六章摘要和案例，2，使用。(1)灵活运用握手整理和推理，(2)画两个图形是否同构，(3)符合特定条件的子图，报道等。二、通道、循环、图的连通性。1，基本概念。2，使用。(1)确定直接或无方向图的路径(循环)类型。(2)查找短线和距离。(3)确定直接图形连接的类型。第三，图的矩阵表示。1，基本概念。2，使用。(1)关联矩阵的行与顶点角度的关系。第四，最短路径和主要路径，1，基本概念。卷度，最短路径，标记，pertmap，最早完成时间，后续