高等学校21卌纪教材 第十章图的概念与表示 10.1图的基本概念 10.2解或路与圈或回路 10.3图的矩阵表示 PT PRESS 人民邮电出版社 退出
第十章 图的概念与表示 10.1 图的基本概念 10.2 链(或路)与圈(或回路) 10.3 图的矩阵表示 退出
高等学校21卌纪教材 10.1图的基本概念 什么是图?可用一句话概括,即:图是用点 和线来刻划离散事物集合中的每对事物间以某 种方式相联系的数学模型。因为它显得太抽象, 不便于理解,所以有必要给出另外的回答。下 面便是把图作为代数结构的一个定义 PT PRESS 人民邮电出版社
10.1 图的基本概念 什么是图?可用一句话概括，即：图是用点 和线来刻划离散事物集合中的每对事物间以某 种方式相联系的数学模型。因为它显得太抽象， 不便于理解，所以有必要给出另外的回答。下 面便是把图作为代数结构的一个定义
高等学校21卌纪教材 定义10.1.1一个图G定义为一个三元组,记作G=。其中是个非空 有限集合,它的元素称为结点;E也是个有限集 合,其元素称为边,而是从E到中的有序对 或无序对的映射 PT PRESS 人民邮电出版社
定义10.1.1 一个图G定义为一个三元组，记作G=。其中V是个非空 有限集合，它的元素称为结点；E也是个有限集 合，其元素称为边，而φ是从E到V中的有序对 或无序对的映射
高等学校21卌纪教材 由定义可知,图G中的每条边都与图中的 无序或有序结点对相联系的。若边e∈E与无序 结点对(v,v)相联系,则v()=(v,v) 这时边e称为无向边,有时简称为边;若边e∈E 与有序结点对, 此时边e称为有向边或弧,v称为弧e的始结点 v称为弧e的终结点。 PT PRESS 人民邮电出版社
由定义可知，图G中的每条边都与图中的 无序或有序结点对相联系的。若边e∈E与无序 结点对〔vi，vj〕相联系，则φ(e)=〔vi，vj〕， 这时边e称为无向边，有时简称为边；若边e∈E 与有序结点对相联系，则φ(e)=， 此时边e称为有向边或弧，vi称为弧e的始结点， vj称为弧e的终结点
高等学校21卌纪教材 若结点v与v由一条边(或弧)所联结,则称 结点和是边(或弧)e的端结点;同时也称结点 与是邻接结点,记作adv;否则为非邻接 结点,记作 V; nadj v;也说边(或弧)e关联w与v 或说结点v与v关联边(或弧)eo关联同一个结点 的两条边或弧称为邻接边或弧。而联结一结点 与它自身的一条边,称为环。环的方向是无意 义的。 PT PRESS 人民邮电出版社
若结点vi与vj由一条边(或弧)e所联结，则称 结点vi和vj是边(或弧)e的端结点；同时也称结点 vi与vj是邻接结点，记作viadj vj；否则为非邻接 结点，记作vi nadj vj；也说边(或弧)e关联vi与vj 或说结点vi与vj关联边(或弧)e。关联同一个结点 的两条边或弧称为邻接边或弧。而联结一结点 与它自身的一条边，称为环。环的方向是无意 义的
高等学校21卌纪教材 如果把图G中的弧或边总看作联结两个结 点,则图G可简记为G=,其中V是非空 结点集,E是联结结点的边集或弧集。 定义10.1.2在图G=中,如果每条 边都是弧,该图称为有向图;若每条边都是无 向边,该图G称为无向图;如果有些边是有向边, 另一些边是无向边,图G称为混合图 PT PRESS 人民邮电出版社
如果把图G中的弧或边总看作联结两个结 点，则图G可简记为G=，其中V是非空 结点集，E是联结结点的边集或弧集。 定义10.1.2 在图G=中，如果每条 边都是弧，该图称为有向图；若每条边都是无 向边，该图G称为无向图；如果有些边是有向边， 另一些边是无向边，图G称为混合图
高等学校21卌纪教材 定义10.13在图G=中,如果任何 两结点间不多于一条边(对于有向图中,任何两 结点间不多于一条同向弧),并且任何结点无环, 则图G称为简单图;若两结点间多于一条边(对 于有向图中,两结点间多于一条同向弧)图G称 为多重图,并把联结两结点之间的多条边或弧 称为平行边或弧,平行边或弧的条数称为重数。 PT PRESS 人民邮电出版社
定义10.1.3 在图G=中，如果任何 两结点间不多于一条边(对于有向图中，任何两 结点间不多于一条同向弧)，并且任何结点无环， 则图G称为简单图；若两结点间多于一条边(对 于有向图中，两结点间多于一条同向弧)图G称 为多重图，并把联结两结点之间的多条边或弧， 称为平行边或弧，平行边或弧的条数称为重数
高等学校21卌纪教材 定义10.1.4给每条边或弧都赋予权的图 G=,称为加权图,记为G=<V,E,W, 其中W表示各边之权的集合 加权图在实际中有许多应用,如在输油管 系统图中权表示单位时间流经管中的石油数量; 在城市街道中,权表示表示通行车辆密度;在 航空交通图中,权表示两城市的距离等等。 PT PRESS 人民邮电出版社
定义10.1.4 给每条边或弧都赋予权的图 G=，称为加权图，记为G=， 其中W表示各边之权的集合。 加权图在实际中有许多应用，如在输油管 系统图中权表示单位时间流经管中的石油数量； 在城市街道中，权表示表示通行车辆密度；在 航空交通图中，权表示两城市的距离等等
高等学校21卌纪教材 定义10.1.5在无向图G=<V,E中,如果V 中的每个结点都与其余的所有结点邻接,即 (v以)(yv)v,v∈(v,w)∈E 则该图称为无向完全图,记作KH。若 =n,该图记作Kn PT PRESS 人民邮电出版社
定义10.1.5 在无向图G=中，如果V 中的每个结点都与其余的所有结点邻接，即 (vi )(vj )(vi，vj∈V→〔vi，vj〕∈E) 则该图称为无向完全图，记作K|V|。若 |V|=n，该图记作Kn
高等学校21卌纪教材 在一个图中,如果一个结点不与任何 其他结点邻接,则该结点称为孤立结点。 仅有孤立结点的图称为零图。显然,在零 图中边集为空集。若一个图中只含一个孤 立结点,该图称为平凡图。 PT PRESS 人民邮电出版社
在一个图中，如果一个结点不与任何 其他结点邻接，则该结点称为孤立结点。 仅有孤立结点的图称为零图。显然，在零 图中边集为空集。若一个图中只含一个孤 立结点，该图称为平凡图