离散数学导论第八章图.ppt

该【离散数学导论第八章图 】是由【wxq362】上传分享，beplayapp体育下载一共【25】页，该beplayapp体育下载可以免费在线阅读，需要了解更多关于【离散数学导论第八章图 】的内容，可以使用beplayapp体育下载的站内搜索功能，选择自己适合的beplayapp体育下载，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此beplayapp体育下载到您的设备，方便您编辑和打印。离散数学导论第八章图CATALOGUE目录图的基本概念图的连通性图的最短路径问题图着色问题图的应用01图的基本概念定义图是由顶点集和边集组成的数据结构,顶点集中的元素称为顶点,边集中的元素称为边。性质图具有无向性、有向性、连通性、简单性等性质。无向图中的边没有方向,而有向图中的边有方向。连通图中的任意两个顶点之间都存在路径,简单图中的边没有自环和多重边。定义与性质邻接矩阵用矩阵表示图,矩阵的行和列对应于顶点,矩阵的元素表示顶点之间的边。邻接表用链表表示图,链表中的每个节点包含一个顶点和与其相邻的顶点列表。图的绘制通过图形界面绘制图,可以直观地展示图的形状和结构。图的表示方法图的分类无向图和有向图根据边的方向进行分类,无向图的边没有方向,而有向图的边有方向。简单图和多重图根据边的数量进行分类,简单图中没有自环和多重边,而多重图中可以有自环和多重边。欧拉图和哈密顿图根据路径的长度进行分类,欧拉图中存在一条遍历所有顶点的路径,哈密顿图中存在一条遍历所有顶点的回路。02图的连通性图中的任意两个顶点之间都存在一条路径,则称该图为连通图。连通性定义在无向图中,如果任意两个顶点之间都存在一条路径,则称该无向图为连通无向图。无向图的连通性在有向图中,如果任意两个顶点之间都存在一条有向路径,则称该有向图为强连通有向图。有向图的连通性连通性的定义连通性性质1一个连通图至少包含一条边。连通性性质3一个连通图中的任意两个顶点都可以通过一条路径相互到达。连通性性质2在连通图中,任意两个顶点之间都存在唯一的路径。连通性的性质最小生成树定义一个连通无向图中,一棵包含所有顶点且边权和最小的生成树称为最小生成树。最小生成树的性质最小生成树是唯一的,且其边权和代表了从任意一个顶点到其他所有顶点的最小距离。最小生成树的算法常见的最小生成树算法有Prim算法和Kruskal算法。最小生成树030201