高等学校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定义为一个三元组<V, E,>,记作G=<V,E,>。其中是个非空 有限集合,它的元素称为结点;E也是个有限集 合,其元素称为边,而是从E到中的有序对 或无序对的映射 PT PRESS 人民邮电出版社
定义10.1.1 一个图G定义为一个三元组<V， E，φ>，记作G=<V，E，φ>。其中V是个非空 有限集合，它的元素称为结点；E也是个有限集 合，其元素称为边，而φ是从E到V中的有序对 或无序对的映射
高等学校21卌纪教材 由定义可知,图G中的每条边都与图中的 无序或有序结点对相联系的。若边e∈E与无序 结点对(v,v)相联系,则v()=(v,v) 这时边e称为无向边,有时简称为边;若边e∈E 与有序结点对<’嗲相联系,则@(e)≤v,y>, 此时边e称为有向边或弧,v称为弧e的始结点 v称为弧e的终结点。 PT PRESS 人民邮电出版社
由定义可知，图G中的每条边都与图中的 无序或有序结点对相联系的。若边e∈E与无序 结点对〔vi，vj〕相联系，则φ(e)=〔vi，vj〕， 这时边e称为无向边，有时简称为边；若边e∈E 与有序结点对<vi，vj>相联系，则φ(e)=<vi，vj>， 此时边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。关联同一个结点 的两条边或弧称为邻接边或弧。而联结一结点 与它自身的一条边，称为环。环的方向是无意 义的