《第八章1图概念课件.ppt》由会员分享，可在线阅读，更多相关《第八章1图概念课件.ppt（27页珍藏版）》请在三一办公上搜索。
1、8.1 基本概念,教学内容1.图的定义、种类和术语 有向边、无向边、加权边 有向图、无向图、加权图 顶点的度、邻接点、子图 路径、回路、图的连通性 生成树和生成林2.图的主要运算 先深搜索、先广搜索 找生成树（最小生成树）找路径（最短路径）,教学要求1.了解图的定义 种类和有关术语2.了解图的主要运算,8.1.1 图的定义和种类,1.图（graph）的定义,由用于表示事物的顶点（vertex）集合V，以及表示事物之间关系的边（edge）集合E构成 记作G=（V，E）顶点数目n0，边数目m0画图时，顶点用圆圈表示，边用线条（或弧线）表示顶点名用大写字母A，B，C表示（写在圈内或圈外）顶点变量名用
2、小写字母v，w，s表示,2有向边（directed edge）,顾名思义，带有方向的边,顶点v和w之间的有向边表示成v：边的尾（tail）；w：边的头（head）边是由v射入w的；w是与v相邻（adjacent）的顶点（w是v的邻接点）有向边也称弧（arc）与 是不同的边有向边用带箭头的线条表示，箭头指向边的头,3无向边（undirected edge）,不带方向的边,顶点v和w之间的无向边表示成（v，w）边是关联于v和w的v与w互为邻接点（v，w）与（w，v）表示同一条边无向边用不带箭头的线条表示,边表示顶点间的某种关系无向边：对称关系（如同志关系）有向边：非对称关系（如领导和被领导关系）单
3、行道：有向边；双行道：无向边,4加权边（labeled edge）,边附带一个实数作为权（weight）,边的权可以表示边的长度、沿着边旅行所需的费用或时间、工程（输电线路、通信线路、高速公路等）造价等（这里只研究非负权）,权又统称为耗费（cost），俗称长度（length）但不一定满足三角不等式（两边之和大于第三边）,画图形时，权标在边旁边,5图的种类,种类繁多，分类的方法各异，最常见的有：,有向图（directed graph，digraph）边都有向无向图（undirected graph）边都无向混和图 有些边有向，有些边无向（可化为有向图）简单图 无重复边，无到自身的边（形如的边）多
4、重图 无上述限制加权图（labeled graph）边均带权,边权图称网（network），非加权图也称0/1图,这里只研究简单图（简单的有向、无向图，简单的有向、无向加权图）,有向图示例,无向图示例,无向加权图示例,A,B,C,D,E,120,74,87,53,60,91,46,8.1.2 有关术语0,1.顶点的度（degree）,有向图的顶点度：v的出度（out-degree）：v射出的边数（以v为尾）v的入度（in-degree）：射入v的边数（以v为头）v的度（degree）：v的出度与入度之和,8.1.2 有关术语1,1.顶点的度（degree）,无向图的顶点度：v的度（degree
5、）：与v关联的边数,2.子图（subgraph）0,原图的一部分,由原图中部分顶点，以及这些顶点之间的一部分边组成的图,2.子图（subgraph）1,原图的一部分,由原图中部分顶点，以及这些顶点之间的一部分边组成的图,3.路径和回路（subgraph）0,路径（path）：首尾相接的边序列,回路径（cycle）：起点与终点重合的路径简单路径：边不重复；基本路径：中间无重复顶点,3.路径和回路（subgraph）1,路径（path）：首尾相接的边序列,回路径（cycle）：起点与终点重合的路径简单路径：边不重复；基本路径：中间无重复顶点,4无向图的连通性0,v与w连通（connected）：顶
6、点v到w有路径也称v可到达w,相关概念：孤立点：与任何点都不连通孤悬边：删除边（v，w）后，v或w就变成孤立点连通图（connected graph）任何两顶点都连通连通分量（connected component）极大连通子图极大指的是在满足连通的条件下，尽可能多的含有图中的顶点以及这些顶点之间的边连通图只含一个连通分量,4无向图的连通性1,示例,4无向图的连通性2,示例,5有向图的连通性0,v与w连通（connected）：v到顶点w路径也称v可到达w,相关概念：强连通图（strongly connected graph）：任何两点v和w均相互连通强连通分量（strongly connec
7、ted components，或strong components）：极大强连通子图极大指的是在满足强连通的条件下，尽可能多的含有图中的顶点以及这些顶点之间的边强连通图只含一个强连通分量,5有向图的连通性1,示例,5有向图的连通性2,示例,6生成树和生成林 0,无向连通图的生成树（spanning tree）：是图的一种连通子图，它含有图的全部n个顶点，但只含有足以使图保持连通的n-1条边,相关概念：生成树也称支撑树生成树不唯一生成森林（spanning forest）：无向非连通图每个连通分量有一棵生成树，构成图的生成森林,6生成树和生成林 1,示例,6生成树和生成林 2,示例,精品课件！,精品课件！,小结,1.图的定义、种类和有关术语,有向边、无向边、加权边、有向图、无向图、加权图顶点的度、邻接点、子图、路径、回路、有向和无向图的连通性、生成树和生成林,2.图的主要运算先深搜索，先广搜索，找连通分量找生成树（最小生成树），找路径（最短路径）,
