第八章1图概念

王庆瑞制作8.1基本概念教学内容1.图的定义、种类和术语有向边、无向边、加权边有向图、无向图、加权图顶点的度、邻接点、子图路径、回路、图的连通性生成树和生成林2.图的主要运算先深搜索、先广搜索找生成树（最小生成树）找路径（最短路径）教学要求1.了解图的定义种类和有关术语2.了解图的主要运算王庆瑞制作8.1.1图的定义和种类1.图（graph）的定义版权所有不得擅用由用于表示事物的顶点（vertex）集合V，以及表示事物之间关系的边（edge）集合E构成记作G=（V，E）顶点数目n0，边数目m≥0画图时，顶点用圆圈表示，边用线条（或弧线）表示顶点名用大写字母A，B，C…表示（写在圈内或圈外）顶点变量名用小写字母v，w，s…表示用于描述多对多的网状关系2．有向边（directededge）顾名思义，带有方向的边版权所有不得擅用顶点v和w之间的有向边表示成v，wv：边的尾（tail）；w：边的头（head）边是由v射入w的；w是与v相邻（adjacent）的顶点（w是v的邻接点）有向边也称弧（arc）v，w与w，v是不同的边有向边用带箭头的线条表示，箭头指向边的头wv尾头3．无向边（undirectededge）不带方向的边版权所有不得擅用顶点v和w之间的无向边表示成（v，w）边是关联于v和w的v与w互为邻接点（v，w）与（w，v）表示同一条边无向边用不带箭头的线条表示wv边表示顶点间的某种关系无向边：对称关系（如同志关系）有向边：非对称关系（如领导和被领导关系）单行道：有向边；双行道：无向边4．加权边（labelededge）边附带一个实数作为权（weight）版权所有不得擅用边的权可以表示边的长度、沿着边旅行所需的费用或时间、工程（输电线路、通信线路、高速公路等）造价等（这里只研究非负权）权又统称为耗费（cost），俗称长度（length）但不一定满足三角不等式（两边之和大于第三边）画图形时，权标在边旁边BA50有向加权边wv16无向加权边5．图的种类种类繁多，分类的方法各异，最常见的有：版权所有不得擅用有向图（directedgraph，digraph）边都有向无向图（undirectedgraph）边都无向混和图有些边有向，有些边无向（可化为有向图）简单图无重复边，无到自身的边（形如v,v的边）多重图无上述限制加权图（labeledgraph）边均带权边权图称网（network），非加权图也称0/1图这里只研究简单图（简单的有向、无向图，简单的有向、无向加权图）有向图示例版权所有不得擅用ABCDE无向图示例版权所有不得擅用ABCDEF无向加权图示例版权所有不得擅用ABCDE120748753609146王庆瑞制作8.1.2有关术语01.顶点的度（degree）版权所有不得擅用有向图的顶点度：v的出度（out-degree）：v射出的边数（以v为尾）v的入度（in-degree）：射入v的边数（以v为头）v的度（degree）：v的出度与入度之和D点：出度2，入度0，度数2A点：出度2，入度2，度数4ABCDEC点：出度1，入度2，度数3王庆瑞制作8.1.2有关术语11.顶点的度（degree）版权所有不得擅用无向图的顶点度：v的度（degree）：与v关联的边数5度A，B，C：3度E，F：2度ABCDEF2.子图（subgraph）0版权所有不得擅用原图的一部分由原图中部分顶点，以及这些顶点之间的一部分边组成的图ABCDE原图ABC子图1ABCE子图22.子图（subgraph）1版权所有不得擅用原图的一部分由原图中部分顶点，以及这些顶点之间的一部分边组成的图子图1ABCD子图2ADEF原图ABCDEF3.路径和回路（subgraph）0版权所有不得擅用路径（path）：首尾相接的边序列回路径（cycle）：起点与终点重合的路径简单路径：边不重复；基本路径：中间无重复顶点ABCDEF路径1路径2回路3.路径和回路（subgraph）1版权所有不得擅用路径（path）：首尾相接的边序列回路径（cycle）：起点与终点重合的路径简单路径：边不重复；基本路径：中间无重复顶点ABCDE路径1路径2，回路回路4．无向图的连通性0版权所有不得擅用v与w连通（connected）：顶点v到w有路径也称v可到达w相关概念：孤立点：与任何点都不连通孤悬边：删除边（v，w）后，v或w就变成孤立点连通图（connectedgraph）任何两顶点都连通连通分量（connectedcomponent）极大连通子图极大指的是在满足连通的条件下，尽可能多的含有图中的顶点以及这些顶点之间的边连通图只含一个连通分量4．无向图的连通性1版权所有不得擅用示例ABCDEFG不连通的图孤悬点孤悬边A到E不可达4．无向图的连通性2版权所有不得擅用示例ABCDEFG不连通的图连通分量1连通分量25．有向图的连通性0版权所有不得擅用v与w连通（connected）：v到顶点w路径也称v可到达w相关概念：强连通图（stronglyconnectedgraph）：任何两点v和w均相互连通强连通分量（stronglyconnectedcomponents，或strongcomponents）：极大强连通子图极大指的是在满足强连通的条件下，尽可能多的含有图中的顶点以及这些顶点之间的边强连通图只含一个强连通分量5．有向图的连通性1版权所有不得擅用示例强连通图ABCDE5．有向图的连通性2版权所有不得擅用示例非强连通图ABCDE强连通分量1ABCDE强连通分量2C不可到达D6．生成树和生成林0版权所有不得擅用无向连通图的生成树（spanningtree）：是图的一种连通子图，它含有图的全部n个顶点，但只含有足以使图保持连通的n-1条边相关概念：生成树也称支撑树生成树不唯一生成森林（spanningforest）：无向非连通图每个连通分量有一棵生成树，构成图的生成森林6．生成树和生成林1版权所有不得擅用示例ABCDEFG生成树1ABCDEFG原图ABCDEFG生成树26．生成树和生成林2版权所有不得擅用示例ABCDEFG非连通图生成林1ABCDEFG生成林2ABCDEFG精品课件！精品课件！王庆瑞制作小结1.图的定义、种类和有关术语有向边、无向边、加权边、有向图、无向图、加权图顶点的度、邻接点、子图、路径、回路、有向和无向图的连通性、生成树和生成林2.图的主要运算先深搜索，先广搜索，找连通分量找生成树（最小生成树），找路径（最短路径）版权所有不得擅用