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